Was ist der schnellste Weg, um alle Eigenwerte einer sehr großen und spärlichen Adjazenzmatrix in Python zu berechnen?

Ich versuche herauszufinden, ob es einen schnelleren Weg gibt, alle Eigenwerte und Eigenvektoren einer sehr großen und spärlichen Adjazenzmatrix zu berechnen, als mit scipy.sparse.linalg.eigsh Soweit ich weiß, verwendet diese Methode nur die Spärlichkeit und Symmetrieattribute der Matrix. Eine Adjazenzmatrix ist auch binär, was mich glauben lässt, dass es einen schnelleren Weg gibt, dies zu tun.

Ich habe eine zufällige 1000x1000-Adjazenzmatrix mit geringer Dichte erstellt und verschiedene Methoden auf meinem x230-Ubuntu-13.04-Laptop verglichen:

scipy.sparse.linalg.eigs: 0,65 Sekunden
scipy.sparse.linalg.eigsh: 0,44 Sekunden
scipy.linalg.eig: 6,09 Sekunden
scipy.linalg.eigh: 1,60 Sekunden

Mit den spärlichen eigs und eigsh setze ich k, die Anzahl der gewünschten Eigenwerte und Eigenvektoren, auf den Rang der Matrix.

Das Problem beginnt mit größeren Matrizen - auf einer 9000x9000-Matrix dauerte es scipy.sparse.linalg.eigsh 45 Minuten!

linear-algebra python performance eigensystem scipy Noam Peled
quelle

NB. scipy.sparse.linalg.eigsh ist ARPACK

pv.

Je größer Ihre Matrix ist, desto weniger wahrscheinlich ist es, dass Sie die inneren Eigenwerte (dh weder die größten noch die kleinsten Eigenwerte) genau berechnen. Welche Informationen benötigen Sie aus der Matrix, die Sie zerlegen?

Geoff Oxberry

Diese Frage wurde Cross-gepostet hier . Ich werde empfehlen, dass die gekreuzte Version geschlossen wird.

Aron Ahmadia

Ich möchte A ^ k berechnen. Nach einem Umdenken denke ich, dass mit einer solchen Matrix die direkte Multiplikation (A A A ...) viel schneller berechnet werden kann als mit der eigendecomposition. Natürlich kommt es auf k an.

Noam Peled

Ja, mach es direkt. Die Ergebnisse der Neukomposition sind nicht spärlich, so dass Sie Speicherprobleme haben (andererseits ist A ^ k auch nicht, wenn k groß genug ist). Related stackoverflow.com/a/9495457/424631

dranxo

Antworten:

FILTLAN ist eine C ++ - Bibliothek zur Berechnung innerer Eigenwerte dünn besetzter symmetrischer Matrizen. Die Tatsache, dass es ein ganzes Paket gibt, das genau diesem Thema gewidmet ist, sollte Ihnen sagen, dass es ein ziemlich schweres Problem ist. Das Finden der größten oder kleinsten Eigenwerte einer symmetrischen Matrix kann durch Verschieben / Invertieren und Verwenden des Lanczos-Algorithmus erfolgen, die Mitte des Spektrums ist jedoch eine andere Sache. Wenn Sie dies verwenden möchten, können Sie mit SWIG ein C ++ - Programm aus Python aufrufen.

Wenn Ihr Endziel darin besteht, große Potenzen der Matrix zu berechnen, können Sie einfach Eigenvektoren berechnen, die den größten Eigenwerten entsprechen, da Sie wissen, dass die kleineren Moden weniger wichtig sind, wenn Sie große Potenzen verwenden.

$k$

Verzeihen Sie mir, wenn Ihnen dies bereits klar ist: Sie können die binäre Natur der Matrix ausnutzen, indem Sie numpy mitteilen, dass sie aus ganzen Zahlen anstelle von Gleitkommazahlen besteht, indem Sie beispielsweise verwenden

a = np.zeros(100,dtype=np.uint)

$A^{16}$ $A^2$ $A^4$ $A^8$ $\approx\log_2 k$ $k$

Sie können auch eine parallele, dünn besetzte, lineare Algebra-Bibliothek wie CUSP oder cuSPARSE von Python aufrufen, wenn Geschwindigkeit Ihr Anliegen ist und Sie eine NVIDIA-GPU haben.

Daniel Shapero
quelle

Ich möchte die Antwort von Daniel Shapero kommentieren, aber ich habe nicht genug SE-Reputation.

Die akzeptierte Antwort verwirrt mich sehr. Ich denke, Shift-Invert-Modus kann leicht verwendet werden, um innere Eigenwerte zu berechnen. Siehe: https://docs.scipy.org/doc/scipy/reference/tutorial/arpack.html

Um die ursprüngliche Frage zu beantworten: Es ist selten der Fall, dass Sie alle Eigenwerte einer großen, dünn besetzten Matrix wollen. Normalerweise möchten Sie Extreme oder eine Gruppe von inneren Werten. In diesem Fall ist eine Hermitianische Matrix eigshschneller. Für Nicht-Hermitianer müssen Sie mitgehen eigs. Und sie sind viel schneller als numpy eigoder eigh.

Alex
quelle