Komplexität des Findens der Neuzusammensetzung einer Matrix

Meine Frage ist einfach:

Was ist die Worst-Case-Laufzeit des bekanntesten Algorithmus zur Berechnung einer eigendekomposition einer Matrix?$n \times n$

Reduziert sich die Zersetzung auf Matrixmultiplikation oder handelt es sich im schlimmsten Fall um die bekanntesten Algorithmen (über SVD )?$O(n^3)$

Bitte beachten Sie, dass ich nach einer Worst-Case-Analyse (nur in Bezug auf ) und nicht nach Grenzen mit problemabhängigen Konstanten wie der Bedingungsnummer frage.$n$

EDIT : Angesichts einiger der folgenden Antworten, lassen Sie mich die Frage anpassen: Ich würde mich über eine Annäherung freuen . Die Annäherung kann multiplikativ, additiv, eingangsseitig oder nach vernünftiger Definition erfolgen. Ich bin interessiert, ob es einen bekannten Algorithmus gibt, der eine bessere Abhängigkeit von n aufweist als etwas wie O ( p o l y ( 1 / ϵ ) n 3 ) .$\epsilon$$n$$O(\mathrm{poly}(1/\epsilon)n^3)$

EDIT 2 : Siehe diese verwandte Frage zu symmetrischen Matrizen .

Ryan beantwortete eine ähnliche Frage zu mathoverflow. Hier ist der Link: mathoverflow-answer

Grundsätzlich können Sie die Eigenwertberechnung auf die Matrixmultiplikation reduzieren, indem Sie eine symbolische Determinante berechnen. Dies ergibt eine Laufzeit von O ( ), um Bits der Eigenwerte zu erhalten; Die derzeit bekannteste Laufzeit ist O ( ) für eine Approximation innerhalb von .$n^{\omega+1}m$$m$$n^3+n^2\log^2 n\log b$$2^{-b}$

Ryans Referenz ist Victor Y. Pan, Zhao Q. Chen: Die Komplexität des Matrix-Eigenproblems. STOC 1999: 507–516 ''.

(Ich glaube, es gibt auch eine Diskussion über die Beziehung zwischen den Komplexitäten von Eigenwerten und der Matrixmultiplikation in dem älteren Aho, Hopcroft und Ullman Buch "The Design and Analysis of Computer Algorithms". Ich habe das Buch jedoch nicht in der Hand vor mir, und ich kann Ihnen nicht die genaue Seitenzahl geben.)

Das Finden von Eigenwerten ist von Natur aus ein iterativer Prozess: Das Finden von Eigenwerten entspricht dem Finden der Wurzeln eines Polynoms. Darüber hinaus besagt das Abel-Ruffini-Theorem, dass man die Wurzeln eines beliebigen Polynoms im Allgemeinen nicht in einer einfachen geschlossenen Form (dh mit Radikalen wie der quadratischen Formel) ausdrücken kann. Sie können also nicht hoffen, Eigenwerte "exakt" zu berechnen.

Dies bedeutet, dass ein spektraler Zerlegungsalgorithmus ungefähr sein muss. Die Laufzeit eines allgemeinen Algorithmus muss von der gewünschten Genauigkeit abhängen. Es kann nicht nur von der Dimension abhängen.

Ich bin kein Experte in diesem Bereich. Ich würde vermuten, dass eine kubische Abhängigkeit von n ziemlich gut ist. Die Algorithmen, die ich gesehen habe, verwenden alle eine Matrix-Vektor-Multiplikation, anstatt eine Matrix-Matrix-Multiplikation. Ich wäre also etwas überrascht, wenn alles auf Matrix-Matrix-Multiplikation hinausläuft.

Schauen Sie sich http://en.wikipedia.org/wiki/List_of_numerical_analysis_topics#Eigenvalue_algorithms an

Ich werde nur eine Teilantwort geben, die sich auf die Eigenwerte einer Matrix bezieht.

Wie bereits erwähnt, gibt es viele iterative Methoden zum Ermitteln der Eigenwerte einer Matrix (z. B. Potenziteration). Im Allgemeinen reduziert sich das Ermitteln der Eigenwerte jedoch auf das Ermitteln der Wurzeln des charakteristischen Polynoms. Das Finden des charakteristischen Polynoms kann in , wobei die Kosten von und die des maximalen Eintrags ist, und zwar durch a Symbolische Determinantenberechnung nach dem Bareiss-Algorithmus . Siehe Yaps Buch über "Grundlagen der algorithmischen Algebra" , insbesondere Kap. 10, "Lineare Systeme" .$O(n^3 M_B[n(log n + L)] )$$M_B(s)$$s$$L$

Sobald das charakteristische Polynom gefunden ist, kann man die Wurzeln mit jedem gewünschten Genauigkeitsgrad unter Verwendung von Isolationsintervallen finden. Siehe Yaps Buch, Kap. 6 "Wurzeln von Polynomen" für Details. Ich vergesse die exakte Laufzeit, aber ihr Polynom im Grad des charakteristischen Polynoms und der gewünschten Genauigkeitsziffern.

Ich vermute, dass die Berechnung von Eigenvektoren bis zu einem beliebigen Genauigkeitsgrad ebenfalls polynomisch ist, aber ich sehe keinen einfachen Algorithmus. Es gibt natürlich die Standard-Trickkiste, die bereits erwähnt wurde, aber meines Wissens garantiert keine von ihnen eine polynomielle Laufzeit für die gewünschte Genauigkeit.

Sie können sich die neue Arbeit von Commandur und Kale ansehen, die einen kombinatorischen Algorithmus für Max-Cut liefert. Es scheint (aus einer flüchtigen Lesart), dass ihr Algorithmus darauf basiert, den dem maximalen Eigenwert entsprechenden Eigenvektor kombinatorisch zu finden und dann Luca Trevisans Algorithmus zu verwenden, sobald sie diesen Eigenvektor haben.

Es scheint, dass sie einen alternativen Ansatz zum Lanczos-Algorithmus verwenden, um einen solchen Eigenvektor zu finden, daher könnte er von Interesse sein. Ich bin mir nicht sicher, wie komplex ihre Methode zum Finden des Eigenvektors sein soll, aber es könnte sich lohnen, sie zu untersuchen. Da es sich um ein Näherungsverhältnis und nicht um die Zeit an sich handelt, an der sie interessiert sind, sind die von ihnen angegebenen Zeitgrenzen möglicherweise nicht optimal.

Dies ist eine alte Frage, aber einige wichtige Literatur scheint übersehen worden zu sein.

Es gibt Algorithmen, für die wir eine stärkere theoretische Unterstützung haben. Zum Beispiel gibt es Iterationen, die auf der Matrixzeichenfunktion basieren, siehe zum Beispiel "Fast Linear Algebra is Stable" von Demmel, Dumitriu und Holtz . In dieser Arbeit wird gezeigt, dass das Eigenwertproblem in der Zeit gelöst werden kann , wobei der Exponent der Matrixmultiplikation und eine beliebige Zahl .$(O^{\omega+\eta})$$\omega$$\eta$$>0$

Ja, es gibt das Pan + Chen + Zheng-Papier, das vorschlägt, das charakteristische Polynom zusammenzusetzen und in BigFloat zu berechnen, da Sie am Ende eine Menge Genauigkeit verlieren, aber nicht viele Leute halten dies für einen praktischen Ansatz.

Ich erwähne auch, dass der am weitesten verbreitete Algorithmus, die Francis-QR-Iteration, keinen Konvergenzbeweis für allgemeine Matrizen hat; Das Buch von Kressner behandelt mehrere Gegenbeispiele.

Ja, so ziemlich die gesamte numerische lineare Algebra kann auf Matrixmultiplikation reduziert werden, obwohl numerische Stabilität wie immer ein Problem darstellt. Auch bei Problemen wie eigendecomposition sollten Sie sich mit einer Annäherung begnügen, da die Lösung irrational sein kann. Lesen Sie das Buch Polynomial and Matrix Computations von Bini and Pan.

Hier ist eine weitere Referenz: Die schnelle lineare Algebra ist stabil. Http://www.netlib.org/lapack/lawnspdf/lawn186.pdf