Residual-based Chebyshev filtered subspace iteration for sparse Hermitian eigenvalue problems tolerant to inexact matrix-vector products

Cet article présente R-ChFSI, une reformulation résiduelle de l'itération de sous-espace filtrée par Chebyshev qui assure une convergence robuste et des accélérations significatives sur GPU pour les problèmes de valeurs propres hermitiennes creuses, même en présence de produits matrice-vecteur inexacts, d'inverses approchés et d'arithmétique de faible précision.

L'essentiel

Le Problème : Trouver les étoiles les plus brillantes dans une tempête

Imaginez que vous êtes un capitaine de navire (un scientifique) qui doit naviguer à travers un océan immense et sombre (un système mathématique complexe, comme la structure d'un matériau). Votre but n'est pas de cartographier tout l'océan, mais de trouver les quelques étoiles les plus brillantes (les solutions mathématiques appelées "valeurs propres") qui vous guideront.

Ces étoiles sont cachées dans une tempête de données. Pour les trouver, les scientifiques utilisent une méthode appelée ChFSI (Itération de sous-espace filtrée par Chebyshev).

Comment fonctionne la méthode classique (ChFSI) ?
C'est comme si vous utilisiez un filtre à café très sophistiqué pour séparer le café (les bonnes étoiles) du marc (le bruit).

1. Vous versez l'océan (vos données) à travers le filtre.
2. Le filtre est conçu pour laisser passer uniquement les étoiles brillantes et bloquer le reste.
3. Vous répétez l'opération plusieurs fois pour nettoyer l'image.

Le problème :
Dans la vraie vie, ce filtre n'est pas parfait.

• Parfois, le café est trop sale (les calculs sont approximatifs).
• Parfois, pour aller plus vite, on utilise un filtre en papier fin au lieu d'un filtre en métal (on utilise des calculs moins précis, comme des nombres à virgule flottante simplifiés).
• Parfois, on ne connaît pas exactement la forme du filtre (on utilise une approximation de l'inverse d'une matrice).

Avec la méthode classique, si le filtre est imparfait ou si l'eau est sale, le café final reste sale. La méthode s'arrête, bloquée par le bruit, et ne trouve pas les étoiles avec une précision parfaite. C'est comme essayer de voir une étoile à travers une vitre sale : plus vous frottez, plus la vitre s'embue.

---

La Solution : R-ChFSI (La méthode "Residuelle")

Les auteurs de ce papier (Nikhil Kodalia, Kartick Ramakrishnan et Phani Motamarri) ont inventé une nouvelle méthode appelée R-ChFSI.

L'analogie du "Bruit de fond" :
Au lieu de filtrer directement les étoiles (les vecteurs propres), la nouvelle méthode décide de filtrer l'erreur (ce qu'ils appellent le "résidu").

Imaginez que vous essayez d'écouter une chanson dans une pièce bruyante.

• L'ancienne méthode (ChFSI) : Vous essayez d'isoler la voix du chanteur directement. Si le bruit est fort, vous entendez mal, et vous vous arrêtez.
• La nouvelle méthode (R-ChFSI) : Vous écoutez d'abord ce qui ne va pas (le bruit, la distorsion). Vous vous concentrez uniquement sur la correction de l'erreur.
  • Au début, l'erreur est énorme (le bruit est fort).
  • À chaque étape, vous corrigez l'erreur.
  • Le secret magique : Plus vous vous rapprochez de la vraie réponse (l'étoile), plus l'erreur devient petite.
  • Parce que vous filtrez l'erreur, et que l'erreur diminue naturellement, le "filtre sale" (les approximations) devient de moins en moins important. Le bruit s'efface tout seul à mesure que vous vous rapprochez du but.

---

Pourquoi est-ce une révolution ?

Cette nouvelle méthode permet trois choses incroyables :

1. Utiliser des approximations bon marché :
   Imaginez que pour calculer la trajectoire, vous deviez utiliser une carte très précise (très chère et lente à imprimer) ou une carte dessinée à la main (rapide mais approximative).

   • L'ancienne méthode exigeait la carte précise.
   • La nouvelle méthode (R-ChFSI) dit : "Peu importe si la carte est dessinée à la main, tant que je corrige mes erreurs à chaque étape, j'arriverai à destination avec une précision parfaite."
     Cela permet d'utiliser des approximations mathématiques très rapides au lieu de calculs lourds et lents.

2. Utiliser des ordinateurs "moins précis" mais plus rapides :
   Les puces modernes (comme les GPU pour l'IA) sont devenues très rapides en utilisant des calculs "simplifiés" (comme la précision FP32 ou TF32 au lieu de la précision double FP64). C'est comme passer d'une balance de laboratoire ultra-précise (lente) à une balance de cuisine rapide.

   • L'ancienne méthode cassait avec la balance de cuisine.
   • La nouvelle méthode fonctionne parfaitement avec la balance de cuisine, tout en donnant un résultat aussi précis que la balance de laboratoire, mais beaucoup plus vite.

3. Résoudre des problèmes géants :
   Les auteurs ont testé leur méthode sur des simulations de matériaux (comme le silicium ou le carbone) avec des millions de points de données.

   • Ils ont réussi à trouver les solutions avec une précision de 100 millions de fois supérieure à l'ancienne méthode quand on utilisait des approximations.
   • Ils ont gagné jusqu'à 2,7 fois plus de vitesse sur les supercalculateurs modernes.

En résumé

Ce papier nous dit : "Arrêtez de chercher la perfection dans chaque étape de votre calcul. Concentrez-vous sur la correction de vos erreurs, et vous pourrez utiliser des outils plus simples, plus rapides et moins chers, tout en obtenant un résultat final parfait."

C'est comme apprendre à conduire : au lieu de regarder chaque petit mouvement du volant avec une loupe (calculs précis et lents), vous regardez la route, vous corrigez votre trajectoire quand vous déviez (filtrage du résidu), et vous arrivez à destination plus vite, même si votre voiture a un système de direction un peu "flou".

Résumé technique

1. Problématique

Les problèmes de valeurs propres hermitiennes de grande taille sont fondamentaux dans de nombreux domaines de la physique computationnelle, notamment la théorie de la fonctionnelle de la densité (DFT) de Kohn-Sham pour la modélisation des matériaux, la dynamique des fluides et l'électromagnétisme. Dans ces applications, il est souvent nécessaire de calculer un petit sous-ensemble de paires de valeurs propres extrêmes (les plus basses) de manière répétée, car la matrice du système évolue au cours d'une itération non linéaire externe (par exemple, dans le processus de champ auto-cohérent - SCF).

La méthode standard pour résoudre ces problèmes est l'Itération de Sous-Espace Filtrée par Chebyshev (ChFSI). Cependant, cette méthode rencontre deux défis majeurs dans les architectures modernes et les applications à grande échelle :

1. Produits Matrice-Vecteur Inexacts : Dans les problèmes de valeurs propres généralisés ($Ax = \lambda Bx$), l'inversion exacte de la matrice $B$ (souvent une matrice de recouvrement) est prohibitivement coûteuse. On utilise donc des approximations (comme des approximations diagonales ou par masses lumpées). De plus, l'utilisation de l'arithmétique de basse précision (FP32, TF32, BF16) pour accélérer les calculs introduit des erreurs d'arrondi.
2. Stagnation de la Convergence : La formulation classique de ChFSI applique le filtre de Chebyshev directement aux vecteurs propres estimés. Lorsque des approximations sont utilisées dans les produits matrice-vecteur, les erreurs s'accumulent et ne disparaissent pas à mesure que la solution converge. Cela entraîne une stagnation de la méthode : la norme du résidu ne descend pas en dessous d'un certain seuil (proportionnel à l'erreur d'approximation), empêchant d'atteindre les tolérances requises pour les simulations de haute précision.

2. Méthodologie : R-ChFSI

Les auteurs proposent une nouvelle reformulation appelée R-ChFSI (Residual-based Chebyshev Filtered Subspace Iteration). L'idée centrale est de déplacer le point d'application du filtre de Chebyshev des vecteurs propres estimés vers les résidus.

Reformulation Mathématique

Au lieu de construire le sous-espace filtré $Y$ directement à partir des vecteurs $X$ via la relation de récurrence standard :
$$Y_{k+1} = 2\sigma_{k+1} \frac{H}{e} Y_k - \dots$$
R-ChFSI définit un résidu pondéré $Z_k = D R_k$, où $R_k = C_k(H)X - X C_k(\Lambda)$ est le résidu et $D$ est une approximation de $B^{-1}$.

La nouvelle relation de récurrence opère sur $Z_k$ :
$$Z_{k+1} = a_k D H D^{-1} Z_k + b_k Z_k + c_k Z_{k-1} + a_k D R \Lambda_k$$
Une fois le filtre appliqué aux résidus, le sous-espace filtré est reconstruit via la relation :
$$Y_p = D^{-1} Z_p + X \Lambda_p$$

Avantages Théoriques

• Découplage de l'erreur : Dans la formulation classique, le bruit d'approximation est appliqué aux vecteurs dont la norme reste constante ($O(1)$), créant une erreur persistante. Dans R-ChFSI, le bruit est appliqué aux résidus. Comme la norme du résidu $\|R^{(i)}\|$ tend vers zéro lors de la convergence, l'erreur introduite par les approximations (produits inexacts, basse précision) décroît proportionnellement au résidu.
• Garantie de convergence : Les auteurs démontrent mathématiquement que R-ChFSI satisfait une condition de convergence même en présence d'erreurs d'approximation, là où ChFSI classique échoue (stagnation). La condition nécessaire pour la convergence est que l'erreur de filtrage reste inférieure à l'écart spectral Chebyshev, ce qui est garanti car l'erreur diminue avec le résidu.

3. Contributions Clés

1. Nouvelle Reformulation Résiduelle : Introduction d'un algorithme qui opère sur les résidus plutôt que sur les vecteurs propres, rendant la méthode intrinsèquement tolérante aux erreurs de produits matrice-vecteur.
2. Robustesse aux Approximations de $B^{-1}$ : Démonstration que R-ChFSI permet d'utiliser des approximations bon marché de l'inverse de la matrice $B$ (crucial pour les problèmes généralisés en DFT) sans dégrader la précision finale, contrairement à ChFSI.
3. Compatibilité avec l'Arithmétique de Basse Précision : La méthode est conçue pour tirer parti des architectures matérielles modernes (GPU, accélérateurs AI) en permettant l'utilisation de formats flottants réduits (FP32, TF32, BF16) pour les produits matrice-vecteur dominants, tout en maintenant une précision de double flottant (FP64) sur le résultat final.
4. Analyse de Convergence Rigoureuse : Preuve théorique des bornes de convergence pour les cas avec erreurs d'approximation, validant que l'erreur de filtrage s'annule avec le résidu.

4. Résultats Expérimentaux

Les auteurs ont validé leur méthode sur deux types de problèmes : des matrices denses aléatoires contrôlées et de grands problèmes de DFT réels.

Expériences sur Matrices Denses (Contrôle)

• Scénario : Comparaison de ChFSI et R-ChFSI avec des niveaux de bruit injectés ($\epsilon$) dans les produits matrice-vecteur.
• Résultat : ChFSI stagne à un résidu de l'ordre de $\epsilon$ (ex: $10^{-2}$ ou $10^{-3}$). R-ChFSI continue de converger jusqu'à la précision machine ($10^{-14}$), indépendamment du niveau de bruit initial, confirmant la théorie.

Expériences à Grande Échelle (DFT sur GPU)

• Configuration : Utilisation du code DFT-FE sur le supercalculateur Aurora (Intel Data Center GPU Max Series).
• Systèmes : Trois systèmes matériaux (Molybdène, Silicium, Carbone) avec jusqu'à 85 millions de points de grille et 13 500 paires de valeurs propres.
• Précision : Tests avec FP64, FP32, TF32 (Tensor Float 32) et communication MPI en BF16 (TF32B).
• Précision :
  • R-ChFSI atteint des normes de résidus de l'ordre de $10^{-8}$ (tolérance cible DFT) même avec des approximations diagonales de $B^{-1}$ et de l'arithmétique TF32/BF16.
  • ChFSI classique échoue à atteindre cette tolérance dans les mêmes conditions, stagnant à des résidus beaucoup plus élevés.
• Performance (Accélération) :
  • Étape de filtrage : Accélérations allant jusqu'à 2,7x avec la variante TF32B (TF32 pour le calcul + BF16 pour la communication MPI) par rapport à la version FP64.
  • Solveur complet : Accélérations allant jusqu'à 2,1x pour la résolution complète du problème de valeurs propres.
  • Ces gains sont obtenus sans sacrifier la précision, grâce à la réduction du trafic mémoire et à l'utilisation des cœurs tensoriels.

5. Signification et Impact

Ce travail comble un fossé critique entre les algorithmes de valeurs propres traditionnels et les exigences des architectures de calcul haute performance (HPC) modernes.

• Efficacité Énergétique et Temporelle : En permettant l'utilisation de la basse précision (TF32, BF16) et d'approximations matricielles peu coûteuses, R-ChFSI réduit considérablement le temps de calcul et la consommation énergétique des simulations de matériaux à grande échelle.
• Faisabilité des Problèmes Généralisés : Il rend viable la résolution de problèmes généralisés ($Ax = \lambda Bx$) complexes où l'inversion exacte de $B$ est impossible, en offrant une alternative robuste aux méthodes itératives coûteuses.
• Adaptabilité Matérielle : La méthode est parfaitement alignée avec l'évolution des puces GPU (comme les architectures NVIDIA Blackwell ou Intel Ponte Vecchio) qui privilégient la haute performance en basse précision.
• Généralité : Bien que testée sur la DFT, la méthode est applicable à tout problème de valeurs propres hermitien nécessitant une itération de sous-espace, ouvrant la voie à des simulations plus rapides en mécanique des fluides, en élasticité et en physique des plasmas.

En résumé, R-ChFSI transforme une limitation (l'imprécision des calculs) en un avantage, en exploitant la structure mathématique du résidu pour garantir une convergence robuste tout en exploitant pleinement la puissance des accélérateurs matériels modernes.