matrices creuses, COO

Nous verrons que la méthode des éléments finis amène à la construction d’une matrice creuse, c’est à dire avec un nombre important de coefficients nuls. Aussi, afin de minimiser la place mémoire occupée par la matrice, on va stocker uniquement les coefficients non nuls.

Il existe plusieurs formats de stockage des matrices creuses ; on se propose ici d’écrire une classe pour les matrices creuses implémentant le format COO (COOrdinates).

Ce format est assez simple : on stocke la matrice sous la forme de trois tableaux, row, col et val, qui contiennent respectivement l’indice de ligne, l’indice de colonne et la valeur des coefficients non nuls.

Un avantage du format COO est que le coût de l’insertion d’un nouvel élément est en $O(1)$ ; il suffit d’ajouter les indices et la valeur du nouveau coefficient à la fin des tableaux row, col et val, par exemple en utilisant push_back (fonction membre de la classe vector).

Prenons l’exemple ci-dessous afin d’illustrer le format COO :

$$ \begin{equation} A= \begin{pmatrix} 2 & 6 & 0 & 0 \\\ 0 & 1 & 0 & 0 \\\ 0 & 0 & 5 & 0 \\\ 0 & 3 & 0 & 0 \\ \end{pmatrix} \end{equation} $$

La matrice $A$ peut être stockée au format COO comme :

Votre classe implémentant les matrices COO aura comme données membres deux entiers représentant la taille de la matrice, ainsi que deux std::vector<int> et un std::vector<double> représentant les tableaux row, col et val. Elle définira au moins :

• un constructeur prenant en paramètre deux entiers représentant la taille, qui initialisera la matrice
• le constructeur par recopie
• l’opérateur d’affectation =
• les méthodes NbRow et NbCol qui retournent le nombre de lignes (resp. de colonnes)
• la méthode Insert qui insère un nouveau coefficient dans la matrice
• l’operateur () qui retourne le coefficient (j,k)
• l’opérateur * qui retourne le résultat du produit de la matrice avec un vecteur