Description
Idealer Einstieg: Theorie und Praxis paralleler numerischer Verfahren anhand klassischer Algorithmen. Dargestellt sind Bereiche der numerischen linearen Algebra als auch der numerischen Analysis. Bei Aufbau und Erstellung paralleler Programme hilft die Programmbibliothek MPI. Anhand der Praktikumsaufgaben knnen Leser ihren Lernerfolg berprfen. Quelltexte sind auf der Homepage der Autoren zu finden. Ein praxisorientiertes Lehr- und bungsbuch fr Mathematiker, Informatiker, Ingenieurwissenschaftler. 1 Grundstzliches ber Parallelrechner.- 1.1 Rechnertypen und Architekt uren.- 1.1.1 Verteilter und gemeinsamer Speicher.- 1.1.2 Granularitt.- 1.1.3 Prozessortopologie.- 1.1.4 SIMD- und MIMD-Rechner.- 1.2 Leistungsb eurt eilung von Par allelrechnern.- 1.2.1 Parallelisierungsgrad.- 1.2.2 Speed-up und Effizienz.- 1.2.3 Das Gesetz von Amdahl.- 1.3 Parallele Programmiermodelle.- 1.3.1 Ebenen der Parallelitt.- 1.3.2 Implizite und explizite Paralle litt.- 1.3.3 Erzeugung von Prozessen.- 1.3.4 Datenaustausch.- 2 Parallele Verfahren fr partielle Differentialgleichungen.- 2.1 Standardverfahren fr elliptische Differentialgleichungen.- 2.1.1 Poisson-Gleichung mit Dirichlet-Randbedin gungen.- 2.1.2 Das Jacobi-Verfahren zur Lsung von Gleichungssystemen.- 2.1.3 Das Gau-Seidel-Verfahren.- 2.1.4 Das SOR-Verfahr en.- 2.2 Parallelisierung.- 2.2.1 Parallelisierung des Jacobi-Verfahrens.- 2.2.2 Parallelisierung von Gau-Seidel- und SOR-Verfahren.- 2.2.3 Wellenfront (Wavefront)-Nummerierung.- 2.2.4 Red-Black-Nummerierung (Schachbrett-Ordnung).- 2.3 Das ADI-Verfahren.- 2.3.1 Die Wrmeleitungsgleichung.- 2.3.2 Explizites Differenzenverfahren.- 2.3.3 Sequentielles ADI-Verfahren.- 2.3.4 Auflsung von Gleichungssystemen mit Tridiagonalmatrix.- 2.3.5 Parallele Durchfiihrung des ADI-Verfahrens.- 3 Graph-Partitionierung.- 3.1 Hilfsmittel und Definitionen.- 3.2 Spektralbisektion.- 3.3 Weitere Partitionierungsheuristiken.- 4 Die Methode der konjugierten Gradienten.- 4.1 Sequentielle Durchfhrung.- 4.1.1 Minimierung eines Funktionals.- 4.1.2 Zusammenhang zum Gauf-Seidel-Verfahren.- 4.1.3 Die Methode des steilsten Abstiegs.- 4.1.4 Die Methode der konjugierten Gradienten (CG-Verfahren).- 4.2 Das vorkonditionierte CG-Verfahren.- 4.2.1 Das symmetrische SOR-Verfahren (SSOR-Verfahren).- 4.2.2 Konstruktion einer Vorkonditionierungsmatrix.- 4.2.3 Weitere Mglichkeiten zur Vorkonditionierung.- 4.3 Parallelisierung des CG-Verfahrens.- 4.3.1 Der parallele Algorithmus.- 4.3.2 Parallele Vorkonditionierung durch Gebietszerlegung.- 5 Mehrgitterverfahren (Multi-Grid Method).- 5.1 Motivation.- 5.2 bergang zwischen Gittern.- 5.3 Grobgitterkorrektur (Coarse Grid Correction).- 5.4 Interpolation und Prolongation im zweidimensionalen Fall.- 5.5 Bemerkungen zur Programmierung des Mehrgitterverfahrens.- 5.5.1 Gitterzerlegung und Mehrgitterverfahren.- 6 Das symmetrische Eigenwert-Problem.- 6.1 Das Jacobi-Verfahren zur Berechnung von Eigenwerten.- 6.1.1 Parallele Durchfuhrung.- 6.1.2 Realisierung auf einem Parallelrechner.- 6.2 Berechnung der Eigenwerte durch Reduktion der Matrix auf Tridiagonalgestalt.- 6.2.1 Reduktion auf Tridiagonalgestalt.- 6.2.2 Berechnung der Eigenwerte einer symmetrischen Tridiagonalmatrix.- 6.3 Ein Divide-and-Conquer- Verfahren (“Teile-und-Herrsche-Verfahren”).- 6.3.1 Divide-and-Conquer-Verfahren fr Tridiagonalmatrizen T ? ?n*n mit n=2m.- 7 Der Gau-Algortthmus – Anwendung bei Integralgleichungen.- 7.1 Grundlagen.- 7.2 Das Nystrm-Verfahren.- 7.3 Parallele Durchfhrung des Nystrm-Verfahrens.- 7.3.1 Der parallele Gau-Algorithmus mit Pivotsuche.- 8 Aufgaben fr ein Parallelrechnerpraktikum.- 8.1 Elementare Aufgaben.- 8.1.1 Speed-up.- 8.1.2 Ein erstes paralleles Programm.- 8.1.3 Punkt-zu-Punkt-Kommunikation mit MPI.- 8.1.4 Kommunikationsbandbreite und Start-up-Zeit.- 8.1.5 Kollektive Kommunikation mit MPI.- 8.2 Parallele Matrix-Vektor-Multiplikation fr dichtbesetzte Matrizen.- 8.3 SOR-Verfahren mit Red-Black-Ordnung.- 8.4 Direktes Lsen von Gleichungssystemen mit Tridiagonalmatrix.- 8.5 Graphpartitionierung I.- 8.6 Graphpartitionierung II.- 8.7 CG-Verfahren.- 8.8 Jacobi-Verfahren zur Berechnung von Eigenwerten.- 8.9 Nystrm-Verfahren.- A Ein Linux-Cluster als Parallelrechner.- A.l Hardware.- A.2 Systemsoftware.- A.2.1 Betriebssystem-Installati on.- A.2.2 Nameservices.- A.2.3 NIS (Network Information Service).- A.2.4 NFS (Network File System).- A.2.5 Remote Shell (rsh) / Secure Shell (ssh).- A.2.6 Automatisierung durch Skripte.- A.3 Programmbiblioth eken zur parallelen Programmierung.- A.3.1 Programmerstellung.- A.3.2 Die Compiler mpicc, mpiCC und mpif77.- A.3.3 Starten und Beenden der Kommunikationsumgebung mit lamboot und lamwipe.- A.3.4 Starten von parallelen Programmen mit mpirun.- A.3.5 MPI-Kurzreferenz.- Stichwortverzeichnis.
