Le Gradient conjugué préconditionné par bloc localement optimal (acronyme anglophone LOBPCG) est une méthode utilisée pour trouver les valeurs propres les plus grandes (ou les plus petites) et les vecteurs propres correspondants d'un problème de valeurs propres généralisé symétrique
pour une paire de matrices hermitiennes complexes ou réelles symétriques, où la matrice est également supposée définie positive.
Caractéristiques principales
La méthode est dite matrix-free c'est-à-dire qu'elle ne nécessite pas de stocker explicitement les coefficients de la matrice, mais on peut accéder à la matrice en évaluant les produits matrice-vecteur.. La méthode ne nécessite pas de factorisation de matrice, même pour un problème aux valeurs propres généralisé. Le coût de calcul par itération ainsi que l'occupation mémoire sont compétitifs par rapport à la méthode de Lanczos, calculant une seule paire vecteur propre, valeur propre d'une matrice symétrique. La convergence linéaire est théoriquement garantie et pratiquement observée. On observe une convergence accélérée due au préconditionnement direct, contrairement à la méthode de Lanczos, la matrice du préconditionneur peut être fixe ou varier d'une itération à l'autre mais rester symétrique et définie positive. La méthode peut tirer parti de l'utilisation de techniques de décomposition de domaine et d'un préconditionneur multigrille. La méthode peut être redémarrée à chaud (c'est-à-dire que l'on utilise des vecteurs propres approchés venant d'une autre méthode pour initier le calcul) et elle calcule une approximation des vecteurs propres, valeurs propres à chaque itération. La méthode est plus stable numériquement que la méthode de Lanczos, et peut fonctionner en arithmétique de faible précision. Elle est facile à mettre en œuvre, avec de nombreuses implantations existantes. La méthode repose sur la notion de bloc et permet ainsi d'utiliser des opérations matrice-matrice très efficaces, par exemple BLAS 3. La taille des blocs peut être ajustée pour équilibrer la vitesse de convergence par rapport aux coûts de calcul des orthogonalisations et au coût de la méthode Rayleigh-Ritz à chaque itération.
Algorithme
Version à un vecteur On commence par décrire un algorithme qui recherché un seul couple vecteur propre / valeur propre, par exemple celui correspondant à la plus petite valeur propre.
Préliminaires : rappel sur la méthode de montée ou descente de gradient pour les problèmes de valeurs propres La méthode effectue une maximisation (ou minimisation) itérative du quotient de Rayleigh généralisé
ce qui permet de trouver les paires vecteurs propres, valeurs propres les plus grandes (ou les plus petites) de
La direction utilisée par l'algorithme du gradient est précisément le gradient du quotient de Rayleigh généralisé, direction proportionnelle au vecteur
appelé vecteur propre résiduel. Si un préconditionneur est disponible, il est appliqué au résidu et donne le vecteur
appelé résidu préconditionné. Sans préconditionnement, on pose et donc . La méthode itérative s'écrit
ou, alternativement de manière moins concise,
Cette méthode est connue sous le nom de montée (ou descente) de gradient préconditionnée, où le scalaire est le pas d'itération. La taille optimale du pas peut être déterminée en maximisant le quotient de Rayleigh, c'est-à-dire,
(ou en cas de minimisation), auquel cas la méthode est dite localement optimale.
On note que le maximum (ou minimum) est pris pour appartenant à l'espace vectoriel de dimension deux engendré par les deux vecteurs et .
Formule de récurrence à trois termes Pour accélérer considérablement la convergence de la montée (ou descente) de gradient préconditionnée localement optimale, un vecteur supplémentaire peut être ajouté à la formule de récurrence à deux termes pour la rendre à trois termes (devient une fonction de , et )
La maximisation/minimisation du quotient de Rayleigh se fait maintenant dans un espace vectoriel de dimension trois et peut être effectuée numériquement par la méthode Rayleigh-Ritz. L'ajout de vecteurs supplémentaires, voir, par exemple, l'extrapolation de Richardson, n'entraîne pas d'accélération significative. mais augmente les coûts de calcul, et n'est donc généralement pas recommandé.
Améliorations de la stabilité numérique Au fur et à mesure que les itérations convergent, les vecteurs et deviennent presque linéairement dépendants, ce qui entraîne une perte de précision et rend la méthode Rayleigh-Ritz numériquement instable en présence d'erreurs d'arrondi. La perte de précision peut être évitée en substituant le vecteur avec un vecteur , qui peut être plus éloigné de , dans la base du sous-espace tridimensionnel , tout en gardant le sous-espace inchangé et en évitant l'orthonormalisation ou toute autre opération supplémentaire. De plus, l'orthonormalisation de la base du sous-espace tridimensionnel peut être nécessaire pour les problèmes de valeurs propres mal conditionnés afin d'améliorer la stabilité et la précision atteignable.
Analogues du sous-espace de Krylov Il s'agit d'une version à vecteur unique de la méthode LOBPCG - une possible généralisation des solveurs linéaires à gradient conjugué préconditionnés au cas des problèmes de valeurs propres symétriques. Même dans le cas trivial et l'approximation résultante avec sera différent de celui obtenu par l'algorithme de Lanczos, bien que les deux approximations appartiendront au même sous-espace de Krylov.
Scénarios d'utilisation pratiques L'extrême simplicité et la haute efficacité de la version à vecteur unique de LOBPCG la rendent attrayante pour les applications de calcul de valeurs propres en environnement contraint en ressources de calcul, par exemple pour la détection d'anomalies en temps réel basée sur le partitionnement spectral. On utilise aussi pour le partitionnement de graphe sur ASIC ou FPGA, ou encore pour la modélisation de phénomènes physiques sur les supercalculateurs exascale du classement TOP500.
version par bloc de l'algorithme
Résumé On cherche maintenant à calculer plusieurs couples propres simultanément. On pourrait appliquer la méthode LOBPCG à un seul vecteur (décrite ci-dessus) pour avoir le couple correspondant à la plus grande valeur propre (en module), noté et enchaîner avec une déflation orthogonale pour trouver les couples suivant. Si on appelle la matrice (supposée symétrique, mais on peut généraliser on cas non-symétrique) dont on cherche les couples propres, rappelons que la déflation orthogonale consiste à introduire une matrice dont on peut montrer qu'elle a les mêmes couples propres que sauf . Il suffit d'appliquer à nouveau la méthode LOBPCG à un seul vecteur pour trouver un deuxième couple propre et de répéter cette opération autant de fois que nécessaire.
Cependant, avec approche, chaque nouveau couple propre calculé de manière approchée dépend du calcul de tous les autres couples propres précédents et ainsi les erreurs de calcul s'accumulent et les estimations des couples propres deviennent de moins en moins bonnes. Pour améliorer cette situation, la méthode LOBPCG par bloc se propose de calculer plusieurs couples propres ensemble d'un seul bloc, de manière rapide, précise et robuste des vecteurs propres. Elle améliore également les cas où l'on a plusieurs plusieurs couples propres très proches les uns des autres qui seraient très mal estimés par la déflation orthogonale (convergence très lente). La taille du bloc peut être ajustée pour équilibrer la stabilité numérique par rapport à la vitesse de convergence et aux coûts de calcul des orthonormalisations et de la méthode Rayleigh-Ritz à chaque itération.
Principe de la méthode L'approche par blocs dans LOBPCG remplace les vecteurs uniques et avec des vecteurs-blocs, c'est-à-dire des matrices et , où, par exemple, chaque colonne de se rapproche de l'un des vecteurs propres. Toutes les colonnes sont itérées simultanément, et la prochaine matrice de vecteurs propres approximatifs est déterminé par la méthode Rayleigh-Ritz sur le sous-espace couvert par toutes les colonnes de matrices et . Chaque colonne de est calculée simplement comme le résidu préconditionné pour chaque colonne de La matrice est déterminée de telle sorte que les sous-espaces engendrés par les colonnes de et de sont identiques.
Compromis entre stabilité numérique et efficacité La méthode Rayleigh-Ritz est appliquée sur le sous-espace engendré par toutes les colonnes de matrices et , où en principe une base peut être choisie arbitrairement. Cependant, la méthode Rayleigh-Ritz peut en pratique devenir numériquement instable si certains des vecteurs de base ne sont qu'approximativement linéairement indépendant.
Le choix de la base de sous-espace devient crucial autant pour d'assurer la stabilité numérique de la méthode Rayleigh-Ritz que pour réduire à des coûts de calcul. L'approche sans doute la plus stable consiste à rendre les vecteurs de base orthogonaux, par exemple, par le processus d'orthonormalisation de Gram-Schmidt, opération coûteuse en temps de calcul. Par exemple, les implémentations LOBPCGMATLAB File Exchange function LOBPCG.SciPy sparse linear algebra function lobpcg., utilise une factorisation de Cholesky instable mais efficace de la matrice normale, qui est effectuée uniquement sur les matrices individuelles et , plutôt que sur l'ensemble du sous-espace. Sur une architecture de calcul moderne, la quantité de mémoire disponible est suffisante pour se permettre d'utiliser des tailles de bloc de l'ordre de , néanmoins le temps de calcul consacré aux orthogonalisations et à la méthode Rayleigh-Ritz commence à dominer.
Verrouillage des vecteurs propres précédemment convergés Quand on utilise une méthode par bloc itérative pour approcher les vecteurs propres, il arrive très souvent qu'à l'intérieur d'un bloc, certains vecteurs propres convergent plus rapidement que d'autres. Le verrouillage des vecteurs propres déjà convergés consiste à les retirer de la boucle itérative, afin d'éliminer des calculs inutiles et d'améliorer la stabilité numérique. Une simple suppression d'un vecteur propre peut probablement entraîner la formation de son double dans des vecteurs toujours itératifs. Le fait que les vecteurs propres d'une matrice symétrique soient orthogonaux par paire suggère de garder tous les vecteurs itératifs orthogonaux aux vecteurs verrouillés.
Le verrouillage peut être mis en œuvre différemment en maintenant la précision et la stabilité numériques tout en minimisant les coûts de calcul. Par exemple, les implémentations LOBPCG., séparent le verrouillage dur, c'est-à-dire une déflation par restriction, où les vecteurs propres verrouillés servent d'entrée de code et ne changent pas, du verrouillage doux, où les vecteurs verrouillés ne participent pas à l'étape itérative généralement la plus coûteuse en calcul des résidus, mais cependant, participent pleinement à la méthode Rayleigh-Ritz et peuvent donc être modifiés par la méthode Rayleigh-Ritz.
Théorie et pratique de la convergence La méthode LOBPCG, par construction, assure une minimisation du quotient de Rayleigh au moins aussi rapide que la descente de gradient appliqué à un du bloc, dont on connaît la convergence théorique. Chaque vecteur propre est un point stationnaire du quotient de Rayleigh, où le gradient s'annule. Ainsi, la descente du gradient peut ralentir à proximité de n'importe quel vecteur propre, cependant, soit la méthode converge vers le vecteur propre avec un taux de convergence linéaire ou, si ce vecteur propre est un point col, le quotient de Rayleigh itératif est susceptible de converger vers la deuxième plus basse valeur propre. La convergence dans le pire cas a été déterminée et dépend de l'écart relatif entre la valeur propre et le reste du spectre de la matrice et de la qualité du préconditionneur, s'il est présent.