Lösung linearer Gleichungssysteme auf Parallelrechnern

ISBN-13: 9783528063979 / Niemiecki / Miękka / 1990 / 267 str.

Andreas Frommer

Opis

Seit es elektronische Rechenanlagen gibt, verbindet man mit einem nume rischen Verfahren ganz selbstverstandlich auch einen zugehorigen Algorith mus, welcher auf einem Computer iiber ein Programm realisiert werden kann. Um so erstaunlicher scheint es, dafi von seiten der Numerik der algorithmi sche Aspekt lange stark vemachlassigt wurde. In den letzten fiinfzehn J ahren hat sich hier jedoch ein tiefgreifender Wan del vollzogen. Er wurde ausgelost durch den erfolgreichen, inzwischen iiberall verbreiteten Einsatz von Vektorrechnem, welche heute Rechenleistungen bie ten, die bis vor kurzem noch fUr unmoglich gehalten wurden. Weiter verstarkt wurde dieser Wandel durch die erst in den letzten fiinf J ahren vermehrt eingesetzten Parallelrechner mit Prozessorzahlen in der Grofienordnung von zehn bis zehntausend. Gegenwartig stellen Parallelrechner hohes Rechenpo tential relativ preisgiinstig zur Verfiigung. Fiir die Zukunft ist zu erwarten, dafi, wie zum Tell bereits heute, die jeweiligen Hochstleistungsrechner oder Supercomputer Prinzipien der Vektor-und Parallelrechner kombinieren. Auf einem Vektor-oder Parallelrechner hangt die erzielte Rechenleistung sehr stark davon ab, ob der programmierte Algorithmus der speziellen Ar chitektur des Rechners angepafit ist. Zwangslaufig kommt so der Umsetzung eines numerischen Verfahrens in einen adaquaten Algorithmus zentrale Be deutung zu. Mehr noch: Kann ein Verfahren nicht in einen effi.zienten AI gorithmus umgesetzt werden, so sucht man neue, bereits im Ansatz "vekto rielle" oder "parallele" numerische Methoden. Beide Punkte, Algorithmen Design und Entwicklung neuer paralleler numerischer Methoden bllden heut zutage einen wichtigen Bestandtell der jungen Disziplin des Wissenschaftli chen Rechnens (engl.: Scientific Computing).

Spis treści

1 Vektor- und Parallelrechner.- 1.1 Vektorrechner.- 1.2 Parallelrechner.- 1.3 Pseudocodes.- 2 Fan-in-Methoden.- 2.1 Fan-in bei Summation.- 2.2 Rundungsfehler bei Fan-in-Summation.- 2.3 Weitere Anwendungen.- 3 Matrizenmultiplikation.- 3.1 ijk-Formen, Vektorrechner.- 3.2 Blockweise Organisation für Parallelrechner.- 3.3 Matrix-Vektor-Multiplikation.- 4 Gau?-Elimination.- 4.1 Gau?-Elimination ohne Pivotsuche.- 4.2 ijk-Formen, Vektorrechner.- 4.3 Gau?-Elimination auf Parallelrechnern.- 4.4 Pivotstrategien.- 5 Gestaffelte lineare Gleichungssysteme.- 5.1 ij-Formen, Vektorrechner.- 5.2 ij-Formen für Parallelrechner.- 6 Lineare Differenzengleichungen.- 6.1 Lineare Differenzengleichungen r-ter Ordnung.- 6.2 Rekursives Verdoppeln und zyklische Reduktion.- 6.3 Partitionsverfahren.- 6.4 Differenzengleichungen höherer Ordnung.- 7 Systeme mit Bandmatrix.- 7.1 Gau?-Elimination.- 7.2 Das Verfahren von Stone.- 7.3 Das Verfahren von Hockney und Golub.- 7.4 Partitionsverfahren.- 7.5 Grö?ere Bandbreiten.- 8 Klassische Iterationsverfahren.- 8.1 Konvergenz von Iterationsverfahren.- 8.2 JOR-Verfahren.- 8.3 SOR-Verfahren.- 8.4 Abbruch bei Iterationsverfahren.- 9 Multisplitting-Verfahren.- 9.1 Definition und Beispiele.- 9.2 Konvergenzaussagen.- 10 Modellproblem: Diskrete Laplace—Gleichung.- 10.1 Beschreibung des Modellproblems.- 10.2 Direkte Verfahren.- 10.3 SOR-Verfahren.- 10.4 Ausblick aufweitere Iterationsverfahren.- 11 Asynchrone Iterationsverfahren.- 11.1 Realisierung asynchroner Verfahren.- 11.2 Konvergenzaussagen.- A Hilfsmittel aus der linearen Algebra.- A.1 Normen.- A.2 Konvergenz von Iterationsverfahren.- A.3 Symmetrisch positiv definite Matrizen.- B Nichtnegative Matrizen.- B.1 Aussagen über den Spektralradius.