Matrice clairsemée - Sparse matrix

Exemple de matrice creuse
La matrice creuse ci-dessus ne contient que 9 éléments non nuls, avec 26 éléments nuls. Sa rareté est de 74% et sa densité est de 26%.
Une matrice creuse obtenue lors de la résolution d'un problème d'éléments finis en deux dimensions. Les éléments non nuls sont représentés en noir.

En analyse numérique et en calcul scientifique , une matrice creuse ou un tableau clairsemé est une matrice dans laquelle la plupart des éléments sont nuls. Il n'y a pas de définition stricte concernant la proportion d'éléments de valeur zéro pour qu'une matrice soit qualifiée de creuse, mais un critère commun est que le nombre d'éléments non nuls est à peu près égal au nombre de lignes ou de colonnes. En revanche, si la plupart des éléments sont non nuls, la matrice est considérée comme dense . Le nombre d'éléments de valeur zéro divisé par le nombre total d'éléments (par exemple, m × n pour une matrice m × n) est parfois appelé la rareté de la matrice.

Conceptuellement, la parcimonie correspond à des systèmes avec peu d'interactions par paires. Par exemple, considérons une ligne de billes reliées par des ressorts de l'une à l'autre : il s'agit d'un système clairsemé car seules les billes adjacentes sont couplées. En revanche, si une même ligne de billes avait des ressorts reliant chaque bille à toutes les autres billes, le système correspondrait à une matrice dense. Le concept de parcimonie est utile dans les domaines de la combinatoire et des applications tels que la théorie des réseaux et l'analyse numérique , qui ont généralement une faible densité de données ou de connexions significatives. De grandes matrices éparses apparaissent souvent dans les applications scientifiques ou d' ingénierie lors de la résolution d'équations aux dérivées partielles .

Lors du stockage et de la manipulation de matrices éparses sur un ordinateur , il est avantageux et souvent nécessaire d'utiliser des algorithmes et des structures de données spécialisés qui tirent parti de la structure éparse de la matrice. Des ordinateurs spécialisés ont été conçus pour les matrices creuses, car ils sont courants dans le domaine de l'apprentissage automatique. Les opérations utilisant des structures et des algorithmes de matrice dense standard sont lentes et inefficaces lorsqu'elles sont appliquées à de grandes matrices éparses, car le traitement et la mémoire sont gaspillés sur les zéros. Les données éparses sont par nature plus faciles à compresser et nécessitent donc beaucoup moins de stockage . Certaines matrices creuses de très grande taille sont impossibles à manipuler à l'aide d'algorithmes de matrice dense standard.

Stockage d'une matrice creuse

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 a i , j de la matrice et est accessible par les deux indices i et j . Classiquement, 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 creuse, des réductions substantielles des besoins en mémoire peuvent être réalisées en stockant uniquement les entrées non nulles. Selon le nombre et la distribution des entrées non nulles, différentes structures de données peuvent être utilisées et permettent de réaliser d'énormes économies de mémoire par rapport à l'approche de base. Le compromis 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 d'origine sans ambiguïté.

Les formats peuvent être divisés en deux groupes :

  • Ceux qui prennent en charge une modification efficace, tels que DOK (Dictionnaire de clés), LIL (Liste de listes) ou COO (Liste de coordonnées). Ceux-ci sont généralement utilisés pour construire les matrices.
  • Ceux qui prennent en charge un accès efficace et des opérations matricielles, telles que CSR (Compressed Sparse Row) ou CSC (Compressed Sparse Column).

Dictionnaire des clés (DOK)

DOK consiste en un dictionnaire qui mappe (ligne, colonne) - les paires à la valeur des éléments. Les éléments manquants dans le dictionnaire sont considérés comme étant nuls. Le format est bon pour la construction incrémentielle d'une matrice clairsemée dans un ordre aléatoire, mais médiocre pour l'itération sur des valeurs non nulles dans l'ordre lexicographique. On construit généralement une matrice dans ce format, puis la convertit en un autre format plus efficace pour le traitement.

Liste des listes (LIL)

LIL stocke une liste par ligne, chaque entrée contenant l'index de colonne et la valeur. En règle générale, ces entrées sont triées par index de colonne pour une recherche plus rapide. Il s'agit d'un autre format adapté à la construction de matrices incrémentielles.

Liste de coordonnées (COO)

COO stocke une liste de tuples (ligne, colonne, valeur) . Idéalement, les entrées sont triées d'abord par index de ligne, puis par index de colonne, pour améliorer les temps d'accès aléatoire. Il s'agit d'un autre format qui convient à la construction de matrices incrémentielles.

Ligne creuse compressée (format CSR, CRS ou Yale)

Le format compressé de lignes creuses (CSR) ou de stockage de lignes compressées (CRS) ou le format Yale représente une matrice M par trois tableaux (unidimensionnels), qui contiennent respectivement des valeurs non nulles, l'étendue des lignes et des indices de colonne. Il est similaire à COO, mais compresse les indices de ligne, d'où le nom. Ce format permet un accès rapide aux lignes et des multiplications matrice-vecteur ( M x ). 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 creuse m × n M sous forme de lignes en utilisant trois tableaux ( unidimensionnels) (V, COL_INDEX, ROW_INDEX) . Soit NNZ le nombre d'entrées non nulles dans M . (Notez que les indices de base zéro doivent être utilisés ici.)

  • Les tableaux V et COL_INDEX sont de longueur NNZ , et contiennent respectivement les valeurs non nulles et les indices de colonne de ces valeurs.
  • Le tableau ROW_INDEX est de longueur m + 1 et code l'index en V et COL_INDEX où commence la ligne donnée. Cela équivaut à ROW_INDEX[j] encodant le nombre total de non-zéros au-dessus de la ligne j . 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

est une matrice 4 × 4 avec 4 éléments non nuls, donc

   V         = [ 5 8 3 6 ]
   COL_INDEX = [ 0 1 2 1 ]
   ROW_INDEX = [ 0 1 2 3 4 ] 

en supposant une langue à index zéro.

Pour extraire une ligne, on définit d'abord :

   row_start = ROW_INDEX[row]
   row_end   = ROW_INDEX[row + 1]

Ensuite, nous prenons des tranches de V et COL_INDEX en commençant à row_start et se terminant à row_end.

Pour extraire la ligne 1 (la deuxième ligne) de cette matrice, nous définissons row_start=1et row_end=2. Ensuite, nous faisons les tranches V[1:2] = [8]et COL_INDEX[1:2] = [1]. 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 d'origine. Le format CSR n'enregistre en mémoire que lorsque NNZ < ( m ( n − 1) − 1) / 2 . Autre exemple, la matrice

est une matrice 4 × 6 (24 entrées) avec 8 éléments non nuls, donc

   V         = [ 10 20 30 40 50 60 70 80 ]
   COL_INDEX = [  0  1  1  3  2  3  4  5 ]   
   ROW_INDEX = [  0  2  4  7  8 ]


Le tout est stocké sous forme de 21 entrées.

  • ROW_INDEX divise le tableau V en lignes : (10, 20) (30, 40) (50, 60, 70) (80);
  • COL_INDEX aligne les valeurs dans les 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 , donc elles sont 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 d'avoir à gérer un cas exceptionnel lors du calcul de la longueur de chaque ligne, car cela garantit que la formule ROW_INDEX[ i + 1] − ROW_INDEX[ i ] fonctionne pour toute ligne i . De plus, le coût mémoire de ce stockage redondant est vraisemblablement insignifiant pour une matrice suffisamment grande.

Les (anciens et nouveaux) formats de matrice creuse 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 dans un seul tableau et gère 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 probablement connu sous le nom de format Yale car il a été proposé dans le rapport de 1977 sur le Yale Sparse Matrix Package du Département d'informatique de l'Université de Yale.

Colonne creuse compressée (CSC ou CCS)

CSC est similaire à CSR sauf que les valeurs sont d'abord lues par colonne, un index de ligne est stocké pour chaque valeur et des pointeurs de colonne sont stockés. Par exemple, CSC est (val, row_ind, col_ptr) , où val est un tableau des valeurs non nulles (de haut en bas, puis de gauche à droite) de la matrice ; row_ind est les indices de ligne correspondant aux valeurs ; et col_ptr est la liste des index 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 de colonnes et les produits matrice-vecteur. Voir scipy.sparse.csc_matrix . C'est le format traditionnel pour spécifier une matrice creuse dans MATLAB (via la sparsefonction).


Structure spéciale

bagué

Un type spécial important de matrices creuses est la matrice de bande , définie comme suit. La bande passante inférieure d'une matrice A est le plus petit nombre p tel que l'entrée a i , j s'annule chaque fois que i > j + p . De même, la bande passante supérieure est le plus petit nombre p tel que a i , j = 0 chaque fois que i < jp ( Golub & Van Loan 1996 , §1.2.1). Par exemple, une matrice tridiagonale a une bande passante inférieure 1 et une bande passante supérieure 1 . Comme autre exemple, la matrice creuse suivante a une bande passante inférieure et supérieure toutes deux égales à 3. Notez que les zéros sont représentés par des points pour plus de clarté.

Les matrices avec des bandes passantes supérieure et inférieure raisonnablement petites sont appelées matrices de bande et se prêtent souvent à des algorithmes plus simples que les matrices creuses générales ; ou l'on peut parfois appliquer des algorithmes matriciels denses et gagner en efficacité simplement en bouclant sur un nombre réduit d'indices.

En réarrangeant les lignes et les colonnes d'une matrice A , il peut être possible d'obtenir une matrice A ' avec une largeur de bande inférieure. Un certain nombre d'algorithmes sont conçus pour minimiser la bande passante .

Diagonale

Une structure très efficace pour un cas extrême de matrices de bandes, la matrice diagonale , consiste à stocker uniquement les entrées de la diagonale principale sous forme de tableau à une dimension , de sorte qu'une matrice diagonale n × n ne nécessite que n entrées.

Symétrique

Une matrice creuse symétrique apparaît comme la matrice d'adjacence d'un graphe non orienté ; il peut être stocké efficacement sous forme de liste de contiguïté .

Diagonale de bloc

Une matrice bloc-diagonale se compose de sous-matrices le long de ses blocs diagonaux. Une matrice bloc-diagonale A a la forme

A k est une matrice carrée pour tout k = 1, ..., n .

Réduire le remplissage

Le remplissage d'une matrice sont les entrées qui passent d'un zéro initial à une valeur non nulle lors de l'exécution d'un algorithme. Pour réduire les besoins en mémoire et le nombre d'opérations arithmétiques utilisées au cours d'un algorithme, il est utile de minimiser le remplissage en changeant de ligne et de colonne dans la matrice. La décomposition symbolique de Cholesky peut être utilisée pour calculer le pire remplissage possible avant de faire la véritable décomposition de Cholesky .

Il existe d'autres méthodes que la décomposition de Cholesky en usage. Les méthodes d'orthogonalisation (telles que la factorisation QR) sont courantes, par exemple, lors de la résolution de problèmes par la méthode des moindres carrés. Alors que le remplissage théorique est toujours le même, en termes pratiques, les "faux non nuls" peuvent être différents pour différentes méthodes. Et les versions symboliques de ces algorithmes peuvent être utilisées de la même manière que le Cholesky symbolique pour calculer le pire des cas.

Résolution d'équations matricielles creuses

Des méthodes itératives et directes existent pour la résolution de matrices creuses.

Les méthodes itératives, telles que la méthode du gradient conjugué et le GMRES, utilisent des calculs rapides de produits matrice-vecteur , où la matrice est clairsemée. L'utilisation de préconditionneurs peut accélérer considérablement la convergence de telles méthodes itératives.

Logiciel

De nombreuses bibliothèques logicielles prennent en charge les matrices creuses et fournissent des solveurs pour les équations matricielles creuses. Les éléments suivants sont open source :

  • SuiteSparse , une suite d'algorithmes matriciels clairsemés, orientée vers la solution directe de systèmes linéaires clairsemés.
  • PETSc , une grande bibliothèque C, contenant de nombreux solveurs matriciels différents pour une variété de formats de stockage matriciel.
  • Trilinos , une grande bibliothèque C++, avec des sous-bibliothèques dédiées au stockage de matrices denses et clairsemées et à la résolution des systèmes linéaires correspondants.
  • Eigen3 est une bibliothèque C++ qui contient plusieurs solveurs de matrices creuses. Cependant, aucun d'entre eux n'est parallélisé .
  • MUMPS ( MU ltifrontal M assively P arallel clairsemée directe S olver), écrit en Fortran90, est un solveur frontal .
  • DUNE , une bibliothèque d'éléments finis qui possède également une sous-bibliothèque pour les systèmes linéaires creux et leur solution.
  • PaStix .
  • SuperLU .
  • Armadillo fournit un wrapper C++ convivial pour BLAS et LAPACK.
  • SciPy prend en charge plusieurs formats de matrices creuses, d'algèbre linéaire et de solveurs.
  • SPArse Matrix (spam) Package R et Python pour les matrices creuses .
  • Wolfram Language Tools pour la gestion des tableaux clairsemés
  • ALGLIB est une bibliothèque C++ et C# avec un support d'algèbre linéaire clairsemé
  • Bibliothèque ARPACK Fortran 77 pour la diagonalisation et la manipulation de matrices creuses , utilisant l'algorithme d'Arnoldi
  • SPARSE Reference (ancien) package NIST pour la diagonalisation de matrice creuse (réelle ou complexe)
  • Bibliothèque SLEPc pour la résolution de systèmes linéaires à grande échelle et de matrices creuses
  • Sympiler , un générateur de code et une bibliothèque spécifiques à un domaine pour résoudre les problèmes de systèmes linéaires et de programmation quadratique.
  • Scikit-learn Un package Python pour l'analyse de données, y compris les matrices creuses.

Histoire

Le terme matrice clairsemée a peut-être été inventé par Harry Markowitz qui a lancé des travaux de pionnier mais a ensuite quitté le terrain.

Voir également

Remarques

Les références


Lectures complémentaires

  1. ^ Saad, Yousef (2003). Méthodes itératives pour les systèmes linéaires creux . SIAM.