EVD non symétrique

Le problème non symétrique de la recherche des valeurs propres admet deux formulations différentes : la recherche des vecteurs x tels que Ax = Λx, et la recherche des vecteurs y tels que yHA = ΛyH (yH désignant la transposée conjuguée complexe de y). Le vecteur x est un vecteur propre à droite, le vecteur y est un vecteur propre à gauche, correspondant à la valeur propre Λ, qui est la même pour les deux vecteurs propres.

Contrairement au problème symétrique, les valeurs propres a d'une matrice non symétrique ne forment pas un système orthogonal. De plus, les valeurs propres ne forment pas nécessairement un système de vecteurs linéairement indépendants (ceci est possible, mais pas obligatoire, dans le cas de valeurs propres multiples : un sous-espace de cardinal inférieur à k peut correspondre à la valeur propre de multiplicité k).

La deuxième différence avec le problème symétrique réside dans le fait qu'une matrice non symétrique ne peut être facilement réduite à une matrice tridiagonale ou à une autre forme compacte. L'asymétrie de la matrice implique qu'après avoir annulé tous les éléments situés sous la première sous-diagonale (par une transformation orthogonale), les éléments du triangle supérieur ne sont pas annulés, ce qui conduit à une matrice sous forme de Hessenberg supérieure. Ceci ralentit l'algorithme, car il est nécessaire de mettre à jour tous les triangles supérieurs de la matrice après chaque itération de l'algorithme QR.

Enfin, la troisième différence est que les valeurs propres d'une matrice non symétrique peuvent être complexes (de même que leurs vecteurs propres associés).

Description de l'algorithme

La résolution d'un problème non symétrique de recherche des valeurs propres se déroule en plusieurs étapes. La première étape consiste à réduire la matrice sous forme de Hessenberg supérieure par une transformation orthogonale. La deuxième étape, la plus longue, consiste à réduire la matrice sous forme de Schur supérieure par une autre transformation orthogonale. Si l'on ne doit calculer que les valeurs propres, cette étape est la dernière car les valeurs propres de la matrice se trouvent dans les blocs diagonaux d'une matrice quasi-triangulaire sous sa forme de Schur canonique. Si l'on doit également calculer les vecteurs propres, il est nécessaire d'effectuer une substitution rétrograde avec les vecteurs de Schur et les vecteurs quasi-triangulaires (ce qui revient à résoudre un système d'équations linéaires ; la substitution rétrograde en elle-même est rapide, mais la nécessité de sauvegarder toutes les transformations double la durée de l'algorithme).

La décomposition de Schur, qui est l'étape la plus longue, est réalisée à l'aide de l'algorithme QR avec décalages multiples. Cet algorithme provient de la bibliothèque LAPACK. Il s'agit d'un analogue, pour les matrices par blocs, de l'algorithme QR classique avec double décalage. Comme tous les algorithmes pour matrices par blocs, il nécessite un paramétrage pour optimiser ses performances.

On peut ajuster la valeur de NS (paramètre interne de la sous-routine InternalSchurDecomposition) en définissant le nombre de décalages par itération. En augmentant le nombre de décalages, les performances de l'algorithme s'améliorent, atteignant leur maximum entre NS=4 et NS=16. Au-delà de NS, les performances diminuent considérablement. Les intervalles peuvent varier selon les systèmes, mais le constat reste globalement le même. La valeur par défaut de NS offre de bonnes performances sur la plupart des systèmes ; toutefois, si les performances sont critiques, il est conseillé de calibrer ce paramètre. Il convient de noter que la valeur optimale dépend à la fois des caractéristiques du système et des propriétés des matrices traitées.

Description du module

La sous-routine RMatrixEVD calcule les valeurs propres et, le cas échéant, les vecteurs propres (à droite et/ou à gauche) d'une matrice quelconque. Elle prend la matrice A en entrée et renvoie le tableau des valeurs propres (parties réelles et imaginaires) ainsi que le tableau des vecteurs propres (la structure des tableaux est décrite en détail dans les commentaires de la sous-routine).