Optimisation des matrices

Bonjour à toutes et à tous,

Je dois déporter un programme Matlab en C++ pour des questions de vitesse (because boucles en matlab). Je suis assez nouveau en C++ et plutôt que de partir d'un type int matrice [n][n] ou int** matrice, j'ai vu qu'il existe des librairies spécialement adaptées pour ce type de questions (traitement de matrices).

Ma question est la suivante:
Je dois faire des traitements très simples: initialiser des matrices de petites ou grandes tailles, modifier un grand nombre de valeurs dans une ou plusieurs matrices à chaque pas de temps, rien de plus compliqué.
Du coup je me demande si les packages spécialement adaptés pour traiter les matrices ne seraient pas un peu surdimensionnés pour ce que je veux faire. Ils sont certainement adaptés pour des calculs plus compliqués (inversions, triangulations, etc.) mais dans mon cas, pour les affectations par exemple, est-ce que j'y gagnerais forcément en temps de calcul ?

Je pose cette question car je suis sur un contrainte temps assez importante (pas du temps réel, mais je risque de me retrouver avec des matrices imposantes en milliers de lignes/colonnes).

Merci par avance pour vos conseils.

Gian

Utilises-tu les opérations mathématiques (addition, multiplication, ...) sur tes "matrices" ?

Si oui, alors une librairie de matrices (p.ex. boost.ublas) serait intéressante.
Si non, alors il est strictement inutile de passer par un paquet externe, et il suffit d'avoir un tableau à deux dimensions.

Eh bien, pour donner un ordre d'idée, en terme de temps, je n'effectue des opérations (additions, soustractions, etc.) entre deux ou plusieurs matrices que "rarement" (environ 5 à 10% du temps de calcul).
Les 90 à 95% du temps restant est plutôt consacré à mettre à jour un grand nombre de valeurs des matrices par des opérations impliquant des scalaires, voire des vecteurs (plus rare). Pour donner un exemple:
g(i,j) = c(i,j) + d(i,j)
ou g, c et d sont des matrices et i,j les indices.
J'ai aussi une composante temps qui consiste aussi à sauvegarder l'état des matrices entre chaque pas de temps (gourmand avec de grandes matrices donc).

Tu as déjà optimisé dans matlab?

Ca fait un bail que j'en ai pas fais, mais je pense que passer par des choses du style:

Code:

---

1 2 3

for j=1:n, A(j,:) = A(j,:) - A(j-1,:)

---

Au lieu de ,

Code:

---

1 2 3 4

for j=1:n, for i=1:m A(j,i) = A(j,i) - A(j-1,i)

---

lui permet de dérouler le traitement en C voir même de paralléliser si c'est bien fait?

Pardon, mal lu, oublie mon poste :x

Pas de soucis!
Sinon pour répondre à ta question, j'ai la pratique du Matlab, je sais qu'il faut tout écrire en matriciel et éviter les boucles, donc j'ai fait au mieux, mais il y a certaines boucles que je ne peux pas éviter.

Merci quand meme :)

Edit: Si ca peut aider, j'ai pas mal de min et max à calculer sur les matrices que j'ai et sur des parties plus "locales" des matrices (subset des matrices).
Edit2: quand je parle de subset, j'ai beaucoup d'extraction de voisinages à faire (voisinage de Moore, etc.).

hello,
Pour la performance ce que tu dois faire, le minimum vital;
- Definir une classe matrice basée sur un conteneur contigue
- Pour toutes les opérations d'algèbre utiliser la lib blas (libre à toi
de choisir la provenance, MKL intel, ACML amd, GOTO uni du texas)
ou bien utiliser boost/blas

example de base le plus simple possible produit de matrice de double (dgemm):

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

typename T::value_type*ad; typename T::value_type*bd; typename T::value_type*cd;   int m,n,k; int lda,ldb,ldc; double alpha(1.0), beta(1.0);   m =(int) T::ValueX; n =(int) T::ValueY; k =(int) T::ValueY;   lda = ldb = ldc = T::ValueX;   ad = new typename T::value_type[T::ValueX*T::ValueY]; bd = new typename T::value_type[T::ValueX*T::ValueY]; cd = new typename T::value_type[T::ValueX*T::ValueY];   memset((void*)cd,0,T::ValueX*T::ValueY*sizeof(typename T::value_type));   for(int i(0); i< T::ValueX*T::ValueY ; ++i){ ad[i] = Rd(); bd[i] = Rd(); }   TimerPTH t1("blas"); t1.begin(); dgemm("N","N", &m, &n, &k, &alpha, ad, &lda, bd, &ldb, &beta, cd, &ldc); t1.end();   delete [] ad; delete [] bd; delete [] cd; }

---

bonsoirs,
moi j'explore la librairie VXL qui contient la bibliothèque VNL du calcule numérique, te c'est je dirai mieux que MATLAB en traitement (relativement) des matrices. C'est très intéressant.

ta aussi la bibliothèque armadillo qui a priori prêtent être mieux que Matlab mais que je n'ai pas encore tester.

bonne courage

Merci pour ces retours,
Je regarde avec détails ces packages.

Gian

Dommage, Matlab est quand même fait pour ça ... peux-t-on vraiment espérer faire mieux ? :zoubi:


Je t'invite à consulter le paragraphe Alternatives - si tu ne l'as pas déjà fait - de la page Wikipedia de Matlab on te cite quelques bibliothèques qui peuvent s'interfacer en C/C++

Si tes matrices sont grandes, que tes traitements sont indépendants et que tu exécutes ton calcul sur du multi-coeur, tu peux envisager de paralléliser tes calculs avec des threads (peux-être cela se fait-il aussi sous Matlab ?).

On peut espérer faire mieux si un prog Matlab contient un grand nombre de boucles imbriquées non réductibles à du traitement matriciel (ce qui est mon cas).
Mais une seule facon d'être sur, implémenter le code! :)

Quelques questions supplémentaires : Tes matrices ont-elles une structure particulière (creuses ? Triangulaires ? Diagonales ? Autre ?). Est-ce que les travaux sur les différentes données sont assez indépendants les uns des autres, ou bien est-ce que tout agit sur tout se croisant dans tous les sens (si tu as un pipeline, peut-être une bonne solution est de regarder du côté de ton GPU, mais je ne maîtrise pas ce domaine).

De ce que tu dis de ton problème (éléments entiers, voisinage...), je vois plus quelque-chose du côté traitement d'image que du côté matriciel au sens mathématique du terme. Si je me trompe, eigen est une bibliothèque de matrice dont j'ai entendu parler.

En tout cas, je pense que quasiment tout sera préférable à une solution à base de matrice [n][n] ou int** matrice :)

Eh bien merci pour ces retours!
Mes matrices sont communes (matrices carrées de réels), peut-être l'une d'entre elle est creuse, mais les autres non.
Les travaux sur les données sont assez indépendant les uns des autres.

Pour l'instant mon choix se porte sur Armadillo, en espérant que ce soit assez facile à utiliser... (je suis novice en C++). :]