title: Die Parallelisierung des filternden algebraischen Mehrgitterverfahrens zum Lösen partieller Differentialgleichungen
creator: Wrobel, Christian
subject: ddc-510
subject: 510 Mathematics
description: In dieser Doktorarbeit wird das neue robuste und effiziente parallele algebraische Mehrgitterverfahren pFAMG zum Lösen von partiellen Differentialgleichungen präsentiert. Der aktuelle Stand der Forschung für parallele und robuste Lösungsverfahren für partielle Differentialgleichungen wird zusammengefaßt; dies umfaßt vor allem parallele geometrische und algebraische Mehrgitterverfahren (AMG). Zwei Einsatzgebiete für algebraische Mehrgitterverfahren werden herausgearbeitet: als Löser für die Gleichung auf der von einem Gittergenerator erzeugten Triangulierung des Gebiets oder als Grobgitterlöser innerhalb eines geometrischen Mehrgitterverfahrens.  MIMD Parallelrechner mit sehr vielen Prozessoren sind die Zielarchitektur; sie werden im SPMD Modell benutzt. Ein ganzer Satz von Methoden wird entwickelt, mit dem sich AMG Verfahren – speziell Selektionsverfahren – parallelisieren lassen. Das Ziel ist dabei, das serielle Verfahren möglichst wenig zu verändern, um seine Güte zu erhalten. Dafür wird ein knotenbasierter Verteilungsansatz verwendet. Darauf wird eine parallele lineare Algebra definiert. Der zentrale Begriff ist dabei die parallele Darstellungsform. Für alle benötigten linearen Algebra Operationen wird bewiesen, welche parallelen Darstellungsformen für die Operanden zulässig sind.  Die wesentlichen Komponenten sind ein ausreichender Überlapp der Matrix-Teilgraphen auf den einzelnen Prozessoren, ein Graphfärbungsalgorithmus, mit dessen Hilfe die Arbeit im Überlappbereich teilsequentialisiert wird, um eine widersprüchliche Markierung der Knoten zu vermeiden, sowie die Gittertransferoperatoren  (Restriktion und Prolongation), die Galerkinassemblierung für die Erstellung der Grobgittermatrizen und der Löser auf dem gröbsten Gitter. Dabei wird Wert darauf gelegt, daß alle Komponenten völlig verteilt ablaufen können, um so eine gute Skalierbarkeit auch für sehr viele Prozessoren zu ermöglichen. Für den Löser auf dem gröbsten Gitter stellt sich eine Agglomeration auf nur einen Prozessor als ausreichend performant heraus. Die Korrektheit aller Algorithmusteile wird bewiesen. Dieser Rahmenalgorithmus wird nun konkret auf das filternde algebraische Mehrgitterverfahren (FAMG) angewandt. Als Hilfsmittel für die parallele Programmierung wird das Programmiersystem UG (Unstructured Grids, siehe http://cox.iwr.uni-heidelberg.de/~ug) verwendet. Der Kern des FAMG Verfahrens, nämlich die Bestimmung einer Menge von guten Elternpaaren, aus denen ein Knoten gut interpoliert werden kann, kann gegenüber dem seriellen Verfahren unter den geschaffenen Voraussetzungen vollkommen unverändert gelassen werden. Die Sequenz, in der diese Elternpaare ausgewählt und zur Fein- bzw. Grobknotenmarkierung herangezogen werden, muß allerdings für einen effizienten parallelen Algorithmus entscheidend umgestaltet werden. Dafür stellt das entwickelte Rahmenverfahren die entscheidenden Hilfsmittel bereit. Da hier allerdings vom seriellen Ablauf abgewichen werden muß, ist das die kritische Stelle im gesamten Verfahren. Daß dabei die Robustheit des Lösungsverfahrens nicht verloren geht, zeigen die durchgeführten numerischen Experimente. Das Verfahren ist für alle Steifigkeitsmatrizen, wie sie aus Finiten Differenzen, Finiten Elemente oder Finiten Volumen Diskretisierungen entstehen, geeignet. Es werden Experimente für die Anisotrope Poissongleichung und die Konvektions-Diffusionsgleichung für lineare Strömungen und Kreisströmungen präsentiert. Für diese singulär gestörten Differentialgleichungen werden auch extreme Parameterwerte getestet, die üblicherweise ein paralleles Lösungsverfahren zum Versagen bringen. Die Parallelisierung kann unverändert auch für Systeme von partiellen Differentialgleichungen verwendet werden. In den Experimenten werden bis zu 128 Prozessoren und 16,7 Mio. Unbekannten verwendet. In allen Fällen wird Robustheit bezüglich des Gleichungsparameters (das ist der Anisotropiekoeffizient bzw. die Pecletzahl), der Prozessoranzahl, der Gebietsaufteilung und der Gitterweite (bzw. der Anzahl der Unbekannten im linearen Gleichungssystem) erzielt. Die ermittelten Scale-up Effizienzen von bis zu 80% auf 128 Prozessoren sind sehr gut. Als die zwei wesentlichen Einflußfaktoren auf die parallele Effizienz werden die Lastbalance und die Interfacelänge nachgewiesen. Für beide Faktoren gibt es ausgereifte Techniken, um mit ihnen umzugehen. Das Ziel, ein robustes, effizientes und paralleles algebraisches Mehrgitterverfahren zu erstellen, ist also vollständig erreicht worden.
date: 2000
type: Dissertation
type: info:eu-repo/semantics/doctoralThesis
type: NonPeerReviewed
format: application/pdf
identifier: https://archiv.ub.uni-heidelberg.de/volltextserverhttps://archiv.ub.uni-heidelberg.de/volltextserver/4146/1/pFAMG.pdf
identifier: DOI:10.11588/heidok.00004146
identifier: urn:nbn:de:bsz:16-opus-41469
identifier:   Wrobel, Christian  (2000) Die Parallelisierung des filternden algebraischen Mehrgitterverfahrens zum Lösen partieller Differentialgleichungen.  [Dissertation]     
relation: https://archiv.ub.uni-heidelberg.de/volltextserver/4146/
rights: info:eu-repo/semantics/openAccess
rights: http://archiv.ub.uni-heidelberg.de/volltextserver/help/license_urhg.html
language: ger