Helmut Podhaisky

Parallele Zweischritt-W-Methoden

Dissertation zur Erlangung des akademischen Grades doctor rerum naturalium (Dr. rer. nat.) vorgelegt an der Mathematisch-Naturwissenschaftlich-Technischen Fakultät der Martin-Luther-Universität Halle-Wittenberg
verteidigt am 10.01.2002

Abstract
In der Arbeit werden parallele Zweischritt-W-Methoden (engl. parallel two-step W-methods, PTSW-methods) für die numerische Lösung steifer Differentialgleichungssysteme entwickelt. PTSW-Verfahren sind parallel bezüglich der Methoden und können daher ohne zusätzlichen Nutzeraufwand auf einem Parallelrechner eingesetzt werden. PTSW-Verfahren besitzen s externe, linear-implizite Stufen, die vollständig parallel berechnet werden können.
Aus der Analyse der lokalen Fehler leiten wir vereinfachende Bedingungen her, aus denen die Konvergenz der Verfahren folgt. Dabei können hohe Ordnungen und Stufenordnungen erreicht werden. Wir zeigen die Existenz L-stabile Verfahren hoher Ordnung mit bis zu 12 Stufen. Ausführlich diskutieren wir die Konstruktion von zwei- drei- und vierstufigen Verfahren. Die Implementierung der PTSW-Verfahren mit Schrittweitensteuerung und Krylovapproximation wird ausführlich beschrieben. Für die Parallelisierung der Methoden verwenden wir shared-memory Direktiven in OpenMP. In numerischen Tests vergleichen wir PTSW-Verfahren mit Standardintegratoren. Für Probleme kleiner Dimension aus dem CWI-Testset verwenden wir zur Lösung der linearen Gleichungssysteme LU-Zerlegung (mittels LAPACK) und vergleichen mit RADAU. Für große steife Probleme, die durch Semidiskretisierung von Reaktions-Diffusions-Gleichungen entstanden sind, setzen wir die Methode der vollständigen Orthogonalisierung (FOM, Arnoli-Algorithmus) ein und vergleichen mit dem BDF-Code VODPK (GMRES). Für viele Beispiele sind die PTSW-Verfahren bereits sequentiell konkurrenzfähig mit den Standardintegratoren. Für große Beispiele erreichen wir gute Speedups.

We derive a new type of parallel time-integration methods for large stiff ODE systems: parallel two-step W-methods, PTSW-methods. Our methods possess s linearly implicit stages which can be computed in parallel using s processors. Note that the parallelism is hidden within the solver (black-box) and additional no effort from the user is needed.
We study the local errors of our methods by means of Taylor series expansion and derive simplifying conditions which guarantee convergence. We can attain the order s and stage order s with an s-stage PTSW-method. We show the existence of L-stable PTSW-methods up to 12 stages. The construction of methods for practical use with two, three and four stages is discussed in detail. We describe the implementation of the PTSW-methods with step size control and Krylov approximation. For parallelization we use OpenMP shared memory directives. In numerical tests we compare with the implicit Runge-Kutta-Code RADAU and the Krylov-methods VODPK based on BDF methods. We consider standard test problems taken from the CWI IVP-testset as well as semidiscretized reaction diffusion problems where we use Krylov approximation (fully orthogonalization method, FOM). Our code performs well. PTSW-methods are competitive with the references method already in sequential mode. Due to the parallelization we outperform VODPK in most examples where we use Krylov approximation.

Keywords:
Parallelität bezüglich des Systems, Krylov-W-Methoden, Steife Differentialgleichungssysteme, Zweischritt Runge-Kutta-Verfahren, Arnoldi-Algorithmus

parallelism across the system, Krylov-W-method, stiff ODE system, two-step Runge-Kutta, Arnoldi's algorithm

Online-Dokument im PDF-Format (841 KB) mit integrierter Gliederung.

Inhaltsverzeichnis
Inhaltsverzeichnis, Abkürzungen und Symbole (i-iii)
1 Einleitung (1-2)
2 Parallele Zweischritt-W-Methoden (3-14)
3 Konstruktion von Parametersätzen (15-34)
4 Implementierung von PTSW-Verfahren (35-46)
5 Numerische Tests (47-58)
6 Zusammenfassung und weiterführende Bemerkungen (59-60)
Literatur (61-64)
A Maple-Skripte (65-69)