Bibliothek zum Lösen eines großen dünnbesetzten linearen Gleichungssystems $Ax=b$ (fast gebänderte Matrix)

Ich suche ein Tool oder eine Bibliothek, die einen schnellen Algorithmus in C oder JAVA implementiert, um die Gleichung $Ax=b$ zu lösen, wobei $A$ eine $N*N$ Sparse-Matrix mit $5$ Diagonalen ungleich Null ist $(- N,-1,0,1,N)$.

Mein Problem ist, dass $N$ wirklich groß ist ($N$ kann $1-5e7$ erreichen).

Ich löse es jetzt in Matlab, aber es ist wirklich langsam, also suche ich nach anderen Methoden in anderen Sprachen, um es schneller zu machen.

aktualisieren:

Entschuldigung für den Mangel an Informationen, ich werde meine Frage aktualisieren und versuchen, mein Problem zu klären.

Ich löse numerisch die 2D-Laplace-Gleichung auf einer rechteckigen Domäne (die Schwierigkeit kann sich aus den Abmessungen des Rechtecks ​​ergeben - 1 mm * 100 nm) mit gemischten Randbedingungen.

Neumann-Grenze auf der linken und unteren Seite, Dirichlet-Grenze auf der oberen Seite und auf der rechten Seite die Ableitung gleich einer Funktion.

Mit der Finite-Differenzen-Methode erhalte ich die Matrix A mit 5 Diagonalen (jeder Punkt ist mit seinen 4 Nachbarn und sich selbst gekoppelt).

Ich habe alle integrierten Funktionen in Matlab zum Lösen linearer Gleichungen einschließlich "bicgstab" ohne Erfolg ausprobiert (die Lösung explodiert).

Der Backslash-Operator mit einer Matrix von N*N (wobei N=5e7) dauert etwa 13 Minuten hin oder her.

Hier ist ein Beispiel für die Matrix mit N=36.Geben Sie hier die Bildbeschreibung ein

Wie löst du das in Matlab? Wie lange dauert es in Matlab? Wie viele Gigabyte Speicher belegt $A$?
Werfen Sie einen Blick auf hindawi.com/journals/mpe/2015/232456 . Es könnte von Interesse sein. arxiv.org/pdf/1409.4802.pdf enthält Details zur Leistung.
In Matlab habe ich eine Sparse-Matrix $A$ mit $5 \times 10^7$ Zeilen, $5 \times 10^7$ Spalten und fünf Diagonalen ungleich Null erstellt und ich habe $Ax = b$ mit dem Backslash-Operator in 20 Sekunden gelöst . Ist das ähnlich zu dem, was Sie beobachten?
Kommt drauf an wie spärlich es ist. Wenn die Bandbreite $O(\sqrt{N})$ ist, dann wäre es wirklich schwierig.
Vielleicht möchten Sie etwas über die Bandstruktur oder die fast gebänderte Matrix in den Titel schreiben - eine dünne Matrix ist viel allgemeiner.
Hallo Dor und willkommen bei SR! Könnten Sie bitte Ihre Frage bearbeiten und einige Details zu den Lizenz-/Kostenanforderungen hinzufügen (z. B. muss sie kostenlos verfügbar sein, muss die Lizenz die kommerzielle Nutzung zulassen usw.)? Je besser Sie Ihre Anforderungen beschreiben, desto genauer können die Antworten übereinstimmen. Eine Richtlinie finden Sie unter Was ist erforderlich, damit eine Frage „genügend Informationen“ enthält? Viel Glück und Daumen drücken!
Es gibt keine Super- oder Subdiagonale mit dem Index $N$ in einer $N$-mal-$N$-Matrix. Der größte relevante Index ist $N-1$. Ist Ihre Matrix wirklich tridiagonal mit einer möglichen Nichtnull bei $a_{1,N}$ und $a_{N,1}$?
Ich habe meine Frage aktualisiert, um mein Problem zu klären. beim Lösen mit N=1e7 brauche ich 13 Minuten. $A$ sind 150 MB.

Antworten (1)

Die Notation ist mir nicht klar, aber unter der Annahme, dass die Diagonale Null ist, die erste Superdiagonale aus Kopien von 1 besteht, die zweite Superdiagonale aus Kopien von N besteht und diese Matrix antisymmetrisch ist, dann ist die Matrix A singulär für ungerade N .

Wenn meine ursprüngliche Interpretation der Notation richtig ist, dann ist die Matrix B auch singulär für ungerade N.

Auf der positiven Seite ist dies eine der schönsten Testmatrizen, mit denen ich seit einiger Zeit gespielt habe.

A=@(N)toeplitz([0 1 N Nullen(1,N-3)],[0 -1 -N Nullen(1,N-3)]);

B=@(N)toeplitz([0 1 Nullen(1,N-3) N],[0 -1 Nullen(1,N-3) -N]);

Insbesondere die reduzierte Zeilenstufenform von B ist am unterhaltsamsten.

Und was genau ist die Bibliothek, die Sie empfehlen?
@ThomasWeller: Es gibt keine Empfehlung. Die Matrizen sind singulär für ungerade N. Das OP wollte Software, die mit jedem N umgehen kann. Diese Software existiert nicht. Was gerettet werden kann, ist eine überraschend schöne Klasse von Testmatrizen A=A(N), für die A(2k) eine langsam wachsende Bedingungszahl hat, während A(2k+1) singulär ist.
Ich gestehe, ich habe keine Ahnung, wovon OP spricht. Ich habe auch keine Ahnung, wovon du sprichst. Auf dieser Seite geht es um Softwareempfehlungen. Wenn es keine zu empfehlende Software gibt, weil zB eine mathematische Antwort immer 42 ist, dann würde ich sagen, dass die Frage nicht zum Thema gehört und geschlossen werden sollte, weil sie keinen Forschungsaufwand zeigt.
Bibliothek zum Lösen eines großen dünnbesetzten linearen Gleichungssystems $Ax=b$ (fast gebänderte Matrix)
AntwortenHierDatenschutz-Bestimmungen1y, 0v