Une matrice est généralement stockée sous la forme d’un tableau à deux dimensions. Chaque entrée du tableau représente un élément ai,j de la matrice et est accessible par les deux indices i et j. Par convention, i est l’indice de ligne, numéroté de haut en bas, et j est l’indice de colonne, numéroté de gauche à droite. Pour une matrice m × n, la quantité de mémoire nécessaire pour stocker la matrice dans ce format est proportionnelle à m × n (sans tenir compte du fait que les dimensions de la matrice doivent également être stockées).
Dans le cas d’une matrice clairsemée, des réductions substantielles des besoins en mémoire peuvent être réalisées en ne stockant que les entrées non nulles. Selon le nombre et la répartition des entrées non nulles, différentes structures de données peuvent être utilisées et permettre d’énormes économies de mémoire par rapport à l’approche de base. La contrepartie est que l’accès aux éléments individuels devient plus complexe et que des structures supplémentaires sont nécessaires pour pouvoir récupérer la matrice originale sans ambiguïté.
Les formats peuvent être divisés en deux groupes :
- Ceux qui supportent une modification efficace, tels que DOK (Dictionnaire de clés), LIL (Liste de listes), ou COO (Liste de coordonnées). Ceux-ci sont typiquement utilisés pour construire les matrices.
- Ceux qui supportent un accès efficace et des opérations matricielles, tels que CSR (Compressed Sparse Row) ou CSC (Compressed Sparse Column).
Dictionnaire de clés (DOK)Edition
DOK consiste en un dictionnaire qui fait correspondre des paires (ligne, colonne)-à la valeur des éléments. Les éléments qui sont manquants dans le dictionnaire sont pris pour zéro. Le format est bon pour la construction incrémentale d’une matrice éparse dans un ordre aléatoire, mais mauvais pour l’itération sur des valeurs non nulles dans un ordre lexicographique. On construit généralement une matrice dans ce format, puis on la convertit dans un autre format plus efficace pour le traitement.
Liste de listes (LIL)Edit
LIL stocke une liste par ligne, chaque entrée contenant l’indice de la colonne et la valeur. Typiquement, ces entrées sont conservées triées par index de colonne pour une recherche plus rapide. C’est un autre format bon pour la construction incrémentale de matrices.
Liste de coordonnées (COO)Edit
COO stocke une liste de tuples (ligne, colonne, valeur). Idéalement, les entrées sont triées d’abord par l’indice de ligne, puis par l’indice de colonne, pour améliorer les temps d’accès aléatoires. C’est un autre format qui est bon pour la construction incrémentale de matrices.
Rangée clairsemée comprimée (CSR, CRS ou format Yale)
La rangée clairsemée comprimée (CSR) ou le stockage de rangée comprimée (CRS) ou le format Yale représente une matrice M par trois tableaux (unidimensionnels), qui contiennent respectivement les valeurs non nulles, les étendues des rangées, et les indices de colonne. Il est similaire au format COO, mais compresse les indices des lignes, d’où son nom. Ce format permet un accès rapide aux rangées et aux multiplications matrice-vecteur (Mx). Le format CSR est utilisé depuis au moins le milieu des années 1960, la première description complète apparaissant en 1967.
Le format CSR stocke une matrice m × n clairsemée M sous forme de rangée en utilisant trois tableaux (unidimensionnels) (V, COL_INDEX, ROW_INDEX). Soit NNZ dénote le nombre d’entrées non nulles dans M. (Notez que les indices basés sur zéro seront utilisés ici.)
- Les tableaux V et COL_INDEX sont de longueur NNZ, et contiennent les valeurs non nulles et les indices de colonne de ces valeurs respectivement.
- Le tableau ROW_INDEX est de longueur m + 1 et code l’indice dans V et COL_INDEX où la ligne donnée commence. Le dernier élément est NNZ , c’est-à-dire , l’indice fictif dans V immédiatement après le dernier indice valide NNZ – 1.
Par exemple, la matrice
( 5 0 0 0 0 8 0 0 0 0 3 0 0 6 0 0 ) {\displaystyle {\begin{pmatrix}5&0&0&0\0\0&8&0&0\0&0&0&3&0\0&6&0&0\\\\end{pmatrix}}.
est une matrice 4 × 4 avec 4 éléments non nuls, donc
V = COL_INDEX = ROW_INDEX =
en supposant un langage à indexation nulle.
Pour extraire une ligne, nous définissons d’abord :
row_start = ROW_INDEX row_end = ROW_INDEX
Puis nous prenons des tranches de V et COL_INDEX en commençant par le début de la ligne et en finissant par la fin de la ligne.
Pour extraire la ligne 1 (la deuxième ligne) de cette matrice, nous définissons row_start=1 et row_end=2. Ensuite, nous faisons les tranches V = et COL_INDEX = . Nous savons maintenant que dans la ligne 1, nous avons un élément à la colonne 1 avec la valeur 8.
Dans ce cas, la représentation CSR contient 13 entrées, contre 16 dans la matrice originale. Le format CSR économise sur la mémoire seulement lorsque NNZ < (m (n – 1) – 1) / 2.Un autre exemple, la matrice
( 10 20 0 0 0 0 0 30 0 40 0 0 0 0 50 60 70 0 0 0 0 0 0 80 ) {\displaystyle {\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}}
est une matrice 4 × 6 (24 entrées) avec 8 éléments non nuls, donc
V = COL_INDEX = ROW_INDEX =
L’ensemble est stocké comme 21 entrées.
- ROW_INDEX divise le tableau V en lignes :
(10, 20) (30, 40) (50, 60, 70) (80); - COL_INDEX aligne les valeurs en colonnes :
(10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).
Notez que dans ce format, la première valeur de ROW_INDEX est toujours zéro et la dernière est toujours NNZ, elles sont donc en quelque sorte redondantes (bien que dans les langages de programmation où la longueur du tableau doit être explicitement stockée, NNZ ne serait pas redondant). Néanmoins, cela évite de devoir gérer un cas exceptionnel lors du calcul de la longueur de chaque ligne, car cela garantit que la formule ROW_INDEX – ROW_INDEX fonctionne pour n’importe quelle ligne i. De plus, le coût mémoire de ce stockage redondant est probablement insignifiant pour une matrice suffisamment grande.
Les (ancien et nouveau) formats de matrice clairsemée de Yale sont des instances du schéma CSR. L’ancien format Yale fonctionne exactement comme décrit ci-dessus, avec trois tableaux ; le nouveau format combine ROW_INDEX et COL_INDEX en un seul tableau et traite la diagonale de la matrice séparément.
Pour les matrices d’adjacence logique, le tableau de données peut être omis, car l’existence d’une entrée dans le tableau de lignes est suffisante pour modéliser une relation d’adjacence binaire.
Il est vraisemblablement connu sous le nom de format de Yale car il a été proposé dans le rapport Yale Sparse Matrix Package de 1977 du département d’informatique de l’université de Yale.
Colonne comprimée clairsemée (CSC ou CCS)Edition
CSC est similaire à CSR sauf que les valeurs sont lues d’abord par colonne, qu’un index de ligne est stocké pour chaque valeur et que des pointeurs de colonne sont stockés. Par exemple, CSC est (val, row_ind, col_ptr), où val est un tableau des valeurs (de haut en bas, puis de gauche à droite) non nulles de la matrice ; row_ind est les indices de ligne correspondant aux valeurs ; et, col_ptr est la liste des indices de val où chaque colonne commence. Le nom est basé sur le fait que les informations d’index de colonne sont compressées par rapport au format COO. On utilise généralement un autre format (LIL, DOK, COO) pour la construction. Ce format est efficace pour les opérations arithmétiques, le découpage en colonnes et les produits matrice-vecteur. Voir scipy.sparse.csc_matrix.C’est le format traditionnel pour spécifier une matrice éparse dans MATLAB (via la fonction sparse).
.