Wie löst LAPACK tridiagonale Systeme und warum?

9

In meinem Projekt muss ich bei jedem Zeitschritt ein paar tridiagonale Matrizen lösen, daher ist es wichtig, einen guten Löser für diese zu haben. Ich habe meine eigene Implementierung gemacht, nur die klassische Art, wie es auf Wikipedia beschrieben wird. Ich habe dann versucht, stattdessen Lapack zu verwenden, und zu meiner Überraschung war es langsamer!

In Lapack scheint es so, als würde es durch LU-Faktorisierung gelöst, und ich frage mich, warum es nicht komplexer ist, als es sein könnte.

Zusätzlich habe ich im Buch "Numerical Recipes" von nr.com einen Algorithmus gefunden, der das System rekursiv in kleinere tridiagonale Probleme unterteilt. Es sah vielversprechend aus. Gibt es noch andere Leckereien da draußen?

Update: Die Problemgröße beträgt ca. 1000x1000. Ich habe GotoBLAS verwendet, es gibt Ihnen auch eine Lapack 3.1.1-Bibliothek. Das Problem ist nicht symmetrisch. Ich habe die Lapack-Routine für allgemeine tridiagonale Matrizen verwendet.

banded-matrix lapack tiam
quelle
2
Sie müssen angeben, welche LAPACK-Routinen Sie dafür verwendet haben. Beachten Sie, dass dgtsv teilweise schwenkt, Ihr Code dies jedoch möglicherweise nicht tut. Bitte geben Sie auch an, mit welcher LAPACK-Implementierung Sie getestet haben und mit welchen Problemgrößen Sie ein Benchmarking durchgeführt haben. Ist Ihr Problem symmetrisch positiv definitiv?
Jed Brown
Ich habe einige Informationen in die Fragenformulierung aufgenommen.
Tiam
Hat Ihre Anwendung etwas mit Finite-Volume-Methoden zu tun?
Untersuchung
Es sind endliche Unterschiede, aber in dieser Perspektive ist es mehr oder weniger dasselbe, denke ich.
Tiam

Antworten:

6

Sie verwenden eine Referenzimplementierung, die teilweise schwenkt. Tridiagonale Lösungen machen sehr wenig Arbeit und rufen nicht in die BLAS auf. Es ist wahrscheinlich langsamer als Ihr Code, da es teilweise schwenkt. Der Quellcode für dgtsv ist unkompliziert.

Wenn Sie mehrmals mit derselben Matrix lösen, möchten Sie die Faktoren möglicherweise mithilfe von dgttrf und dgttrs speichern . Es ist möglich, dass die Implementierungen in einem optimierten LAPACK wie MKL, ACML oder ESSL leistungsfähiger sind.

Jed Brown
quelle
Ich bin ein bisschen neugierig. Gaussian Elim mit PP würde für alle Matrizen einschließlich TriDiagonal funktionieren. In CFD verwenden wir eine spezielle Methode für FVM 1D-Fälle namens TDMA . Was ist Ihrer Meinung nach schneller für den Fall, über den er spricht? Obwohl ich nicht ganz sicher bin, ob seine Matrizen diagonal dominant sind.
Untersuchung
Das TDMA habe ich in meinem Code implementiert. Die Frage ist, warum der superschnelle Lapack das partielle Schwenkverfahren in einer solchen bestimmten Matrix verwenden würde, die durch eine so einfache Methode wie TDMA schneller gelöst wird.
Tiam
Es ist genau derselbe Algorithmus (Gaußsche Eliminierung, spezialisiert auf eine tridiagonale Matrix), aber Ihre Implementierung führt kein partielles Schwenken durch, sodass sie möglicherweise numerisch instabil ist. Das Schwenken ist nicht kostenlos und Sie vergleichen mit der Referenzimplementierung. Die Referenzimplementierung ist nicht für die Leistung optimiert und das teilweise Schwenken ist nicht frei.
Jed Brown
Ich verstehe, was Sie meinen, ich profitiere von meinem Wissen über die Systeme, die ich löse. Bieten andere Implementierungen von LAPACK Leistungssteigerungen aufgrund der Anpassung an eine bestimmte Architektur oder gehen sie darüber hinaus?
Tiam