Große dünnbesetzte Gleichungssysteme

In diesem SCCOMP Modul wollen wir uns mit großen dünnbesetzten Gleichungssystemen beschäftigen. Gleichungssysteme treten in vielen numerischen Anwendungen auf, wie der Diskretisierung von Differentialgleichungen. Dabei ist entscheidend, dass nur wenige Einträge der Matrix einen Wert ungleich NULL besitzen. Damit lassen sich die Matrizen durch entsprechende Datenstrukturen effizient darstellen und Operationen, wie Matrix-Vektor Produkt, effizient durchführen.

Für besonders große Systeme kann es erforderlich sein die Daten in einem Rechner-Netz zu verteilen und auch die Operationen verteilt durchzuführen. Dadurch entstehen neue Schwierigkeiten, die behandelt werden müssen. Wir wollen uns Algorithmen anschauen zur Lösung von Gleichungssystemen, die auch als Building-Blocks in anderen Algorithmen eingesetzt werden können. Dabei sollen auch Aspekte der Parallelisierung der Algorithmen, und Verfahren die speziell für die Parallelisierung entwickelt worden, betrachtet werden.

Neben der Theorie der Algorithmen sollen alle Verfahren implementiert werden.

Ort und Zeit

Themen

• Einfache Iterationsverfahren (Jacobi, Gauss-Seidel, SOR)
• Krylov-Unterraum Verfahren (CG, GMRES)
• Mehrgitterverfahren
• Gebietszerlegungsverfahren

Literaturhinweise

• Iterative Methods for Sparse Linear Systems, Second Edition, 2003 (Yousef Saad)
• Parallele numerische Verfahren, 2002 (Alefeld, Lenhardt, Obermaier)