Parallele Adaptive Mehrgitterverfahren

ISBN-13: 9783519027218 / Niemiecki / Miękka / 1996 / 200 str.

Peter Bastian; Peter Bastian

Opis

Die Simulation technisch-wissenschaftlicher Vorgange auf dem Computer gewinnt heute immer mehr an Bedeutung. In zunehmenden Masse werden Bauteile mit Hilfe des Rechners entworfen und somit teuere Versuchsauf bauten vermieden sowie der Entwicklungsprozess beschleunigt. Enorme Be deutung erlangen auch Methoden zur Simulation des Schadstoff transportes im Grundwasser um etwa Verschmutzungen in Wassereinzugsgebieten zu vermeiden oder Sanierungsmassnahmen zu optimieren. Die rechnergestutzte Simulation oben genannter Probleme erfordert in ihrem Kern fast immer die Losung grosser, schwachbesetzter linearer Gleichungs systeme. Die Beschleunigung der Losung solcher Gleichungssysteme wurde in den letzten Jahrzehnten zu gleichen Teilen durch eine Verbesserung der Rechner und durch eine Verbesserung der Algorithmen erreicht. Die Be schleunigung der Rechner wurde durch die Verbesserung der Halbleitertech nologie (hohere Taktrate und grossere Wortbreiten) und verschiedene Paral lelisierungskonzepte (Vektorrechner, superskalare Rechner, MIMD-Rechner) erzielt. Auf algorithmischer Seite wurden hocheffiziente Iterationsverfahren, etwa das Mehrgitterverfahren, entwickelt und die Anzahl der Unbekannten durch adaptive Algorithmen minimiert. In diesem Buch wird nun die Kombination mehrerer dieser Beschleunigungs techniken in einem flexiblen Programmsystem vorgestellt. Es werden adapti ve Mehrgitterverfahren auf einem portablen, parallelen Programmiermodell implementiert und anhand praktischer Versuche gezeigt, dass sich diese Ver fahren sehr effizient parallelisieren lassen. Die Implementierung beschrankt sich auf zweidimensionale Probleme, die Gitter konnen allerdings vollkom men unstrukturiert sein und beliebig lokal verfeinert werden. In der Arbeit wird die Parallelisierung aller Komponenten des adaptiven Algorithmus be sprochen, der Schwerpunkt liegt jedoch auf der Entwicklung von Verfahren zur dynamischen Lastverteilung auf Anwendungse

Spis treści

1 Einleitung.- 2 Komponenten adaptiver Verfahren.- 2.1 Randwertproblem und Diskretisierung.- 2.2 Funktionenräume für Mehrgitterverfahren.- 2.3 Das Mehrgitterverfahren.- 2.4 Abstrakte Formulierung linearer Iterationsverfahren.- 2.5 Konvergenzresultate.- 2.6 Implementierung der Verfahren auf seriellen Rechnern.- 2.7 Eine Finite-Volumen-Diskretisierung.- 2.8 Fehlerschätzer.- 3 Parallelisierung des Mehrgitterverfahrens.- 3.1 Überblick.- 3.2 Datenpartitionierung für unstrukturierte Gitter.- 3.3 Matrizen und Vektoren.- 3.4 Defektbildung.- 3.5 Glätter.- 3.6 Restriktion.- 3.7 Prolongation.- 3.8 Paralleles Gesamtverfahren.- 4 Der Programmbaukasten UG.- 4.1 Ziele.- 4.2 Datenstruktur.- 4.2.1 Algebraische Struktur.- 4.2.2 Geometriebeschreibung.- 4.2.3 Problembeschreibung.- 4.2.4 Knoten, Kanten und Elemente.- 4.2.5 Gitter und Mehrgitter.- 4.3 Parallele Verwaltung der Datenstruktur.- 4.4 Gitterverfeinerung.- 4.4.1 Ein Beispiel.- 4.4.2 Algorithmus.- 4.4.3 Komplexität.- 4.5 Lasttransfer.- 5 Lastverteilung.- 5.1 Übersicht.- 5.2 Mathematische Formulierung des Problems.- 5.2.1 Graphenmodelle.- 5.2.2 Kostenfunktionale für Eingitterverfahren.- 5.2.3 Kostenfunktionale für additives Mehrgitterverfahren.- 5.2.4 Kostenfunktionale für multiplikatives Mehrgitterverfahren.- 5.3 Lastverteilung für Eingitterverfahren.- 5.4 Lastverteilung für adaptive Mehrgitterverfahren.- 5.4.1 Clustering.- 5.4.2 Lastverteilung für multiplikatives Mehrgitterverfahren.- 5.4.3 Lastverteilung für additives Mehrgitterverfahren.- 5.4.4 Analyse des Verfahrens für additives Mehrgitter.- 6 Praktische Ergebnisse und Ausblick.- 6.1 Ziele und Methoden.- 6.2 Beispiel KAMMER.- 6.2.1 Beschreibung.- 6.2.2 Iterationszahlen.- 6.2.3 Effizienzvergleich der Verfahren.- 6.3 Beispiel NORDSEE.- 6.3.1 Beschreibung.- 6.3.2 Einfluß der Lastverteilung.- 6.4 Beispiel MODELL.- 6.4.1 Beschreibung.- 6.4.2 Effizienz in Abhängigkeit des Wachstumsfaktors.- 6.4.3 Analyse der Verluste.- 6.5 Beispiel KONVEKTION.- 6.5.1 Beschreibung.- 6.5.2 Effizienzvergleiche.- 6.5.3 Prozentuale Anteile.- 6.6 Beispiel EXAKT.- 6.6.1 Beschreibung.- 6.6.2 Effizienzvergleich.- 6.7 Abschließende Bewertung der Ergebnisse.- 6.8 Zusammenfassung und Ausblick.- A Übersicht über Lastverteilungsverfahren.- 1.1 Einige Begriffe.- 1.2 Verfahren der diskreten Optimierung.- 1.2.1 Exakte Verfahren.- 1.2.2 Nichtdeterministische Heuristiken.- 1.2.3 Deterministische Heuristiken.- 1.3 Verfahren zur Lösung des Graphabbildungsproblems.- 1.3.1 Bisektionsverfahren.- 1.3.2 Direkte Aufteilung in mehr als zwei Partitionen.- 1.4 Diffusionsverfahren.

Blurb

Aus dem Inhalt Komponenten adaptiver Verfahren - Parallelisierung des Mehrgitterverfahrens - Parallele Gitterverfeinerung - Der Programmbaukasten UG - Dynamische Lastverteilung für adaptive Mehrgitterverfahren - Praktische Ergebnisse und Ausblick - Anhang: Übersicht über Lastverteilungsverfahren