1. Formats COO et CSR

$\newcommand{\nnz}{\texttt{nnz}}$

Objectifs

• Comprendre les formats COO et CSR

Matrice Creuse ?

De nombreuses méthodes discrétisations mènent à la résolution de problème du type :

$$ A x=b, $$

où la matrice $A$ est creuse, c’est-à-dire que, majoritairement, les coefficients de $A$ sont nuls. Pour minimiser la mémoire occupée par la matrice, seuls les coefficients non-nuls sont stockés. Ceci permet également d’améliorer notablement les performances du produit matrice-vecteur, en passant d’une complexité de $O(N^2)$ à $O($nnz$)$ où nnz est le nombre de coefficients non-nuls (nnz = number of non-zeros).

Il existe plusieurs formats de matrices creuses. Parmi les plus connus et utilisés : les formats COO (COOrdinates) et CSR (Compressed Sparse Row ou CRS pour Compressed Row Storage).

Format COO

Principe

Relativement naturel et simple à comprendre et utiliser. La matrice est stockée sous la forme de trois tableaux row, col et val, tous trois de taille nnz et contenant respectivement l’indice ligne, colonne et le coefficient non nuls de la matrice. En d’autre termes, pour i = 0, …, (nnz-1), \begin{equation} \label{eq:coo} A(\texttt{row}[i],\texttt{col}[i]) = \texttt{val}[i]. \end{equation} L’avantage de ce format est la facilité d’implémentation et la possibilité d’ajouter des coefficients “à la volée”. En effet, les tableaux row, col et val n’ont pas besoin d’être triés selon l’ordre indices.

Prenons la matrice exemple suivante avec nnz=10 :

\begin{equation} \label{eq:matA} A= \begin{pmatrix} 3 & 0 & 0 & 2 & 1 \\\
0 & 0 & 5 & 8 & 0 \\\
0 & 1 & 2 & 0 & 0 \\\
0 & 0 & 9 & 0 & 0 \\\
0 & 0 & 10& 4 & 0 \end{pmatrix}. \end{equation}

Le stockage COO de cette matrice prendra alors la forme suivante :

Doublons

Le format COO peut autoriser les doublons, c’est-à-dire des coefficients ayant les mêmes indices ligne et colonne qu’un autre. En reprenant l’exemple ci-dessus et en divisant le dernier coefficient en deux, nous pourrions obtenir le stockage suivant :

Du COO au Dense

Pour reconstuire la matrice sous format dense, le pseudo-code ci-dessous fonctionnerait et autorise d’avoir une dupplication de coefficients (du fait du += ):

A = zeros(N,N)
for (i = 0; i < row.size(); i++)
  A(row[i], col[i]) = val[i]
end

Produit Matrice-Vecteur

Un pseudo code serait le suivant :

// y = A*x
y = zeros(n) // vecteur nul
for (i = 0; i < row.size(); i++)
  y[row[i]] += val[i] * x[col[i]]
end

Triplets

Plutôt que 3 tableaux, une matrice au format COO peut aussi être stockée sous forme d’un tableau de triplets (i,j,val), ce qui donnerait pour la matrice \eqref{eq:matA} :

Conclusion

Le format COO est très souple et permet de construire une matrice aisément, cependant il présente les défauts suivants :

• Deux adressages indirects sont nécessaires pour effectuer le produit matrice vecteur
• Les accès aux données ne sont pas a priori connus
• Absence de méthode rapide pour obtenir un terme de la matrice connaissant ses indices ligne et colonne

Dans la pratique, le format COO est souvent utilisée comme format “tampon” pour stocker la matrice au format CSR, bien plus efficace pour les opérations d’algèbre linéaire. Le stockage sous forme de triplets est alors le plus pratique.

Format CSR

Principe

Le format CSR est spécialisé dans les opérations d’algèbres linéaires et pallie les défauts du COO. Son nom vient du fait que le tableau row est compressé. Une matrice au format CSR est composée des deux tableaux col et val, comme pour le COO et ordonnés par “lignes”, et le tableau row est défini ainsi :

• Sa taille est fixée à n+1 (n=nombre de lignes de la matrice)
• row[i] est maintenant l’indice du premier élément non nul de la ligne i dans les tableaux col et val

Par exemple, le stockage CSR de la matrice \eqref{eq:matA} est :

Le tableau row est compressé par rapport au format COO puisque sa taille est maintenant de n+1, bien inférieure à nnz ! Sur une petite matrice, le gain mémoire est très faible, mais sur une matrice à plusieurs millions d’entrée, cette stratégie devient payante. D’autre part, l’absence de doublon de coefficients et le fait que les tableaux sont triés permettent d’améliorer significativement les opérations d’algèbres linéaires.

Du CSR au Dense

Le pseudo code pour reconstruire la matrice dense associé ressemblerait à ceci :

A = zeros(N,N)
for (i = 0; i < row.size() - 1; i++)
  for (j = row[i]; j < row[i+1]; j++)
    A(i, col[j]) = val[j]
  end
end

Produit Matrice - Vecteur

Le pseudo-code est le suivant

// y = A*x
y = zeros(row.size() - 1)
for (i = 0; i < row.size()-1; i++)
  for (j = row[i]; j < row[i+1]; j++)
    // Parcours des indices colonnes de la ligne i
    y[i] += val[j]*x[col[j]];
  end
end

Nous noterons que, cette fois-ci, les coefficients des vecteurs sont parcourus consécutivement.

Conclusion

Le format CSR est rigide : il est très coûteux d’ajouter des éléments dans la matrice. Ainsi et afin de ne pas perdre en efficacité, il est nécessaire de connaître à l’avance l’emplacement des coefficients non nuls de la matrice avant de la construire. En revanche, une fois construire, cette forme de stockage est très efficace.

Du COO au CSR

Principe

La souplesse du format COO permet de construire la matrice en ajoutant les triplets des coefficients (i,j,val) au fur et à mesure. Ensuite, une fois tous les triplets sauvegardés, ils sont triés (ou assemblés) et les doublons fusionnés. Il ne reste alors plus qu’à extraire les tableaux row, col et val du tableau de triplets et à compresser le vecteur row pour obtenir une matrice CSR.

Utilisation

En supposant les fonctions existantes, le pseudo-code suivant permet de passer d’une matrice A au format COO à une matrice B au format CSR :

MatriceCOO A(n) // COO
MatriceCSR B(n) // CSR
// Ajout des triplets
A.add(0,0,2.);
A.add(0,1,-1.1);
[...]
// Convertisseur en CSR
B = A.to_csr();