Effiziente Implementierung eines Tridiagonal-Matrix-Algorithmus

12

Ich löse ein physikalisches Problem mit Hilfe eines impliziten numerischen Schemas. Dies führt mich zur Lösung einer linearen Gleichung mit einer tridiagonalen Matrix. Ich habe diesen Algorithmus von Wikipedia codiert . Ich frage mich, ob es eine effiziente Bibliothek gibt, die es ermöglicht, diese Art von Gleichung auf optimierte Weise zu lösen. Ein wichtiger Hinweis ist, dass sich die Matrix selbst nur ändert, wenn sich die Systemparameter ändern. Daher hatte ich die Möglichkeit, einige Algorithmusschritte vorab zu berechnen, um einen schönen Leistungsbonus zu erzielen. Ich benutze C ++.

gmk
quelle
Wie groß ist ein System, muss es parallel sein?
Aterrel
1
Die Größe hängt von der erforderlichen Genauigkeit ab (von Hundert bis Zehntausenden von Werten). Jetzt codiere ich auf einem Ein-Kern-Computer, aber es ist möglich, auf einen Universitäts-Supercomputer mit vielen verfügbaren CPUs zuzugreifen, so dass Parallelitätsunterstützung nett wäre.
GMK

Antworten:

15

Sie sollten wahrscheinlich mit der LAPACK-Implementierung beginnen, zB gtsv , dgtsv . Wenn Sie eine Version mit verteiltem Speicher möchten, sollten Sie mit dem p? Gtsv von ScaLAPACK beginnen.

EDIT: Da sich Ihre Matrix nicht sehr oft ändert, können Sie das redundante Zerlegen der tridiagonalen Matrix vermeiden, indem Sie die LAPACK-Routine? Gtsv in den Faktorisierungsschritt? Gttrf und den Auflösungsschritt? Gttrs aufteilen. In ScaLAPACK gibt es ähnlich benannte Routinen, die denselben Zweck erfüllen.

Jack Poulson
quelle
Danke, es sieht aus wie was ich brauche. Ich werde jetzt versuchen, diese Routinen aus meinem Code auszuführen.
GMK
1
Da Sie es von C ++ aus aufrufen, müssen Sie den Prototyp in einem externen "C" {} -Block deklarieren. Abhängig von Ihrem System müssen Sie möglicherweise einen Unterstrich an den Routinennamen anhängen.
Jack Poulson
2

Für verteilte Parallelsysteme : Ich habe ScaLAPACK nicht ausprobiert, da es einen parallelen Tridiagonal-Solver gibt, für den es online Beispiele gibt . Ich habe mit einigem Erfolg eine von David Moulton in einer LANL-Veröffentlichung vorgeschlagene Methode ausprobiert . Das zu verschlüsseln mag mehr sein, als Sie wollen, aber mit LAPACK ist es geradeaus.

Yann
quelle
1

Ich habe hier auf Seite 975 einen interessanten rekursiven Algorithmus gefunden . Er sieht vielversprechend aus. Ich frage mich, was erfahrenere Leute dazu sagen.

tiam
quelle
Numerical Recipes enthält einige Fehler. In Bezug auf die Quelle der zu verwendenden Codes ist es nicht das Beste, obwohl einige es für einen Klassiker halten. Es würde mich wundern, wenn ScaLAPACK keinen Algorithmus implementieren würde, der mindestens so effizient ist wie die rekursive zyklische Reduktion.
Geoff Oxberry