Welcher spärliche lineare Löser ist schneller? SparseLU oder BiCGSTAB?

Question

Ich habe die SparseLU- und BicGSTAB-Methode von Eigen auf einer spärlichen Matrix getestet, deren Dichte von 3000 * 3000 bis 16000 * 16000 reicht. Alle Fälle zeigen, dass SparseLU etwa 13% schneller ist als die BicGSTAB-Methode.

Ich habe dem BiCGSTAB keine RowMajor Sparse-Matrix zugeführt, oder gebe ihm keine Vorkonditionierer. Das könnte der Grund für langsam sein.

Also ich frage mich, ob ich beide Methoden gut mache, welche sollte man schneller sein?

Wie wäre es, wenn die Matrixgröße auf Millionen * Millionen ansteigt?

Vielen Dank!

Answer 1

Die Leistung von direkten und iterativen Methoden wird von ganz anderen Faktoren beeinflusst. Betrachten Sie symmetrische, positiv definite Matrizen. Für eine direkte Methode ist der wichtigste Faktor: Um die bestmögliche Permutation der Zeilen und Spalten zu finden, so dass die faktorisierte Matrix eine so geringe Anzahl neuer Nicht-Null-Elemente hätte (sogenannte "Fill-Ins") wie möglich. Für eine iterative Methode ist der wichtigste Faktor die Verteilung der Eigenwerte. Zum Beispiel erfordert die konjugierte Gradientenmethode (vorausgesetzt, dass alle numerischen Operationen exakte Zahlen liefern), um so viele Iterationen wie viele verschiedene Eigenwerte, die die Matrix hat, vollständig zu konvergieren. Für jedes spezielle physikalische Problem (das zum Beispiel durch die Finite Differenz oder durch die Finite-Elemente-Methode gelöst wird) kann die entsprechende Matrix Eigenschaften haben, die so einfach sind, dass es keine Möglichkeit gibt, vorherzusagen: welcher Ansatz (dh direkt oder iterativ) würde Ergebnisse schneller als die anderen liefern. Für Systeme linearer Gleichungen, die aus Millionen von Gleichungen bestehen, wäre wahrscheinlich ein iterativer Ansatz vorzuziehen, nur weil keine neuen Elemente ungleich Null in der Matrix erscheinen. Als ein Beispiel für ein System, das aus Millionen von Gleichungen besteht, die durch einen iterativen Algorithmus gelöst werden, schlage ich vor, dass Sie sich das Problem anschauen, das im folgenden Link dargestellt ist (dies ist ein typisches FEA-Problem mit sehr feinem Finite-Elemente-Netz, führt zu einem System von 3,5 Millionen Gleichungen): http://members.ozemail.com.au/~comecau/CMA_Sparse.htm

Answer 2

Sie haben bereits den Hauptgrund für den Leistungsunterschied erwähnt. Die iterativen Methoden werden viel schneller, wenn Sie den "richtigen" Vorkonditionierer wählen.

Ein Beispiel Liste der Vorkonditionierern Sie ist verweisen könnten:

• Jacobi
• SOR
• ILU
• Mehrgitter

Jeder Vorkonditionierer hat einige Parameter sollten die auch abgestimmt werden .

Answer 3

Die Wahl des linearen Lösers hat viel mit der Verteilung von Eigenwerten/Eigenvektoren der Matrix zu tun. Wenn Sie eine symmetrische positiv definite Matrix haben, ist der konjugierte Gradient eine gute Option. Die Anzahl der Iterationen hängt von der Konditionsnummer ab (max Eigenwert/min Eigenwert). Bei einer Matrix, die von einem elliptischen Operator abgeleitet wird, erhöht sich die Zustandsnummer mit der Größe der Matrix.

Werfen Sie einen Blick auf diesen Artikel von Jonathan Shewchuk für eine großartige Erklärung zu CG.().

Für andere Matrixtypen können Sie GMRES usw. verwendenbasierend auf den Eigeneigenschaften. Sehen Sie sich dieses Papier an http://www.sam.math.ethz.ch/~mhg/pub/biksm.pdf

Hoffe, dass dies hilft.