Solveurs linéaires denses et creux
ALGLIB, une bibliothèque numérique open source gratuite et commerciale, offre l'une des meilleures suites open source de solveurs d'équations linéaires denses et creuses. ALGLIB est disponible dans plusieurs langages de programmation, notamment C++, C#, Java et Python.
La bibliothèque prend en charge différents types de problèmes et de solveurs : denses et creux, asymétriques et symétriques, directs et itératifs. Les éditions gratuites et commerciales d'ALGLIB sont toutes deux évolutives et peuvent traiter des problèmes comportant des millions de variables.
Langages de programmation pris en charge
ALGLIB prend en charge de nombreux langages de programmation, notamment C++, C#, Java, Python et autres :
- Version C++ : Bibliothèque hautement optimisée, portable et autonome (x86/x64/ARM ; compatible avec Windows, Linux et les systèmes POSIX).
- Version C# : API C# unifiée pour deux architectures : une implémentation C# entièrement managée et un noyau de calcul natif haute performance écrit en C.
- Java, Python et autres langages : Interface pour un noyau de calcul natif haute performance écrit en C. Intégration transparente avec le langage de programmation cible.
L'une des caractéristiques distinctives d'ALGLIB est qu'elle offre la même API dans tous les langages de programmation. Ceci est rendu possible grâce à notre technologie exclusive de traduction automatique du code et de génération d'enveloppes.
Problèmes et solutions
Solutions denses
Les équations linéaires denses sont traditionnellement résolues par des solveurs directs (factorisant la matrice du système pour trouver une solution). Le sous-package `directdensesolvers` d'ALGLIB inclut de nombreux solveurs denses destinés à divers types de problèmes.
Ce sous-paquet est présenté plus en détail dans un article dédié ; nous nous contentons ici de décrire brièvement les types de problèmes pris en charge :
- Systèmes réels et complexes non symétriques. Le cas le plus général, généralement résolu par décomposition LU et, éventuellement, par raffinement itératif.
- Systèmes symétriques/hermitiens définis positifs. Un cas particulier important, résolu par décomposition de Cholesky.
- Problèmes des moindres carrés linéaires. Résolus par décomposition en valeurs singulières (SVD).
L'entrée du manuel de référence ALGLIB pour le sous-paquet (directdensesolvers) comprend plusieurs exemples dans tous les langages de programmation pris en charge par ALGLIB.
Solveurs itératifs pour matrices creuses
Les méthodes itératives constituent une approche courante pour la résolution de grands systèmes d'équations linéaires creux. Elles présentent généralement des besoins en mémoire modestes (souvent linéaires par rapport à la taille du problème) et des coûts d'itération prévisibles, indépendants de la structure creuse du système. Leur seul inconvénient réside dans leur forte dépendance au conditionnement du système.
ALGLIB inclut plusieurs solveurs itératifs pour matrices creuses, fournis par différents sous-paquets :
- La méthode du résidu minimum généralisé (GMRES) est probablement la méthode la plus répandue pour les équations linéaires générales (non symétriques). Ce solveur est fourni par le sous-package iterativesparse et prend en charge les modes de fonctionnement en mémoire (la matrice creuse A est fournie explicitement) et hors mémoire (la matrice creuse A est donnée comme produit matrice-vecteur). Le solveur GMRES est présenté plus en détail dans un article dédié. La méthode du gradient conjugué linéaire (CG) est couramment utilisée pour résoudre les systèmes d'équations linéaires symétriques définies positives. Le solveur CG est fourni par le sous-paquet lincg. L'article sur les solveurs itératifs pour matrices creuses apporte des informations complémentaires sur la méthode CG linéaire.
- La méthode LSQR, une méthode itérative puissante et précise pour les moindres carrés linéaires sur matrices creuses, est fournie par le sous-paquet linlsqr. Elle est traitée dans un article distinct.
Solveurs directs pour matrices creuses
Les solveurs directs (basés sur la factorisation) pour matrices creuses sont, d'une certaine manière, complémentaires aux solveurs itératifs. Leur temps d'exécution est indépendant du conditionnement du système à résoudre. Ils tendent également à trouver des solutions d'une très grande précision. En revanche, leur temps d'exécution et leurs besoins en mémoire dépendent fortement de la structure creuse de la matrice du système.
ALGLIB inclut plusieurs solveurs directs pour matrices creuses, fournis par le sous-paquet `directsparsesolvers` (voir le lien pour des exemples) :
- Le solveur direct pour matrices définies positives creuses, reposant sur la décomposition de Cholesky supernodale creuse avec ordre de degré minimal approximatif (AMD). Ce solveur est accessible via la fonction `sparsespdsolve`.
- Le solveur direct pour matrices non symétriques creuses, utilisant la décomposition LU creuse avec pivotage dynamique. Ce solveur est accessible via la fonction `sparsesolve`.
- Le solveur basé sur la méthode Skyline pour matrices creuses est conçu pour les matrices définies positives de faible épaisseur stockées au format SKS (Skyline Storage). Il constitue une alternative intéressante aux solveurs de Cholesky plus généraux lorsque la matrice présente une épaisseur très réduite. Ce solveur est accessible via la fonction `sparsespdsolvesks`.