Was ist der effizienteste Weg, um den Eigenvektor einer dichten Matrix zu berechnen, die dem Eigenwert der größten Größe entspricht?

Ich habe eine dichte echte symmetrische quadratische Matrix. Die Abmessung beträgt ca. 1000x1000. Ich muss die erste Hauptkomponente berechnen und mich fragen, welcher Algorithmus dafür am besten geeignet ist.

Es scheint, dass MATLAB die Arnoldi / Lanczos- Algorithmen (für eigs) verwendet. Aber wenn ich über sie lese, bin ich mir nicht sicher, ob sie Vorteile gegenüber einer einfachen Potenziteration haben , da meine Matrix nicht dünn ist und ich nur am ersten Eigenvektor interessiert bin.

Irgendwelche Empfehlungen, was ist der schnellste Algorithmus in diesem Fall?

linear-algebra algorithms eigensystem Mika Fischer
quelle

Auf meinem Computer, auf einer zufällig erzeugten 1000 x 1000 symmetrischen Matrix, dauerte die "Eigen" -Funktion in R ungefähr eine Sekunde, um alle Eigenwerte und Vektoren zu berechnen und aufzurunden. Ihr Kilometerstand kann variieren, aber ich bezweifle, dass Ihre Algorithmusauswahl bei solchen Zeiten einen Unterschied macht.

Ja, das stimmt natürlich. Ich bin nicht wirklich daran interessiert, mein Programm schneller laufen zu lassen. Ich bin nur neugierig, ob die erwähnten komplizierteren Techniken in diesem Anwendungsfall ebenfalls als überlegen angesehen werden (dicht, nur erster Eigenvektor) oder ob es verschiedene Techniken für dichte Matrizen gibt.

Meinen Sie den Eigenvektor, der dem größten oder kleinsten Eigenwert entspricht? Es hört sich so an, als ob Sie das erstere wollen.

Jack Poulson

Ja, der Eigenvektor entspricht dem Eigenwert mit der größten Größe.

Mika Fischer

Antworten:

Die schnellste Methode hängt wahrscheinlich vom Spektrum und der Normalität Ihrer Matrix ab, aber in allen Fällen sollten Krylov-Algorithmen strikt besser sein als die Leistungsiteration. GW Stewart hat eine nette Diskussion dieses Themas in Kapitel 4, Abschnitt 3 von Matrixalgorithmen, Band II: Eigensysteme :

Die Potenzmethode basiert auf der Beobachtung, dass, wenn ein dominantes Eigenpaar hat, die Vektoren unter milden Einschränkungen von immer genauere Annäherungen an den dominanten Eigenvektor erzeugen. Bei jedem Schritt berücksichtigt das Leistungsverfahren jedoch nur den einzelnen Vektor , was darauf hinausläuft, Informationen wegzuwerfen, die in den zuvor erzeugten Vektoren enthalten sind. Es stellt sich heraus, dass diese Informationen wertvoll sind ... " $A$ $u$ $A^k u$ $A^k u$

und er fährt fort zu zeigen, dass für eine Diagonalmatrix mit dem -ten Diagonalwert, der auf (ab ), der Krylov-Unterraum nach 25 Iterationen den dominanten Eigenvektor acht Größenordnungen erfasst besser als Power-Iteration. $100 \times 100$ $i$ $.95^i$ $i=0$

Jack Poulson
quelle

Hmm, ich hätte gedacht, MRRR wäre jetzt die Standardmethode, wenn man nur ein paar Eigenvektoren will ...

MRRR läuft auf symmetrischen tridiagonalen Matrizen, und um es für dichte Matrizen zu verwenden, muss man zuerst die dichte Matrix durch Ähnlichkeitstransformation (en) auf tridiagonale Form reduzieren, was im Allgemeinen kubische Arbeit erfordert. Wenn für ein Krylov-Verfahren nur Matrix-Vektor-Multiplikationen erforderlich sind, ist Arbeit erforderlich. Wenn relativ zu sehr klein ist , sollten Krylov-Methoden gewinnen.

k

$k$

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

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

k

$k$

n

$n$

Jack Poulson

Aha; Irgendwie hatte ich den Eindruck, dass man zuerst tridiagonalisieren musste, bevor man Krylov machte. Vielen Dank!

Lanczos baut diese tridiagonale Matrix tatsächlich allmählich auf.

Jack Poulson

Die Leistungsiteration ist die einfachste, aber wie oben erwähnt, würde sie wahrscheinlich sehr langsam konvergieren , wenn die Matrix sehr nicht normal ist. Sie erhalten ein "Buckel" -Phänomen, bei dem die Sequenz für viele Iterationen zu divergieren scheint, bevor asymptotisches Verhalten einsetzt.

Da Ihre Matrix symmetrisch ist, können Sie RQI-Iterationen in Betracht ziehen, die im symmetrischen Fall eine kubische Konvergenz ergeben: http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration .

Was Arnoldi- oder Lanczos-Iterationen sehr schön macht (zumindest meiner Meinung nach, aber ich erforsche keine numerische lineare Algebra), ist, dass sie sehr vielseitig sind. Es ist normalerweise möglich zu steuern, welche Eigenwerte sie Ihnen geben und wie viele Sie erhalten. Dies gilt insbesondere im symmetrischen Fall (und noch besser, wenn Ihre Matrix eindeutig ist). Für symmetrische Probleme sind sie sehr robust. Als Black Box funktionieren sie gut, sind aber auch sehr empfänglich für neue Probleminformationen, wie beispielsweise die Fähigkeit, Systeme zu lösen, an denen die Matrix beteiligt ist.

Reid.Atcheson
quelle