Quelle est la façon la plus efficace de calculer le vecteur propre d'une matrice dense correspondant à la valeur propre de plus grande ampleur?

J'ai une matrice carrée symétrique réelle dense. La dimension est d'environ 1000x1000. Je dois calculer le premier composant principal et me demander quel pourrait être le meilleur algorithme pour ce faire.

Il semble que MATLAB utilise les algorithmes Arnoldi / Lanczos (pour eigs). Mais en lisant à leur sujet, je ne sais pas s'ils ont des avantages par rapport à la simple itération de puissance , car ma matrice n'est pas rare et je ne suis intéressé que par le premier vecteur propre.

Des recommandations quel est l'algorithme le plus rapide dans ce cas?

linear-algebra algorithms eigensystem Mika Fischer
la source

Sur mon ordinateur, sur une matrice symétrique 1000 X 1000 générée aléatoirement, la fonction "propre" dans R a pris environ une seconde pour calculer toutes les valeurs propres et les vecteurs, en arrondissant. Votre kilométrage peut varier, mais je doute que votre choix d'algorithme fasse une différence à des moments comme celui-ci.

Oui, c'est vrai bien sûr. Je ne suis pas vraiment soucieux de rendre mon programme plus rapide. Je suis simplement curieux de savoir si les techniques mentionnées plus compliquées sont également considérées comme supérieures dans ce cas d'utilisation (dense, uniquement le premier vecteur propre), ou s'il existe différentes techniques pour les matrices denses.

Voulez-vous dire le vecteur propre correspondant à la valeur propre la plus grande ou la plus petite? On dirait que vous voulez l'ancien.

Jack Poulson

Oui, le vecteur propre correspondant à la valeur propre de plus grande ampleur.

Mika Fischer

Réponses:

La méthode la plus rapide dépendra probablement du spectre et de la normalité de votre matrice, mais dans tous les cas, les algorithmes de Krylov devraient être strictement meilleurs que l'itération de puissance. GW Stewart a une discussion intéressante sur ce problème dans le chapitre 4, section 3 des algorithmes matriciels, volume II: Eigensystems :

$A$ $u$ $A^k u$ $A^k u$

$100 \times 100$ $i$ $.95^i$ $i=0$

Jack Poulson
la source

Hmm, j'aurais pensé que MRRR était maintenant la méthode standard quand on veut juste quelques vecteurs propres ...

k

$k$

O (k n^{2} + k^{2} n + k^{3})

$O(k n^2 + k^2 n + k^3)$

k

$k$

n

$n$

Je vois; d'une certaine manière, j'avais l'impression que vous deviez d'abord tridiagonaliser avant de faire Krylov. Merci!

Lanczos construit en fait progressivement cette matrice tridiagonale.

Jack Poulson

L'itération de puissance est la plus simple, mais comme mentionné ci-dessus, elle convergerait probablement très lentement si la matrice n'est pas normale. Vous obtenez un phénomène de "bosse" où la séquence semble diverger pendant de nombreuses itérations avant que le comportement asymptotique ne se déclenche.

Comme votre matrice est symétrique, vous pouvez envisager des itérations RQI, qui dans le cas symétrique produisent une convergence cubique: http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration .

Ce qui rend les itérations Arnoldi ou Lanczos très agréables (du moins à mon avis, mais je ne recherche pas l'algèbre linéaire numérique), c'est qu'elles sont très polyvalentes. Il est généralement possible de contrôler les valeurs propres qu'ils vous donnent et le nombre que vous obtenez. Cela est particulièrement vrai dans le cas symétrique (et encore mieux si votre matrice est définie). Pour les problèmes symétriques, ils sont très robustes. En tant que boîte noire, ils fonctionnent bien, mais ils sont également très réceptifs aux nouvelles informations sur les problèmes, telles que la capacité de résoudre des systèmes impliquant la matrice.

Reid.Atcheson
la source