Durch Konstruktion von Modellen realer Strukturen, gelingt es in vielen Bereichen der Wissenschaften den Einfluss von Größen auf ein Gesamtsystem zu bestimmen und dadurch qualitativ und quantitativ zu einem besseren Verständnis zu gelangen. Ziel ist es, mit einer möglichst geringen Anzahl von Annahmen die reale Struktur so exakt wie möglich darzustellen. Solche Modelle finden in allen Zweigen der Naturwissenschaften, wie auch in den Wirtschaftswissenschaften ihre Anwendung. Die mathematische Modellierung komplexer Prozesse und deren Simulation auf Rechnern, gewinnt dabei zunehmend an Bedeutung. Sie ermöglicht im Vergleich zur komplizierten Konstruktion eines Versuchsaufbaus, die immer komplexeren Fragestellungen auf kostengünstige Weise zu untersuchen. Dabei ist sie mit einem geringeren Aufwand an Zeit verbunden. Dies gilt insbesondere bei der Erforschung neuer Technologien. Die anwachsende Komplexität der Problemstellungen erfordert jedoch für deren numerischen Lösung in zunehmendem Maß einen steigenden Aufwand an Rechenleistung bzw. Speicherplatzkapazit. Diese Arbeit entstand im Umfeld eines DFG Schwerpunktprojektes zur Simulation eines Modells laminarer Flammen, dem sog. Fame sheet Modell. Die Dynamik chemischer Reaktionssysteme läßt sich mathematisch durch die Lösung der zugrunde liegenden Erhaltungsgleichungen simulieren. Für die Weiterentwicklung bestehender Verbrennungsanlagen jeder Art in Hinblick auf eine ökologische Nutzung der Recourcen.
Inhaltsverzeichnis
1 Modellprobleme und Diskretisierung
2 Krylov Unterraum Verfahren
2.1 Symmetrischer Lanczos
2.2 Asymmetrischer Lanczos
2.3 Arnoldi Prozeß
2.4 Verfahren der bi-konjugierten Gradienten
2.5 Verfahren der konjugierten Gradienten
2.6 Generalised minimal residual
3 Look-ahead Lanczos
3.1 Eine Variante des asymmetrischen Lanczos
3.2 Orthogonalpolynome und Standard Lanczos
3.3 Formal orthogonale Polynome
3.4 Look-ahead Lanczos
3.5 Notation
3.6 Kriterien eines look-ahead Schrittes
3.7 Look-ahead Schritt
4 QMR-Verfahren
4.1 Das Verfahren
4.2 Zusammenhang QMR und BCG
5 Vorkonditionierung
5.1 Unvollständige LU-Zerlegung
5.2 Implementierung der ILU
6 Parallelisierung
6.1 Übersicht
6.2 Transputersysteme
6.3 Kenngrößen
6.4 Gebietszerlegung und Datenverteilung
6.5 Kommunikationsroutinen
7 Parallele Version des QMR
7.1 Parallele Lanczos Verfahren
7.2 Paralleler Look-ahead Schritt
7.3 Paralleles QMR-Verfahren
8 Parallele Vorkonditionierung
8.1 Grundsätzliche Überlegungen
8.2 Skalare Gleichungen
8.3 Block Version
9 Abschließende Bemerkungen
Zielsetzung & Themen
Die Diplomarbeit untersucht die iterative Lösung asymmetrischer Gleichungssysteme auf Transputersystemen, mit dem Ziel, effiziente parallele Algorithmen für komplexe physikalische Modelle wie Strömungs- und Reaktionsabläufe zu entwickeln.
- Krylov-Unterraum-Verfahren (QMR, Lanczos, BCG)
- Look-ahead Strategien zur Stabilitätssicherung
- Parallelisierung und Datenverteilung auf Transputersystemen
- Methoden der Vorkonditionierung zur Konvergenzbeschleunigung
- Leistungsanalyse und Effizienz paralleler Algorithmen
Auszug aus dem Buch
2. Krylov Unterraum Verfahren
Das QMR-Verfahren basiert auf einer Strategie, die C. Lanczos zur iterativen Eigenwertbestimmung Ax = λx großer, dünn besetzter, symmetrischer Gleichungssysteme vorgeschlagen hatte, [16]. Arnoldi faßte diese Idee auf und übertrug sie auf asymmetrische Gleichungssysteme, [9]. Diese Techniken erwiesen sich jedoch als äußerst anfällig für Rundungsfehler und gerieten dadurch in Vergessenheit. Neues Interesse am Lösungsansatz von Lanczos kam jedoch mit der Theorie von Kaniel und Paige auf, [23]. Sie bewies die außerordentliche Konvergenzgeschwindigkeit dieser Verfahrensweise für den Fall, daß lediglich die extremen Eigenwerte einer Matrix aufzufinden sind. Insbesondere gewannen iterative Verfahren zur Lösung linearer Gleichungssysteme Ax = b aufgrund der anwachsenden Dimensionen zunehmend an Bedeutung.
Basierend auf den Strategien von Lanczos und Arnoldi wurden Verfahren zur Lösung dieser Probleme entwickelt und Versuche unternommen, diese durch unterschiedliche Techniken zu stabilisieren. Eine Reihe bekannter Verfahren beruhen auf der Idee von Lanczos, welche unter dem Begriff Krylov Unterraum Verfahren zusammengefaßt werden. So führt der symmetrische Ansatz von Lanczos auf das bekannte Verfahren der konjugierten Gradienten, dem CG, [13], welches heute zu den meist verwandten iterativen Verfahren zur Lösung großer, dünn besetzter und symmetrischer Gleichungssysteme gehört. Die Modifikation des CG für asymmetrische Matrizen, die bikonjugierte Gradienten Verfahren, BCG, [15], resultiert aus einem asymmetrischen Ansatz von Lanczos. Das GMRES, generalised minimal residual, [21], beruht seinerseits auf dem asymmetrischen Lösungsansatz von Arnoldi. Zur Einordnung des QMR-Verfahrens in diese Reihe von Verfahren in diesem Kapitel deren Zusammenhänge untereinander herausgearbeitet. Sie beruhen auf den Eigenschaften, spezieller Unterräume des RN, den Krylov Unterräumen. Deren wesentlichen Merkmale werden aus diesem Grund im Folgenden knapp skizziert.
Zusammenfassung der Kapitel
1 Modellprobleme und Diskretisierung: Beschreibung der mathematischen Modellierung physikalischer Vorgänge mittels partieller Differentialgleichungen und deren numerische Diskretisierung.
2 Krylov Unterraum Verfahren: Einführung in die theoretischen Grundlagen iterativer Verfahren zur Lösung linearer Gleichungssysteme, insbesondere basierend auf Krylov-Unterräumen.
3 Look-ahead Lanczos: Behandlung stabiler Varianten des Lanczos-Algorithmus unter Verwendung von Formal orthogonalen Polynomen zur Umgehung kritischer Abbrüche.
4 QMR-Verfahren: Vorstellung des Quasi-Minimal-Residual-Verfahrens und dessen Zusammenhang zum BCG-Verfahren sowie die Herleitung der Iterationsschritte.
5 Vorkonditionierung: Untersuchung von Methoden zur Verbesserung der Kondition von Matrizen, insbesondere durch unvollständige LU-Zerlegungen (ILU).
6 Parallelisierung: Erläuterung der Rechnerarchitekturen, insbesondere Transputersysteme, sowie Strategien zur Gebietszerlegung und Datenverteilung.
7 Parallele Version des QMR: Ableitung und Implementierung paralleler Algorithmen für das QMR-Verfahren unter Berücksichtigung lokaler und globaler Kommunikation.
8 Parallele Vorkonditionierung: Anpassung der Vorkonditionierungsmethoden an parallele Architekturen und Analyse der Effizienzsteigerung durch Block-Varianten.
9 Abschließende Bemerkungen: Zusammenfassende Diskussion der Ergebnisse sowie Ausblick auf die Eignung der Verfahren für spezifische Simulationsanwendungen.
Schlüsselwörter
Iterative Lösung, Asymmetrische Gleichungssysteme, Krylov-Unterraum-Verfahren, Transputersysteme, QMR-Verfahren, Lanczos-Verfahren, Vorkonditionierung, Parallelisierung, Gebietszerlegung, Datenverteilung, Konvergenzgeschwindigkeit, Numerische Simulation, Mathematische Modellierung, Recheneffizienz, ILU-Zerlegung
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Diplomarbeit befasst sich mit der Entwicklung und Implementierung iterativer Lösungsverfahren für asymmetrische lineare Gleichungssysteme auf parallelen Transputersystemen.
Was sind die zentralen Themenfelder der Arbeit?
Die zentralen Themen umfassen die Krylov-Unterraum-Methoden (speziell QMR), Techniken der Vorkonditionierung zur Stabilitätsverbesserung sowie Strategien zur Parallelisierung und Datenverteilung auf Transputerarchitekturen.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist es, effiziente parallele Algorithmen für komplexe mathematische Modelle zu entwerfen, die eine beschleunigte Berechnung bei hoher Recheneffizienz auf parallelen Rechnersystemen ermöglichen.
Welche wissenschaftliche Methode wird primär verwendet?
Die Arbeit nutzt die numerische Analyse und mathematische Modellierung, insbesondere Verfahren zur iterativen Tridiagonalisierung und Projektionsmethoden wie das QMR- und Lanczos-Verfahren.
Welche Schwerpunkte bilden den Hauptteil?
Der Hauptteil behandelt die theoretische Herleitung der Krylov-Methoden und deren Look-ahead-Varianten, die methodische Vorkonditionierung mittels unvollständiger Zerlegungen sowie die praktische Implementierung und Kommunikation auf parallelen Systemen.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Wichtige Begriffe sind iterative Lösungsverfahren, parallele Effizienz, Gebietszerlegung, Look-ahead Lanczos und Transputersysteme.
Wie löst die Arbeit das Problem instabiler Abbrüche in Lanczos-Verfahren?
Durch die Implementierung der Look-ahead Strategie, die bei drohendem kritischem Abbruch (z.B. nahe singuläre Unterräume) auf stabilere Berechnungsblöcke ausweicht.
Warum ist die Wahl der Vorkonditionierung für dieses Projekt wichtig?
Da die hier betrachteten Gleichungssysteme häufig eine schlechte Kondition aufweisen, ist eine effiziente Vorkonditionierung wie die unvollständige LU-Zerlegung entscheidend, um die Anzahl der Iterationsschritte und damit die Gesamtrechenzeit zu reduzieren.
Welche Rolle spielt die Kommunikation zwischen den Prozessoren?
Die Kommunikation ist bei parallelen Verfahren auf Transputersystemen ein kritischer Faktor. Die Arbeit untersucht verschiedene Kommunikationsroutinen und Topologien, um den Kommunikations-Overhead zu minimieren und eine hohe parallele Effizienz zu erzielen.
Was ist das Hauptergebnis bezüglich der gewählten Architektur?
Die Arbeit zeigt, dass eine sorgfältige Datenverteilung und die Berücksichtigung der Granularität der Algorithmen entscheidend sind, um die Hardwareleistung von Transputersystemen optimal zu nutzen.
- Citar trabajo
- Dorothea Eggers (Autor), 1994, Iterative Lösung asymmetrischer Gleichungssysteme auf Transputersystemen, Múnich, GRIN Verlag, https://www.grin.com/document/151725