Komplexität des Findens der Neuzusammensetzung einer Matrix

40

Meine Frage ist einfach:

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

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

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 ) .ϵnO(poly(1/ϵ)n3)

EDIT 2 : Siehe diese verwandte Frage zu symmetrischen Matrizen .

Lev Reyzin
quelle
Haben Sie sich die Reduktion von der Matrixinversion zur Matrixmultiplikation im Lehrbuch der CLRS-Algorithmen angesehen? Ich würde mich zunächst mit diesen Ideen befassen, um festzustellen, ob sie sich auf die Selbstzerlegung erstrecken.
Warren Schudy
Ja - sie scheinen sich auf das Auffinden einer LU-Zerlegung zu erstrecken, aber ich weiß nicht, wie ich sie für eine Eigenzerlegung einsetzen soll.
Lev Reyzin
Wissen Sie, ob der bekannteste Algorithmus zur Berechnung der SVD ist? O(n3)
Robin Kothari
1
O(min(mn2,m2n))n×n
In Ordung. Ich weiß auch nicht viel über diesen Bereich, aber vielleicht kann die SVD-Berechnung auf eine Neukomposition reduziert werden, da Sie, wenn Sie AA * und A * A neu komponieren können, die rechte und linke Matrix für die SVD erhalten.
Robin Kothari

Antworten:

18

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ω+1mmn3+n2log2nlogb2b

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.)

virgi
quelle
13

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

Thomas
quelle
Vielen Dank für Ihre Antwort - ich brauche etwas Zeit, um es zu verdauen! Aber wenn man Matrix-Vektor-Multiplikation verwendet, könnte die Abhängigkeit von n vielleicht besser sein als n ^ 3.
Lev Reyzin
6

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(n3MB[n(logn+L)])MB(s)sL

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.

user834
quelle
interessant, aber das scheint noch schlimmer als n ^ 3. Wissen wir, dass dies das bestmögliche ist?
Lev Reyzin
Die Laufzeiten von Algorithmen dieser Art hängen mit der Komplexität der Matrixmultiplikation zusammen, die bei O (n ^ 3) liegt. Ich kenne Strassens Algorithmus, aber wenn Sie numerische Stabilitätsprobleme nicht ignorieren, erhalten Sie meiner Meinung nach O (n ^ 3) für die Matrixmultiplikation zurück. Iterative Methoden konvergieren im "durchschnittlichen" Fall möglicherweise schneller, aber ich glaube im Allgemeinen, dass O (n ^ 3) das Beste ist, was Sie tun können.
User834
Sie sagen also, wenn mir numerische Stabilitätsprobleme egal sind, können wir es auf O (n ^ 2.376) bringen?
Lev Reyzin
5

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.

Asterix
quelle
1

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ω+η)ωη>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.

Sébastien Loisel
quelle
0

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

Anonym
quelle
3
Vielen Dank für den Hinweis, aber beim Durchsuchen des Buches in Google Books konnte ich die Reduktion auf die Matrixmultiplikation nicht finden. Haben Sie einen Hinweis auf eine konkrete Referenz oder einen Algorithmus? Und ihre SVD-Algorithmen scheinen von der Bedingungsnummer der Matrix abzuhängen, was keine Worst-Case-Analyse ist. In Bezug auf numerische Stabilitätsprobleme usw. nehmen wir den idealisierten Fall an, in dem alle Multiplikationen und Divisionen Zeiteinheiten benötigen und genaue Antworten liefern.
Lev Reyzin