Komplexität beim Auffinden der Eigendekomposition einer * symmetrischen * Matrix

9

Dies ist eine spezielle Version einer früheren Frage: Komplexität beim Finden der Eigendekomposition einer Matrix .

Für NxN-Symmetriematrizen ist bekannt, dass die O (N ^ 3) -Zeit ausreicht, um die Eigenzerlegung zu berechnen. Die Frage ist: Können wir eine subkubische Komplexität erreichen? Vielen Dank.

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis Lihong Li
quelle
Braucht das wirklich eine separate Frage? Wenn jemand die Antwort auf diesen Sonderfall gewusst hätte, hätte er dies sicherlich in der anderen Frage gesagt.
Warren Schudy
Ich habe den schlimmsten Fall in meiner Frage betont, daher denke ich, dass dies fair ist ...
Lev Reyzin
2
Sind Sie sicher, dass O (N ^ 3) zeitgebunden ist? Siehe meine verwandte Frage zur Gaußschen Eliminierung.
Jeffs
Es scheint aus mathoverflow.net/questions/24287/... können Sie erhalten für eine annähernde Lösung. O(n3)
Lev Reyzin

Antworten:

2

Aus meiner Sicht ist dieser Sonderfall nicht einfacher als der allgemeine Fall. Rein symbolisch können Sie das Problem des Findens der Singularwertzerlegung (SVD) auf das Problem des Diagonalisierens einer symmetrischen Matrix reduzieren. Man kann die SVD von M aus den Eigenvektoren und Eigenwerten von M * M ablesen. Beachten Sie, dass die Reduktion nur eine Matrixmultiplikation zur Berechnung von M * M beinhaltet. Es scheint nicht, dass es ernsthafte numerische Probleme geben sollte.


quelle