Komplexität der Matrixinversion in Numpy

Ich löse Differentialgleichungen, die das Invertieren dichter quadratischer Matrizen erfordern. Diese Matrixinversion nimmt den größten Teil meiner Rechenzeit in Anspruch, daher habe ich mich gefragt, ob ich den schnellsten verfügbaren Algorithmus verwende.

Meine aktuelle Wahl ist numpy.linalg.inv . Aus meiner Numerik geht hervor, dass es als skaliert, wobei n die Anzahl der Zeilen ist, daher scheint die Methode die Gaußsche Eliminierung zu sein. $O(n^3)$

Laut Wikipedia sind schnellere Algorithmen verfügbar. Weiß jemand, ob es eine Bibliothek gibt, die diese implementiert?

Ich frage mich, warum diese schnelleren Algorithmen nicht numpy sind.

numpy dense-matrix inverse PhysikGuy
quelle

Sie müssen Ihre Matrizen vorher ausführen. Schau dir Scipy an. Sparsam für Ihre Hilfe. Es enthält viele Werkzeuge, die Sie benötigen.

Tobal

@Tobal nicht sicher, ob ich folge ... wie würden Sie eine Matrix "durchführen"? und genau wie würde scipy.sparsehelfen?

GoHokies

@ GoHokies scipy ist eine Ergänzung zu numpy. Dichte / spärliche Matrizen müssen gut implementiert werden, bevor Sie einige Berechnungen durchführen. Dies verbessert Ihre Berechnungen. Bitte lesen Sie diese docs.scipy.org/doc/scipy/reference/sparse.html , die am besten erklärt als ich mit meinem schlechten Englisch.

Tobal

@Tobal Die Frage bezieht sich speziell auf dichte Matrizen, also sehe ich nicht, wie scipy.sparserelevant hier ist?

Christian Clason

@Tobal - Ich glaube ich verstehe immer noch nicht. Was genau meinen Sie mit "Vorformen Ihrer Matrizen" und "Matrizen müssen gut implementiert sein, bevor Sie einige Berechnungen durchführen"? In Bezug auf Ihren letzten Kommentar werden Sie sicherlich zustimmen, dass die Techniken, die für spärliche und dichte Matrizen verwendet werden können, sehr unterschiedlich sind.

Wolfgang Bangerth

Antworten:

(Dies wird zu lang für Kommentare ...)

Ich gehe davon aus, dass Sie tatsächlich eine Inverse in Ihrem Algorithmus berechnen müssen. ¹ Zunächst ist zu beachten, dass diese alternativen Algorithmen nicht als schneller gelten , sondern nur eine bessere asymptotische Komplexität aufweisen (was bedeutet, dass die erforderliche Anzahl von Elementaroperationen langsamer wächst). In der Praxis sind diese aus folgenden Gründen (viel) langsamer als der Standardansatz (für gegebenes ): $n$

Die -Notation Häute eine Konstante vor der Leistung von , die astronomisch groß sein können - so groß ist, daß kann viel kleiner als seine für jeden , dass kann in absehbarer Zeit von jedem Computer gehandhabt werden. (Dies ist beispielsweise beim Coppersmith-Winograd-Algorithmus der Fall.) $\mathcal{O}$ $n$ $C_1 n^3$ $C_2 n^{2.x}$ $n$
Die Komplexität setzt voraus, dass jede (arithmetische) Operation dieselbe Zeit benötigt - dies ist jedoch in der Praxis bei weitem nicht der Fall: Das Multiplizieren einer Reihe von Zahlen mit derselben Zahl ist viel schneller als das Multiplizieren derselben Anzahl unterschiedlicher Zahlen. Dies liegt an der Tatsache, dass der Hauptflaschenhals beim aktuellen Rechnen darin besteht, die Daten in den Cache zu bringen, nicht die tatsächlichen arithmetischen Operationen an diesen Daten. Ein Algorithmus, der neu angeordnet werden kann, um die erste Situation zu haben ( Cache-fähig genannt ), ist also viel schneller als einer, bei dem dies nicht möglich ist. (Dies ist beispielsweise beim Strassen-Algorithmus der Fall.)

Auch die numerische Stabilität ist mindestens so wichtig wie die Leistung. und auch hier gewinnt normalerweise der Standardansatz.

Aus diesem Grund implementieren die Standard-Hochleistungsbibliotheken (BLAS / LAPACK, die Numpy aufruft, wenn Sie ihn zur Berechnung einer Inversen auffordern) normalerweise nur diesen Ansatz. Natürlich gibt es Numpy-Implementierungen von z. B. Strassens Algorithmus, aber ein auf Assembly-Ebene von Hand abgestimmter -Algorithmus schlägt einen Algorithmus, der in einer höheren Sprache für jede vernünftige Matrixgröße geschrieben ist. $\mathcal{O}(n^3)$ $\mathcal{O}(n^{2.x})$

¹ Aber ich wäre falsch, wenn ich nicht darauf hinweisen würde, dass dies sehr selten wirklich notwendig ist: Immer wenn Sie ein Produkt berechnen müssen , sollten Sie stattdessen das lineare System lösen (z. using ) und stattdessen verwenden - dies ist viel stabiler und kann (abhängig von der Struktur der Matrix ) viel schneller durchgeführt werden. Wenn Sie mehrmals verwenden müssen, können Sie eine Faktorisierung von (die normalerweise der teuerste Teil der Lösung ist) vorberechnen und diese später wiederverwenden.

A^{- 1} b

$A^{-1}b$

A x = b

$Ax=b$ numpy.linalg.solve

x

$x$

A

$A$

A^{- 1}

$A^{-1}$

A

$A$

Christian Clason
quelle

Tolle Antwort, danke, Sir, insbesondere für den Hinweis auf den Teufel in den Details (Konstanten in großer O-Notation), die einen großen Unterschied zwischen theoretischer und praktischer Geschwindigkeit ausmachen.

gaborous

Ich denke, dass der Teil "Inverse ist selten notwendig" stärker betont werden sollte. Wenn der Zweck darin besteht, ein System von Differentialgleichungen zu lösen, scheint es nicht wahrscheinlich, dass eine vollständige Inverse erforderlich ist.

Jared Goguen

@o_o Nun, das war mein erster ursprünglicher Kommentar (den ich gelöscht habe, nachdem ich sie alle zu einer Antwort zusammengefasst hatte). Aber ich dachte, zum Nutzen der Website (und späterer Leser) sollte eine Antwort die eigentliche Frage in der Frage beantworten (die sowohl vernünftig als auch thematisch ist), selbst wenn ein XY-Problem dahinter steckt. Außerdem wollte ich nicht zu mahnend klingen ...

Christian Clason

Wie ich geschrieben habe, können Sie Ihren Algorithmus in fast allen Fällen neu schreiben, um Operationen mit der Umkehrung durch das Lösen des entsprechenden linearen Systems (oder in diesem Fall der Folge linearer Systeme) zu ersetzen. Wenn Sie interessiert sind, können Sie eine separate Frage zu stellen das ("Kann ich das Invertieren von Matrizen in diesem Algorithmus vermeiden?"). Und ja, da die Anzahl der Matrizen nicht von abhängt , ist die Komplexität immer noch dieselbe (Sie erhalten nur eine größere Konstante - in Ihrem Fall um den Faktor vier).

n

$n$

Christian Clason

@ Heisenberg: Abhängig von der Struktur von - LU, Cholesky oder sogar QR - Zerlegungsarbeiten. Der Punkt (der in jedem Text zur numerischen linearen Algebra gemacht wird) ist, dass das Anwenden der Zerlegung im Vergleich zum Berechnen billig ist, so dass Sie letztere nur einmal ausführen und sie dann viele Male anwenden.

A

$A$

Christian Clason

Sie sollten wahrscheinlich beachten, dass die inv-Routine versucht, die Funktion dgetrf aufzurufen, die tief im numpy-Quellcode vergraben ist (siehe https://github.com/numpy/numpy/blob/master/numpy/linalg/umath_linalg.c.src ) aus Ihrem System-LAPACK-Paket, das dann eine LU-Zerlegung Ihrer ursprünglichen Matrix durchführt. Dies entspricht moralisch der Gaußschen Eliminierung, kann jedoch durch Verwendung schnellerer Matrixmultiplikationsalgorithmen in einem Hochleistungs-BLAS auf eine etwas geringere Komplexität eingestellt werden.

Wenn Sie dieser Route folgen, sollten Sie gewarnt werden, dass es ziemlich komplex ist, die gesamte Bibliothekskette zu zwingen, die neue Bibliothek anstelle der mit Ihrer Distribution gelieferten Systembibliothek zu verwenden. Eine Alternative auf modernen Computersystemen besteht darin, parallelisierte Methoden mit Paketen wie scaLAPACK oder (in der Python-Welt) petesc4py zu untersuchen. Diese werden jedoch in der Regel eher als iterative Löser für lineare Algebra-Systeme verwendet als für direkte Methoden, und PETSc zielt insbesondere auf spärliche Systeme ab, die dichter sind als auf dichte.

Origimbo
quelle