matrices creuses, CSR

Malgré son coût d’insertion en $O(1)$ et sa simplicité, le format COO vu précédemment présente certains inconvenients ; c’est un format non trié, ce qui implique un coût important pour l’accès à un élément, et une efficacité réduite pour les opérations d’algèbre linéaire. Nous allons donc introduire un autre format de stockage pour pallier à ces inconvenients, le format CSR (Compressed Sparse Row).

Comme son nom l’indique, un premier avantage du format CSR vient du fait que le tableau row des indices de ligne est compressé, ce qui réduit la place mémoire occupée par la matrice. De plus, c’est un format trié, ce qui permet l’accès à un élément en $O(1)$. Cela rend également le format plus performant à l’utilisation, pour le produit matrice-vecteur par exemple.

Dans le format CSR, on va retrouver les trois tableaux row, col et val. Les tableaux col et val sont similaires au format COO, mais ordonnés par ligne. La différence vient du format du tableau row : il est de taille $n+1$ (où $n$ est le nombre de lignes de la matrice), et row[i] stocke l’indice de position, dans col et val, du premier élément non-nul de la ligne i.
row[n] sera égal au nombre total d’éléments non-nuls de la matrice, et row[i+1] - row[i] sera égal au nombre de coefficients non-nuls de la ligne i.

L’exemple ci-dessous illustre le format CSR :

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

La matrice $A$ sera stockée au format CSR comme :

En général, le format COO est utilisé lors de la construction de la matrice, durant l’assemblage dans la méthode des éléments finis par exemple, et le format CSR est préféré une fois la matrice assemblée, lors de la résolution du système linéaire par une méthode itérative par exemple. Nous allons donc proposer dans notre classe matrice CSR un constructeur prenant en paramètre une matrice au format COO, qui effectuera la conversion au format CSR.

Votre classe implémentant les matrices CSR 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 trois tableaux row, col et val et qui copiera les données correspondantes, à des fins de test
• le constructeur par recopie
• un constructeur prenant en paramètre une matrice au format COO, qui convertira la matrice au format CSR
• l’opérateur d’affectation =
• les méthodes NbRow et NbCol qui retournent le nombre de lignes (resp. de colonnes)
• l’operateur () qui retourne le coefficient (j,k)
• l’opérateur * qui retourne le résultat du produit de la matrice avec un vecteur

Vous pourrez tester votre implémentation du format CSR avec l’algorithme MinRes écrit précédemment, en le modifiant pour qu’il prenne en paramètre une matrice au format CSR.
Une manière de procéder est de modifier la fonction minres en la déclarant comme fonction template. En passant le type de la matrice en paramètre template, la fonction minres pourra alors prendre en paramètre une instance de n’importe quelle classe de matrice que vous aurez préalablement définie, pourvu que celle-ci implémente l’opérateur * pour le produit matrice-vecteur.
Pour ce faire, vous pourrez modifier le prototype de la fonction minres en la déclarant comme fonction template, comme ceci :

template <class matrix>
std::vector<double> minres(const matrix& A, const std::vector<double>& b, double eps);