Der schnellste Weg, um ein lineares Gleichungssystem zu lösen

Ich muss ein System von bis zu 10000 Gleichungen mit 10000 Unbekannten so schnell wie möglich lösen (vorzugsweise innerhalb weniger Sekunden). Ich weiß, dass die Gaußsche Eliminierung dafür zu langsam ist. Welcher Algorithmus ist also für diese Aufgabe geeignet?

Alle Koeffizienten und Konstanten sind nicht negative ganze Zahlen modulo p (wobei p eine Primzahl ist). Es gibt garantiert nur 1 Lösung. Ich brauche die Lösung modulo p.

Eine LU-Zerlegung einer Matrix kann in O ( M ( n ) ) -Zeit berechnet werden, wobei M ( n ) die Zeit zum Multiplizieren von zwei n × n- Matrizen ist. Daher können Sie eine Lösung für ein System von n linearen Gleichungen in n Unbekannten in O ( M ( n ) ) Zeit finden. Zum Beispiel Strassen-Algorithmus erreicht , M ( n ) = O $n \times n$$O(M(n))$$M(n)$$n \times n$$n$$n$$O(M(n))$ , was schneller ist als die Gaußsche Eliminierung. Siehehttps://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion.$M(n) = O(n^{2.8})$

Anstatt dies selbst zu implementieren, würde ich vorschlagen, eine Bibliothek zu verwenden: z. B. eine BLAS-Bibliothek.

Es gibt das, was Sie erreichen wollen, und es gibt die Realität, und manchmal stehen sie in Konflikt. Zuerst prüfen Sie, ob es sich bei Ihrem Problem um einen Sonderfall handelt, der schneller gelöst werden kann, z. B. eine spärliche Matrix. Dann suchen Sie nach schnelleren Algorithmen; Die LU-Zerlegung endet etwas schneller. Dann untersuchen Sie, was Strassen für Sie tun kann (was nicht sehr viel ist; es kann die Hälfte der Operationen einsparen, wenn Sie die Problemgröße mit 32 multiplizieren).

Und dann wenden Sie rohe Gewalt an. Verwenden Sie ein Multiprozessorsystem mit mehreren Threads. Verwenden Sie verfügbare Vektoreinheiten. Ordnen Sie Ihre Daten und Vorgänge so an, dass sie cachefreundlich sind. Untersuchen Sie, was der schnellste Weg ist, um modulo p für ein festes p zu berechnen. Und Sie können Operationen häufig speichern, indem Sie keine Operationen modulo p ausführen (Ergebnis im Bereich 0 ≤ Ergebnis <p), sondern etwas entspannter (z. B. Ergebnis im Bereich -p <Ergebnis <p).

Der beste Weg, um große lineare Gleichungen zu lösen, besteht darin, Parallelisierung zu verwenden oder Berechnungen auf CPUs oder so zu verteilen.

Siehe CUDA, OpenCL, OpenMP.

Viele Leute schlagen vor, Strassen's algorithmaber es hat eine sehr große versteckte Konstante, die es ineffizient macht.

Übrigens: Ihre linearen Gleichungen sind möglicherweise sehr spärlich (viele Nullen), es gibt nur wenige sehr nette Optimierungen, um sie parallel zu lösen.