Algèbre linéaire creuse
La bibliothèque d'analyse numérique ALGLIB offre un ensemble complet de fonctions pour matrices creuses, disponibles en C++, C#, Java et plusieurs autres langages de programmation. Elle prend en charge divers formats de stockage de matrices creuses, les fonctions BLAS creuses (GEMV creuse et ses variantes), les factorisations (Cholesky creuse, LDLT et LU), ainsi que les solveurs linéaires creux directs et itératifs.
ALGLIB est une bibliothèque à double licence, disponible en version gratuite et en version commerciale. La version gratuite, entièrement fonctionnelle, est idéale pour la recherche académique ou les petits projets non commerciaux. La version commerciale est destinée aux utilisateurs recherchant des performances élevées, un support prioritaire ou la possibilité d'utiliser la bibliothèque dans des applications commerciales.
Les premiers pas
Formats d'entreposage et initialisation des matrices creuses
ALGLIB prend en charge plusieurs formats d'entreposage de matrices creuses, optimisés pour différents types de structures creuses et d'opérations :
| Format | Description |
|---|---|
| CRS (Compressed Row Storage) | Format optimisé pour les opérations d'algèbre linéaire sur les matrices creuses. Ce format stocke efficacement les matrices présentant n'importe quel type de structure creuse. Cependant, son initialisation est limitée (les matrices sont toujours initialisées de haut en bas et de gauche à droite) et il est impossible de modifier la structure creuse à la volée. |
| HTS (Hash Table Storage) | Format optimisé pour une initialisation facile. Les éléments de la matrice sont entreposés dans une table de hachage, ce qui permet d'ajouter ou de supprimer facilement des éléments. Toutefois, la plupart des opérations (y compris l'algèbre linéaire) n'étant pas prises en charge par ce format, il est nécessaire de convertir le format HTS en CRS (de préférence) pour pouvoir utiliser une matrice creuse. |
| SKS (Skyline Storage) | Format optimisé pour les matrices légères, notamment celles à faible bande passante. |
Nous recommandons d'utiliser d'abord le format HTS en raison de sa mise en ouvre simple et pratique, puis de procéder à une conversion au format CRS dès que possible, car il offre les meilleures performances.
Utilisation des matrices creuses
Les fonctionnalités de base relatives aux matrices creuses sont fournies par un sous-paquet dédié des matrices creuses au sein du paquet LinAlg. Ces fonctionnalités comprennent :
- Un ensemble complet de fonctions d'initialisation de matrices permettant de créer des matrices aux formats CRS, HTS ou SKS, soit à partir de zéro, soit en réutilisant de la mémoire précédemment allouée.
- Un ensemble de fonctions de conversion permettant d'effectuer des conversions sur place ou hors place entre différents formats de stockage de matrices creuses.
- Des fonctions supplémentaires, telles que la transposition, la permutation, la sérialisation, l'énumération, etc.
Le manuel de référence d'ALGLIB contient plusieurs exemples d'initialisation et d'utilisation de matrices creuses, notamment `sparse_d_1` et `sparse_d_crs`.
Fonctions d'algèbre linéaire creuses
BLAS creux
Le sous-paquet «sparse» du paquet LinAlg propose un ensemble complet de fonctions BLAS creuses rapides et efficaces, notamment :
- Produits matrice-matrice creux-dense de différents types, tels que (S·A et S'·A)
- Produits matrice-vecteur, tels que S·x, S'·x et x'·S·x
- Produits triangulaires et solveurs, c'est-à-dire des produits de la forme S·x et S-1·x, où S est une matrice triangulaire creuse
L'implémentation d'algèbre linéaire creuse gère efficacement les matrices creuses de toutes tailles, des plus petites aux plus grandes. Avec suffisamment de RAM, il est possible de traiter des matrices contenant plus d'un milliard d'éléments.
Factorisations de Cholesky creuses et autres factorisations triangulaires
La factorisation triangulaire creuse est une composante essentielle de tout paquet de matrices creuses. Le sous-paquet trfac propose les factorisations creuses suivantes :
- Décomposition de Cholesky creuse (supernodale) avec ordre AMD (Approximate Minimum Degree), capable de traiter des matrices de plus d'un million de lignes. ALGLIB offre une API flexible et riche en fonctionnalités permettant d'effectuer une factorisation unique ou des factorisations multiples efficaces avec les mêmes motifs de creux (approche «analyser»/«factoriser»).
- Décomposition LU creuse avec pivotage complet, par lignes ou sans pivotage.
La version commerciale du solveur de Cholesky pour matrices creuses prend en charge le multi-processus léger. Cependant, le gain de vitesse précis dépend fortement de la structure creuse de la matrice à factoriser.
Solveurs linéaires directs pour systèmes creux
Un solveur linéaire direct utilise une factorisation triangulaire (creuse) pour résoudre un système linéaire. ALGLIB propose plusieurs solveurs directs pour systèmes creux dans son sous-quet `directsparsesolvers` :
- Un solveur creux basé sur la méthode de Cholesky pour les systèmes symétriques définis positifs
- Un solveur creux basé sur la méthode LU pour les systèmes linéaires généraux (non symétriques)
Les solveurs directs offrent généralement les résultats les plus précis, avec une précision d'au moins six chiffres (et souvent bien plus). Leur principal inconvénient réside dans leurs besoins imprévisibles en mémoire et en temps : il est difficile de prévoir à l'avance la quantité de mémoire et le temps nécessaires à une factorisation.
Solveurs itératifs linéaires pour matrices creuses
Un solveur itératif linéaire résout généralement un système linéaire par une suite de produits matrice-vecteur. Les solveurs itératifs pour matrices creuses sont fournis par les sous-packages iterativesparse, linlsqr et lincg, incluant les algorithmes suivants :
| Algorithme | Description |
|---|---|
| GMRES | Un algorithme bien connu pour les systèmes généraux creux (non symétriques), disponible en versions mémoire et hors mémoire. |
| LSQR | Un algorithme pour la méthode des moindres carrés linéaires sur matrices creuses. Conçu initialement pour les problèmes de moindres carrés avec des matrices rectangulaires M×N, il peut également être utilisé pour résoudre des problèmes avec des matrices carrées. |
| CG | Un algorithme bien connu pour les systèmes symétriques définis positifs. |
Comparativement aux solveurs directs, les solveurs itératifs ont généralement des besoins en mémoire beaucoup plus prévisibles, mais une précision beaucoup moins prévisible. Ils n'allouent généralement qu'une quantité limitée de mémoire supplémentaire, bornée par O(max(M,N)), qui peut être facilement prédite à l'avance. Ce qui est difficile à prévoir, c'est le nombre d'itérations nécessaires pour converger vers une précision de 6 chiffres.
Résolution de valeurs propres pour matrices creuses
Les problèmes de valeurs propres avec des matrices creuses constituent un sous-ensemble important de l'algèbre linéaire. Le sous-paquet evd inclut un solveur de valeurs propres par itération de sous-espace permettant de calculer plusieurs valeurs propres/vecteurs propres de premier ordre d'une grande matrice creuse.
Autres fonctions prenant en compte la sparsité
De nombreux autres algorithmes d'ALGLIB peuvent exploiter la sparsité de leurs entrées, notamment :
- Les solveurs de programmation linéaire et quadratique, fortement optimisés pour les problèmes à données éparses.
- Les solveurs de programmation non linéaire à grande échelle, dont les performances sont nettement supérieures lorsque les contraintes sont éparses.