Full Description
Die Konzepte numerischer Verfahren auf modernen Parallel- und Vektorrechnern stehen im Mittelpunkt dieser neuen Einführung. Studierende und Anwender aus den Bereichen Mathematik, Natur- und Ingenieurwissenschaften und Informatik werden die erforderlichen Kenntnisse und Fähigkeiten vermittelt, die eine effiziente Nutzung paralleler Strukturen in numerischen Anwendungen ermöglichen.
Contents
1 Einleitung.- 2 Einführende Beispiele und grundlegende Begriffe.- 2.1 Einführende Beispiele.- 2.2 Parallele Strukturen in Algorithmen.- 2.3 Parallelitätsbegriff.- 3 Parallelität in Rechnerarchitekturen und Softwarewerkzeuge zur Beschreibung paralleler Strukturen.- 3.1 Parallele Strukturen in Rechnerarchitekturen.- 3.1.1 Basiskomponenten einer Rechnerarchitektur.- 3.1.2 Sequentielle Rechner.- 3.1.3 Vektorrechner.- 3.1.3.1 Arithmetische und logische Einheiten.- 3.1.3.2 Aspekte der Speicherstruktur.- 3.1.3.3 Optimale Nutzung der Vektorprozessor-Architektur.- 3.1.4 Mikroprozessoren.- 3.1.4.1 Merkmale von RISC-Architekturen.- 3.1.4.2 Aspekte der Speicherstruktur.- 3.1.5 Parallelrechner.- 3.1.5.1 Prozessoren.- 3.1.5.2 Speichertopologie.- 3.1.5.3 Prozessorkopplung und Kommunikation.- 3.1.5.4 Besondere Parallelrechnerformen.- 3.1.6 Kontrollfluss und Programmiermodell als Klassifikationsmerkmal.- 3.1.7 Beispiele für Rechnerarchitekturen.- 3.1.7.1 Vektorrechner.- 3.1.7.2 Parallelrechner.- 3.1.7.3 Cluster.- 3.2 Unterstützende Software zur Parallelisierung, Vektorisierung und Optimierung.- 3.2.1 Parallele Programmiersprachen.- 3.2.2 Erweiterungen gängiger Programmiersprachen.- 3.2.3 Automatische Erkennung paralleler oder vektorieller Konstrukte und automatische Optimierung.- 3.2.4 Steuerung durch Direktiven.- 3.2.5 Unterprogramm-Bibliotheken zur Kommunikation und Synchronisation.- 3.2.6 Bibliotheken für Elementaralgorithmen.- 3.2.7 Softwarewerkzeuge zur Analyse.- 3.3 Einflüsse der Rechnerarchitektur auf die Entwicklung paralleler Anwendungen.- 3.3.1 Verfahrensauswahl.- 3.3.2 Algorithmenentwicklung.- 3.3.3 Programmentwicklung.- 3.4 Zeit, Leistung und Geschwindigkeit.- 3.4.1 Maßzahlen zur Leistungsbeschreibung.- 3.4.2 Zeitmessung.- 3.4.3 Leistungskriterien für Rechner.- 3.4.4 Leistungskriterien für numerische Anwendungen.- 3.4.5 Amdahls Gesetz.- 4 Basisalgorithmen der linearen Algebra.- 4.1 Reduktionsoperationen.- 4.2 Vektor-Vektor-Operationen und Skalarprodukt.- 4.3 Matrix-Vektor-Operationen.- 4.3.1 Matrix-Vektor-Multiplikation für vollbesetzte Matrizen.- 4.3.2 Matrix-Vektor-Multiplikation für dünnbesetzte Matrizen und Bandmatrizen.- 4.4 Matrix-Matrix-Operationen.- 4.4.1 Grundformen der Matrix-Multiplikation.- 4.4.2 Blockalgorithmen zur Matrix-Multiplikation.- 4.4.3 Beispiel zur Einzelprozessor-Optimierung.- 4.5 Rekurrente Relationen und Differenzengleichungen.- 4.5.1 Allgemeine rekurrente Relationen.- 4.5.2 Lineare rekurrente Relationen und lineare Differenzengleichungen.- 4.5.2.1 Algorithmen für lineare rekurrente Relationen m-ter Ordnung.- 4.5.2.2 Algorithmen für lineare rekurrente Relationen niedriger Ordnung.- 5 Lineare Gleichungssysteme.- 5.1 Direkte Verfahren.- 5.1.1 Vollbesetzte Matrizen.- 5.1.1.1 Sequentieller Gauß-Algorithmus.- 5.1.1.2 Gauß-Algorithmus ohne Pivotsuche.- 5.1.1.3 Gauß-Algorithmus mit Pivotsuche.- 5.1.1.4 Gauß-Algorithmus ohne Pivotsuche für mehrere Systeme.- 5.1.1.5 Block-Gauß-Algorithmus.- 5.1.2 Dreieckssysteme.- 5.1.3 Allgemeine Bandmatrizen.- 5.1.3.1 Gauß-Algorithmus.- 5.1.3.2 Verallgemeinertes Verfahren von Wang.- 5.1.4 Tridiagonalmatrizen.- 5.1.4.1 Gauß-Algorithmus.- 5.1.4.2 Zyklische Reduktion.- 5.1.4.3 Kombination von Gauß-Algorithmus und Zyklischer Reduktion.- 5.1.4.4 Blockzerlegung — Verfahren von Wang und Modifikation von Johnsson.- 5.1.4.5 Schur-Komplement-Verfahren.- 5.1.4.6 Vergleich.- 5.1.5 Blocktridiagonalmatrizen.- 5.1.5.1 Blockzyklische Reduktion.- 5.1.5.2 Buneman-Algorithmus.- 5.1.5.3 Eigenwert-Eigenvektor-Zerlegung.- 5.1.5.4 FACR(1)-Algorithmus.- 5.1.5.5 Vergleich.- 5.2 Iterative Verfahren.- 5.2.1 Parallele Iterationsverfahren und Abbruchkriterien.- 5.2.2 Iterationsverfahren für lineare Gleichungssysteme.- 5.2.2.1 Zerlegungsverfahren.- 5.2.2.1.1 Relaxationsverfahren.- 5.2.2.1.2 Blockverfahren.- 5.2.2.1.3 Mehrfachzerlegungen.- 5.2.2.2 Verfahren der konjugierten Gradienten (CG-Verfahren).- 5.2.2.3 Mehrgitterverfahren.- 5.2.3 Asynchrone Iterationsverfahren.- 6 Schnelle Fourier-Transformation.- 6.1 Problemstellung.- 6.2 Sequentielle Algorithmen.- 6.3 Vektorielle Algorithmen.- 6.4 Parallele Algorithmen.- 6.5 Mehrdimensionale FFT.- 6.6 Bemerkungen zu weiteren Algorithmen.- 6.7 Zahlentheoretische Transformation.- 7 Gebietszerlegung.- 7.1 Aufgabenstellung.- 7.2 Gebietszerlegung mit zwei Teilgebieten.- 7.3 Schur-Komplement-Verfahren.- 7.4 Schwarzsche Alternierende Prozedur und Multisplitting-Verfahren.- A Anhang.- A.1 Bezeichnungen.- A.2 Definitionen und Hilfsergebnisse.
