MĂ©thodes Matrix-free
En mathématiques appliquées, une méthode dite matrix-free (sans matrice) est un algorithme qui permet de résoudre un système d'équations linéaires ou un problème aux valeurs propres sans avoir besoin de stocker explicitement en mémoire les coefficients de la matrice, mais en accédant implicitement à la matrice par des évaluations de produits matrice-vecteur[1]. Lorsque la matrice du système linéaire à étudier est de très grande taille, on préfère utiliser une méthode matrix-free qui permet d'économiser le stockage en mémoire et la manipulation (lecture / écriture) qui sont souvent des opérations très coûteuses en temps de calcul (même avec l'utilisation de méthodes pour matrices creuses). Ces méthodes réalisent une sorte de compromis;on remplace des accès mémoire aux coefficients de la matrice par du calcul (petit produit matrice-vecteur) au profit de l’efficacité globale de l'implantation algorithmique. De nombreuses méthodes itératives en algèbre linéaire permettent une implémentation matrix-free, notamment :
- la méthode de la puissance itérée,
- l'algorithme de Lanczos[2],
- Méthode du gradient conjugué préconditionné par bloc localement optimal (LOBPCG)[3],
- l'algorithme de récurrence des coordonnées de Wiedemann[4],
- la méthode du gradient conjugué[5].
Il existe de nombreuses implantations parallèles de ces algorithmes pour les calculateurs à mémoire distribuée[6] .
Ces méthodes sont par exemple utilisées dans la résolution d'équations linéaires résultant de la discrétisation des équations d'Euler (équations aux dérivées partielles) en dynamique des fluides numérique. La méthode du gradient conjugué matrix-free a été appliquée par exemple à la résolution par la méthode des éléments finis de problèmes élasto-plastiques non linéaire[7]. La résolution de ces équations nécessite le calcul d'une matrice jacobienne qui est coûteux en temps de calcul et en stockage en mémoire. Afin de supprimer le besoin de calculer ce jacobien, on forme un produit matrice-vecteur à la place. Manipuler et calculer ces produits matrice-vecteur est plus facile que de travailler avec une matrice de grande taille.
Notes et références
- (en) Amy N. Langville et Carl D. Meyer, Google's PageRank and beyond: the science of search engine rankings, Princeton University Press, (ISBN 978-0-691-12202-1), p. 40
- (en) Don Coppersmith, « Solving linear equations over GF(2): Block Lanczos algorithm », Linear Algebra and its Applications, vol. 192,‎ , p. 33–60 (DOI 10.1016/0024-3795(93)90235-G
) - (en) Knyazev, « Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method », SIAM Journal on Scientific Computing, vol. 23, no 2,‎ , p. 517–541 (DOI 10.1137/S1064827500366124)
- (en) D. Wiedemann, « Solving sparse linear equations over finite fields », IEEE Transactions on Information Theory, vol. 32,‎ , p. 54–62 (DOI 10.1109/TIT.1986.1057137, lire en ligne)
- (en) B. A. Lamacchia et A. M. Odlyzko, Advances in Cryptology-CRYPT0' 90, vol. 537, coll. « Lecture Notes in Computer Science », , 109 p. (ISBN 978-3-540-54508-8, DOI 10.1007/3-540-38424-3_8 ), « Solving Large Sparse Linear Systems Over Finite Fields »
- (en) E. Kaltofen et A. Lobo, « Distributed Matrix-Free Solution of Large Sparse Linear Systems over Finite Fields », Algorithmica, vol. 24, nos 3–4,‎ , p. 311–348 (DOI 10.1007/PL00008266, CiteSeerx 10.1.1.17.7470)
- (en) Prabhune et Krishnan, « A fast matrix-free elasto-plastic solver for predicting residual stresses in additive manufacturing », Computer Aided Design, vol. 123,‎ , p. 102829 (DOI 10.1016/j.cad.2020.102829, lire en ligne, consulté le )