Matrice : quoi utiliser?

Version imprimable

11/11/2009, 22h00
-={-_-}=-

Matrice : quoi utiliser?

Bonjour,
je suis en train de concevoir mini appli.
J'aurais besoin d'un objet matrice.

Qu'est ce que je dois faire?

1/ Faire un truc genre T[][] à la C?
2/ Faire un truc avec la STL (genre comme dans le bouquin de Stroustrup)?
3/ Dans Boost ya un object matrice?
4/ Dans pas mal d'appli que je connais ils utilisent ca : http://www.robertnz.net/nm_intro.htm ?
5/ Je reprends tout de zéro et je m'y met comme un grand?

bref je suis un peu perdu....

Autre petite question, pour un tableau à 2 colonnes c'est pas "too much" de faire une matrice? Dans la STL, il existe un truc pour faire ca direct?

Autre question (de débutant), Boost est-il libre? Pour un projet dans une entreprise peut-on utiliser boost sans problème?

Merci d'aider ce pauvre Débutant :mouarf:
11/11/2009, 22h06
Goten

Boost.ublas (et oui boost est libre, tu peux lire la licence boost pour voir les conditions d'utilisations).
sinon y'a aussi blitz++, mais c'est abandonné, dommage c'était vraiment bon.

L'avantage de pas refaire ça c'est que tu perds pas de temps, et que niveau perf ça va être dur de faire mieux (dans un cour laps de temps en tout cas)..
11/11/2009, 22h43
JolyLoic

Déjà, il faut savoir ce que tu entends par matrice. Manipuler des matrices de taille fixe 3*3 ou des matrices de taille variable 1000*1000 ne se fait pas de la même façon, les choix de conception sont différents.
11/11/2009, 22h48
-={-_-}=-

Citation:

Déjà, il faut savoir ce que tu entends par matrice. Manipuler des matrices de taille fixe 3*3 ou des matrices de taille variable 1000*1000 ne se fait pas de la même façon, les choix de conception sont différents.

Justement ya-t-il des best pratices avec tous ces objets(objects STL, BOOST)?
Ya-t-il des objects a choisir en fonction de leur taille pour des meilleures perf?

Je sais que c'est le cas pour les algo de tri en fonction de la taille des données.....

Les opérations que je souhaite faire :
2 types
1/ Aucune : sert juste à stocker des données
2/ Des opérations genre les méthodes numériques, algo d'optimisation.....
11/11/2009, 22h58
JolyLoic

En gros (je n'ai pas regardé ce sujet depuis longtemps) :

Petites matrices de taille fixe : L'objectif est de ne pas faire d'allocation dynamique, et éventuellement de dérouler des boucles. Blitz avait un truc pour ça, mais n'est plus trouvable. Je ne connais pas d'alternatives.

Grosses matrices : Ce qu'il y a dans boost constitue une base, mais ne va pas très loin en terme de fonctionnalités : C'est fait pour fonctionner avec d'autres libs plus complètes, mais ayant une interface moins orientée C++.

Dans le standard, il y a valarray, mais c'est un peu spécial à utiliser, et assez mal supporté en général.

Chez Intel, ils ont des choses (payantes, je crois), et sont en train d'en développer d'autre (la technologie Ct, par exemple). Un de leur but est de bien utiliser les capacités des processeurs, en particulier en parallèlisant certains calculs.
12/11/2009, 09h52
r0d

Sinon, faire une matrice soi-même n'est pas très compliqué et c'est une très bon exercice. Tu pourras prendre exemple sur la classe Dyn2dMatrix proposée ici.
12/11/2009, 10h52
-={-_-}=-

Je pense que tu as raison r0d.
Cet exercice doit etre un des plus classique.
Etant novice ca me permettra de découvrir pas mal de truc et continuer à apprendre.
Je pense que je vais aussi regarder le code de boost pour voir les fonctions qui ont été codées et m'en inspiré.

Merci aussi pour ton bout de code.
Ca va bien me servir.

Je vais aussi regarder les fonctions codées dans NR et dans GSL et faire un mix de tout ca...

Merci à vous.
12/11/2009, 11h04
Invité

Citation:

Envoyé par -={-_-}=-

Je vais aussi regarder les fonctions codées dans NR et dans GSL et faire un mix de tout ca...

La troisième édition de NR propose une petite classe de vecteurs et de matrices, codées en C++, et donne quelques conseils utiles (et pas du tout intuitifs) sur les problèmes qu'on rencontre. C'est à lire...

Sur les autres options... Je me méfierais d'une implémentation trop basique via la STL, au moins dès qu'on manipule de grosses matrices : la STL a tendance à copier énormément. Pour de petites matrices (2x2, 3x3, 4x4 ou nx2) c'est largement suffisant.

Si tu as de l'algèbre linéaire à faire (ou des stats) et de grosses matrices, alors boost est très vite insuffisant. La librairie que tu cites (newmat, ou une autre du même tonneau) est nécessaire. Ces choses sont souvent délicates à programmer soi même (il y a plein d'astuces liées à la stabilité des calculs, surtout en stats où les matrices qu'on utilise sont toujours fortement dégénérées, ie multicollinéaires).

Pour des choses plus pointues, tu peux aller chercher chez netlib.org, il y a beaucoup de choses, là, et de grande qualité en général.

Francois
12/11/2009, 14h31
-={-_-}=-

Citation:

Envoyé par fcharton

Ces choses sont souvent délicates à programmer soi même

Tu me conseilles plutot alors de m'interesser à un Newmat et d'y lire la doc ou alors de reprendre les fonctions pour réorganiser mon propre objet Matrice?

Merci
12/11/2009, 16h00
Invité

Citation:

Envoyé par -={-_-}=-

Tu me conseilles plutot alors de m'interesser à un Newmat et d'y lire la doc ou alors de reprendre les fonctions pour réorganiser mon propre objet Matrice?

Si tu dois faire les choses pour lesquelles Newmat est faite : matrices 10x10 et plus, et calculs un peu pointus, certainement. Si le but est juste de faire des matrices pour faire des calculs de perspective, ou de mouvement en 3D, non...

Francois
12/11/2009, 22h22
-={-_-}=-

Citation:

Envoyé par fcharton

Si tu dois faire les choses pour lesquelles Newmat est faite : matrices 10x10 et plus, et calculs un peu pointus, certainement. Si le but est juste de faire des matrices pour faire des calculs de perspective, ou de mouvement en 3D, non...

Francois

En gros c'est pour du calcul num. J'ai envie de mettre en c++ tout ce que j'ai vu. La prog que je vois est souvent trop horrible.
Si dja on fait du c++, autant faire de l'objet.
Donc j'ai envie de reprendre mes prog de ce que j'ai vu un peu partout pour les mettre a ma sauce.

Donc yaura du monté carlo. Des trucs 3 000 000 * 255... bref de la matrice quoi
13/11/2009, 00h20
Invité

Citation:

Envoyé par -={-_-}=-

En gros c'est pour du calcul num. J'ai envie de mettre en c++ tout ce que j'ai vu. La prog que je vois est souvent trop horrible.

Dans ce cas, pars de newmat... boost / blas, ce sont des trucs de base, mais ca ne va pas loin. newmat est ouvert, tu as les sources, et un certain nombre de questions de base sont déjà résolues. Va quand même voir du côté de netlib aussi...

Sur de très grosses matrices, évite la STL. Elle a une tendance à faire beaucoup de copies. Sur des petits trucs ce n'est pas grave, sur de grosses matrices... La force de newmat, c'est justement cette évaluation paresseuse...

Francois
13/11/2009, 10h20
-={-_-}=-

Ok Maitre de la Matrice. Neo c'est ca? :lol:

Bon plus serieusement, le débat que tu lance m'interesses.
J'aimerais en savoir un peu plus sur tout ca.

Quels sont les astuces à connaitre pour que les algos de matrices soient stables sur des matrices enormes?

Je veux pas te demander tous tes secrets mais en tant que debutant, j'aimerais connaitre quelques trucs pour que mes futurs appli codées dans le monde professionnel soient stables et rapides et pouvoir aussi arbitrer sur les différentes solutions (on va pas prendre le bazooka pour buter une mouche...:mouarf:)

D'avance merci
13/11/2009, 10h23
Goten

D'un point de vue purement performance, il faut mettre en place des expressions templates afin de dérouler les boucles etc.
13/11/2009, 10h39
Alp

Citation:

Envoyé par Goten

D'un point de vue purement performance, il faut mettre en place des expressions templates afin de dérouler les boucles etc.

Oui. Pour une VRAIE utilisation des matrices, pas juste 3 opérations qui se courrent après, il FAUT des expressions templates !
Sinon, en additionnant 100 matrices par exemple, t'aurais 200 boucles for, là où 2 auraient suffit !
Cf justement http://alpmestan.wordpress.com/2009/...plates-matter/ .
Après, t'as le choix entre blitz, MTL (je crois), NT2, ... Mais c'est un critère très important à mon avis.
13/11/2009, 11h49
Invité

La rapidité et la stabilité sont des problèmes distincts.

Pour la rapidité, il y a deux aspects :

1- une grosse matrice, ca occupe beaucoup de place en mémoire, il faut donc se garder d'en créer trop (rien qu'à copier c'est moche).
2- comme les matrices ont beaucoup d'éléments, cela signifie beaucoup d'opérations de base, à chaque calcul.

Pour les créations, il faut privilégier, partout où tu le peux, les opérations 'en place' (A+=B par rapport à C=A+B), par rapport aux fonctions qui retournent une copie. Il faut aussi se méfier comme de la peste des initiatives de ton compilateur (qui parfois crée des temporaires sans rien dire...), pour cela, ajoute un log dans le constructeur de tes objets matrice, tu seras fixé tout de suite... Il est aussi intéressant de définir des "super opérations": si tu fais souvent A=A*B+C prédéfinis la fonction.

Les expression templates dont parle Alp permettent notamment de réduire le nombre des "fonctions de base" qui te seront nécessaires.

Pour les opérations, c'est simple, il faut compter... Sur des matrices rectangulaires, l'ordre dans lequel on fait les calculs a souvent un effet sur leur nombre. Il faut aussi tirer partie des symétries (matrices symétriques et autres).

Enfin, si tu as des matrices creuses (avec beaucoup de coefficents à zéro), il NE FAUT JAMAIS les stocker comme des tableaux. Ca prend de la mémoire, et c'est lent en calcul (parce qu'on fait plein d'opérations inutiles sur les zéros).

Donc, en terme de vitesse, il va certainement falloir écrire des opérations spécialisées, pour les matrices creuses,et les symétriques. Regarde newmat!

En général, la bonne méthode, c'est de commencer par écrire sur le papier le nombre d'opérations qu'on doit faire, et d'essayer de simplifier le calcul avant de programmer...

Pour la stabilité, il faut un livre, Numerical Recipes est un excellent point de départ. Les problèmes varient énormément d'un calcul à l'autre, mais en gros, il faut avoir un peu lu sur l'algorithme du pivot et les problèmes de stabilité qu'il pose, et connaitre les SVD et la théorie autour. Ce sont à mon avis les bases.

Ensuite, si tu fais des stats, il faut être conscient des problèmes de conditionnement des matrices de variance covariance...

En gros, une matrice de variance covariance est symétrique, définie, positive, donc diagonalisable dans une base orthonormale. Comme les problèmes statistiques présentent toujours des corrélations (sinon on ne les étudierait pas... ce serait juste du bruit), il va y avoir des valeurs propres proches de zéro (jamais nulles parce que l'ensemble des matrices non inversibles est de mesure zéro).

Ces valeurs propres voisines de zéro sont en fait du "bruit" sur ta matrice. Le problème, c'est que quand tu inverses ta matrice, elles deviennent les principales valeurs propres (puisques les vp sont remplacées par leur inverse...) Et du coup, les petites erreurs sur les vecteurs propres correspondant (qui viennent de l'erreur statistique sur les coefficients de ta matrice) deviennent des facteurs très importants de ton calcul...

Le conditionnement, c'est le rapport entre la plus grand et la plus petite valeur propre de ta matrice. Plus il est grand, plus tu vas avoir des problèmes.

Pour les éviter, il faut utiliser des algorithmes stables (ie la SVD qui élimine cet "espace propre quasi-noyau"), ou réduire artificiellement le conditionnement (par régularisation, en ajoutant une petite diagonale à ta matrice de variance covariance avant tout calcul: identité fois 1e-4 ou un truc comme ca, ca fait des merveilles!), ou commencer par "réduire ton problème", en passant des le début dans un référentiel factoriel (la base des vecteurs propres de ta matrice), dont tu tronques les vecteurs correspondant aux petites valeurs propres (en gros ca revient à faire une analyse factorielle avant de commencer les calculs).

C'est pas facile facile, le calcul matriciel...

Pour te lancer, si tu veux toujours essayer d'écrire ta librairie (ce que je te conseille, c'est très formateur), je suggérerais
1- de réfléchir au stockage des matrices, notamment symétriques et creuses (rien que les symétriques on divise par deux la taille... les creuses, je ne te dis même pas)
2- d'implémenter les opérations de base (multiplication, somme) sur ces formats de stockage, et les conversions entre format
3- de te lancer dans les inversions/résolutions de système, via le pivot et les améliorations de celui ci, et éventuellement via des méthodes régularisées pour les gros systèmes dégénérés
4- d'écrire des SVD et des outils de diagonalisation

C'est beaucoup de travail mais c'est la "boite de base"

Francois
13/11/2009, 21h54
-={-_-}=-

Merci pour vos conseils.
Merci fcharton pour ton monologue passionnant.
J'ai compris plein de trucs.

Moi qui est l'habitude de faire de la gestion de projet, je me pose une question plus macro.

Comment je pourrais tester la rapidité et la meilleur perf de tel ou tel algo?
Comment monter un jeu de test interessant?
Certes c'est un point lointain... mais bon indispensable car j'aime bien tester fonction par fonction.
Ensuite quel est le niveau acceptable de rapidité pour chacun des tests que je vais monter?
J'aurais besoin de vos conseils avisés.

Bon passons au vif du sujet.....

Pour mon constructeur, je peux utiliser un objet STL ou je le code à la C?

Un ami me disait que passer par les fonctions C améliorait énormément la rapidité du code. C'est vrai ou c'est une légende informaticienne?
Je copie NewMat?
13/11/2009, 22h53
Alp

Bah en C tu peux oublier les expression templates... Ce qui est assez pénalisant, malgré le fait que du code C s'exécute un poil plus vite en moyenne.

Pour les tests, bah ça me semble assez évident, je ne vois pas où tu ne vois pas comment faire un benchmark dans ce cas précis :koi:
13/11/2009, 23h25
-={-_-}=-

Citation:

Envoyé par Alp

Pour les tests, bah ça me semble assez évident, je ne vois pas où tu ne vois pas comment faire un benchmark dans ce cas précis :koi:

C'est vrai c'est assez facile en fait :scarymov:
27/11/2009, 09h05
-={-_-}=-

Rebonjour tout le monde,
Je souhaite reprendre mon sujet car j'ai encore quelques questions...

J'ai pas encore commencer à coder ma partie Matrice.
J'ai préféré étudié, dans un premier temps, l'ensemble de mon projet et faire les schémas de mes objets. (Ne parlons pas d'UML car ca reste du bidouillage maison)

En faisant cela je me suis rendu compte que j'allais avoir besoin de tableau simple, de tableau pour faire des graph en 2D, des tableaux pour faire des graphs en 3D et des tableaux de séries temporelles.

Je voulais savoir si vous aviez déjà fait ce genre d'objets,comment vous les aviez organisé et comment les aviez vous optimisé?
N'oubliez pas que je vais avoir pas mal de données....

Je voulais savoir si, par exemple pour les series temporelles, il ne serait pas opportun de les exporter à un moment vers un fichier Txt et le requéter en SQL. Si oui à partir de quelle dimension? comment organiser ca proprement?
A quel moment le faire? Car je pense pour faire des calculs entre i et i-1 le SQL n'est pas adapté.

D'avance merci pour vos conseils.