Description
Die Konzepte numerischer Verfahren auf modernen Parallel- und Vektorrechnern stehen im Mittelpunkt dieser neuen Einfhrung. Studierende und Anwender aus den Bereichen Mathematik, Natur- und Ingenieurwissenschaften und Informatik werden die erforderlichen Kenntnisse und Fhigkeiten vermittelt, die eine effiziente Nutzung paralleler Strukturen in numerischen Anwendungen ermglichen. Prof. Dr. Hartmut Schwandt, TU Berlin 1 Einleitung.- 2 Einfhrende Beispiele und grundlegende Begriffe.- 2.1 Einfhrende Beispiele.- 2.2 Parallele Strukturen in Algorithmen.- 2.3 Parallelittsbegriff.- 3 Parallelitt 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 fr Rechnerarchitekturen.- 3.1.7.1 Vektorrechner.- 3.1.7.2 Parallelrechner.- 3.1.7.3 Cluster.- 3.2 Untersttzende Software zur Parallelisierung, Vektorisierung und Optimierung.- 3.2.1 Parallele Programmiersprachen.- 3.2.2 Erweiterungen gngiger 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 fr Elementaralgorithmen.- 3.2.7 Softwarewerkzeuge zur Analyse.- 3.3 Einflsse 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 Mazahlen zur Leistungsbeschreibung.- 3.4.2 Zeitmessung.- 3.4.3 Leistungskriterien fr Rechner.- 3.4.4 Leistungskriterien fr 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 fr vollbesetzte Matrizen.- 4.3.2 Matrix-Vektor-Multiplikation fr dnnbesetzte 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 fr lineare rekurrente Relationen m-ter Ordnung.- 4.5.2.2 Algorithmen fr 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 fr 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 fr 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.
