Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation
maximize
[1] G. W. Zumbusch. Adaptive parallele Multilevel-Methoden zur Lösung elliptischer Randwertprobleme. Technical Report 342/19/91 A, SFB 342, TU München, Munich, Germany, 1991.
bib | .ps.gz 1 | .pdf 1 ]
Multilevel Methoden sind die zur Zeit effizientesten Verfahren zur Lösung großer linearer Gleichungssysteme, die aus der Diskretisierung elliptischer Randwertprobleme entstehen. Der Aufwand, mit Mehrgitterverfahren oder auch mit multilevel vorkonditionierten Verfahren der konjugierten Gradienten (CG) im symmetrisch positiv definiten Fall ein Gleichungssystem bis auf Diskretisierungsgenauigkeit zu lösen, ist unter geeigneten Voraus- setzungen proportional zur Zahl der Unbekannten oder nur um einen logarithmischen Term höher. ...
Die Ausführungsgeschwindigkeit kann durch adaptive Verfeinerungs- techniken, die die Zahl der notwendigen Unbekannten reduzieren, erhöht werden. Dazu existieren vollständige Programmpakete, wie PLTMG [Bank] und Kaskade [Leinen], [Deuflhard, Leinen, Yserentant], die die Ordnung des eingebauten iterativen Lösers durch Gitterverwaltung, Verfeinerung und Gittermanipulation nicht verschlechtern. Die Ordnung des Lösungsverfahrens kann nur durch parallele Ausführung gesenkt werden. In Hinblick auf sehr große lineare Gleichungssysteme, wie sie insbesondere auch durch Randwertprobleme in drei Raumdimensionen entstehen, liegt es nahe, beide Techniken zu verbinden. Bei der Lastverteilung adaptiv, also dynamisch erzeugter Strukturen, können allerdings nicht mehr alle Vorraussetzungen an die Finiten-Elemente-Räume und alle Algorithmen zur Gittermanipulation vom sequentiellen Programm übernommen werden. Existierende Ansätze, wie [Fox & Otto], [Berger & Bokhari] und [Bastian] führen zu Verfahren, deren Ordnung höher als die des iterativen Lösers ist, und nutzen die Multilevel-Struktur der Gitter nicht aus. Ansätze zur Parallelisierung von Standard-Mehrgitterverfahren wie [Briggs, Hart, McCormick & Quinlan] oder von adaptiven Mehrgitterverfahren wie [Mierendorff] können in dieser Form nicht auf adaptive Verfahren angewendet werden, obwohl sie für regulär verfeinerte Gitter optimale Ergebnisse liefern. ...
Wir werden im folgenden Parallelrechner mit verteiltem Speicher und Message-Passing-Kommunikation und Parallelrechner mit gemeinsamem Speicher und Semaphor-Synchronisation verwenden, um ein multilevel- vorkonditioniertes CG-Verfahren so zu implementieren, daß die Eigenschaften des sequentiellen Programms, soweit möglich, erhalten bleiben, und gleichzeitig eine effiziente Parallelisierung erreicht wird.