Iterative Lösung asymmetrischer Gleichungssysteme auf Transputersystemen

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

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.