Ein Nested-Dissection basierter Schur-Komplement-Niedrigrang-Korrektur Präkonditionierer

Betreuer/in:            Sabine Le Borne           
Dekanat/Institut:   Elektrotechnik, Informatik, Mathematik / Mathematik (E-10)           

E-Mail:   leborne@tuhh.de

Motivation: Große, schwachbesetzte Gleichungssysteme können durch sogenannte Krylovraumverfahren iterativ gelöst werden, wobei die Konvergenzeigenschaften von der Konstruktion eines geeigneten Präkonditionierers abhängen. Der von Zheng, Xi, Saad [1] vorgeschlagene Power Schur Complement Low-Rank Correction
(PSLR) Präkonditionierer verwendet als Ansatz eine Gebietszerlegung in mehrere disjunkte Teilgebiete und einen inneren Rand, in der Randknoten mit Knoten aus nur genau einem Teilgebiet verbunden sind. Es soll untersucht werden, wie sich eine alternative Nested Dissection Zerlegung auf den Präkonditonierer auswirkt.

[1] A power Schur complement Low-Rank correction preconditioner for general sparse linear systems, Qingqing Zheng, Yuanzhe Xi, Yousef Saad (2020), https://arxiv.org/abs/2002.00917

Methoden: Die Gebietszerlegung in mehrere disjunkte Teilgebiete soll durch einen Nested Dissection Ansatz ersetzt werden, d.h. eine Zerlegung in nur zwei disjunkte Teilgebiete mit möglichst kleinem inneren Rand und anschließender
rekursiver Anwendung der Zerlegung innerhalb der Teilgebiete. Solche Zerlegungen werden typischerweise über den Matrixgraphen bestimmt. Die zugrundeliegende Struktur des Präkonditionierers, basierend auf einer Potenzreihenentwicklung und Niedrigrangkorrektur, soll erhalten bleiben und rekursiv formuliert werden. Der resultierende Algorithmus verwendet diverse Methoden aus der numerischen linearen Algebra. Beide Ansätze sollen durch umfangreiche numerische Tests verglichen werden.

Projektziele und Arbeitspakete:
– Durcharbeiten des Artikels [1] – Implementierung (C/C++) der Gebietszerlegung in mehrere disjunkte Teilgebiete mit Rand (wie in [1]) sowie der Nested Dissection Zerlegung (ggfs. unter Verwendung des METIS Pakets)
– Implementierung des Präkonditionerers aus [1] und Anpassung an die Nested Dissection Zerlegung (Rekursion)
– Umfangreiche Tests und Dokumentation numerischer Ergebnisse im Hinblick auf Konvergenzraten, Parallelisierbarkeit, Rechen- und Speicheraufwand; Anwendungsprobleme sind hierbei elliptische partielle
Differentialgleichungen in zwei- und drei Raumdimensionen (Implementierungen der Testprobleme sind bereits vorhanden).

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.