Ist der Thomas-Algorithmus der schnellste Weg, um ein symmetrisch diagonal dominantes spärlich tridiagonales lineares System zu lösen?

Ich frage mich, ob der Thomas-Algorithmus (nachweislich?) Der schnellste Weg ist, ein symmetrisch diagonal dominiertes, dünn besetztes tridiagonales System in Bezug auf die algorithmische Komplexität zu lösen (ohne nach Implementierungspaketen wie LAPACK usw. zu suchen). Ich weiß, dass sowohl der Thomas-Algorithmus als auch das Multigrid -Komplexität haben, aber vielleicht ist der konstante Faktor für Multigrid geringer? Es scheint mir nicht, dass Multigrid schneller sein könnte, aber ich bin nicht positiv. $O(n)$

Hinweis: Ich denke an den Fall, dass die Matrizen sehr groß sind. Es sind entweder direkte oder iterative Methoden zulässig.

linear-solver sparse-matrix complexity multigrid James
quelle

Antworten:

Ich glaube, ein Vergleich einer iterativen Methode (Multigrid) mit einer direkten / genauen Methode (Thomas) in Bezug auf die genaue Anzahl der Operationen ist nicht wirklich aussagekräftig. IIRC, Thomas Operation Count ist für jedes tridiagonale System. Das einzige Mal, dass ich mir vorstellen kann, dass Multigrid-Schläge für einen trivialen Fall einer linearen Lösung geeignet sind, und selbst dann wären die Kosten für die Bewertung des Residuums auf jeder Ebene mit den Kosten von Thomas vergleichbar. $8N$

Die -Nützlichkeit von Multigrid liegt in der Tatsache, dass es allgemein für spärliche Matrizen gilt und nicht auf tridiagonale Systeme beschränkt ist. $O(N)$

Aurelius
quelle

Vielen Dank. Mir ist klar, dass iterative Methoden nicht genau sind. Ich hätte eine sehr kleine Toleranz angeben sollen (sagen wir 10 ^ -15) und dies nur zu Vergleichszwecken als "genau" behandeln sollen.

James

@ user2697246 naja, du hast nach dem "nachweislich" schnellsten gefragt. Die genaue Konvergenzrate für Multigrid (oder ein beliebiges iteratives Schema) hängt immer von der Lösung selbst und der Ausgangsschätzung ab - eine lineare Lösung wird effektiv genau in einem Schritt gelöst, wohingegen etwas Oszillierenderes mehr Operationen erfordert. Thomas hat eine genaue, feste Operationsanzahl für alle Fälle. In der Praxis werden Sie niemals Thomas schlagen, wenn Sie ein tridiagonales System für einen nicht-trivialen Fall (seriell) lösen.

Aurelius

@Aurelius Kann der Thomas-Algorithmus parallelisiert werden? Wenn nicht, ist das ein großer Vorteil von Multigrid!

Nick Alger

@NickAlger Nein, der Thomas-Algorithmus ist streng seriell, und ja, Parallelisierung ist ein großer Vorteil für Multigrid-Systeme (obwohl ich für den speziellen Fall eines tridiagonalen Systems vermute, dass die Kommunikationslatenz Sie töten würde.) Reduktion (PCR) ist

, parallelisierbar mit

, das ich erfolgreich auf GPUs eingesetzt habe.

O (N l o g N)

$O(N log N)$

N

$N$

Aurelius

Eine Korrektur, der Thomas-Algorithmus, erfordert 8N Operationen, nicht 9N. Was meinen Sie mit "Multigrid ... mit einer linearen Lösung"? Alle hier betrachteten Systeme sind linear.

Doug Lipinski

Die kurze Antwort lautet, dass der Thomas-Algorithmus in fast allen Fällen schneller ist als jedes iterative Schema. Die Ausnahme wäre vielleicht die Anwendung einer einzelnen Iteration eines sehr einfachen iterativen Schemas wie Gauß-Seidel, aber es ist sehr unwahrscheinlich, dass dies eine akzeptable Lösung ergibt. Dies ignoriert auch Parallelverarbeitungsprobleme.

$\mathcal O(n)$ $\mathcal O(n)$

$5N$ $3N$ $3N-2$ $2N-2$

Doug Lipinski
quelle

"Multigrid ist eine besonders schlechte Wahl im Fall einer dreieckigen Matrix, da Multigrid zwar O (n) ist, die Konstante aber ziemlich groß ist." Ich denke das auch, aber Googeln brachte eine Zeile in Trottenburgs Multigrid-Buch hervor, in der eine Konstante von 0,1-0,2 angegeben wurde, ohne dass Beweise vorlagen. Ich glaube nicht, dass ich das glaube.

Aurelius

@ Aurelius Interessant. Dies ist im allgemeinen Fall eindeutig unmöglich, da eine tridiagonale Matrix 3N Einträge enthält. Wenn die Kosten ~ 0,1 * N betragen, bedeutet dies, dass Sie die meisten Einträge nicht einmal bearbeiten.

Doug Lipinski

Ja, wir sind auf derselben Seite. Das einfache Auswerten einer 3-Punkt-Schablone erfordert 3N-Operationen. Ich habe nur überflogen, also habe ich die Aussage vielleicht völlig falsch interpretiert, aber Sie können es selbst in den Google Books-Auszügen sehen.

Aurelius

Das vollständige Zitat (S. 21) lautet: "Effizienz im praktischen Sinne bedeutet, dass die Proportionalitätskonstanten in dieser O (N) -Anweisung klein oder moderat sind. Dies ist in der Tat für Multigrid der Fall: Wenn gut ausgelegt, können die h-unabhängigen Konvergenzfaktoren sehr klein gemacht werden (im Bereich von 0,1-0,2 oder noch weniger) und die Anzahl der Operationen pro unbekanntem Iterationsschritt ist ebenfalls klein. " Der Wert 0,1-0,2 bezieht sich auf die Restverringerung für jeden Mehrgitterzyklus. Die Konstante für O (N) würde in der Größenordnung von 1,5 bis 2,0 x der Matrixmultiplikation pro Zyklus liegen (mit insgesamt einem Dutzend oder zwei Zyklen).

Godric Seer

Ah, danke @GodricSeer, das macht mehr Sinn.

Aurelius

Multigrid-Schleifen auch auf einem Kern können vom Optimierer vektorisiert werden. Obwohl die Anzahl der Vorgänge hilfreich sein kann, sollten wir nicht vergessen, dass Prozessoren auch in der seriellen Welt Vektorparallelität aufweisen und daher die Zeit bis zur Lösung möglicherweise nicht genau das ist, was wir aus der Kostenanalyse vorhersagen.

Hasbestein
quelle