Krylowunterraumverfahren
Bei Anwendung der Finite Elemente Methode in der Strukturmechanik entstehen lineare Gleichungssysteme mit großen Koeffizientenmatrizen. Diese sind im Speziellen dünn besetzt, symmetrisch und positiv definit.
Bei Benutzung von direkten Methoden zur Lösung des linearen Gleichungssystems, wie die Cholesky-Zerlegung, entstehen vollbesetzte Dreiecksmatrizen, welche um ein Vielfaches größer sind als die dünnbesetzte Koeffizientenmatrix. Deshalb sind direkte Methoden bei großen Problemen oft nicht anwendbar. Eine Alternative bietet die Klasse der Krylow-Unterraum-Verfahren, hier im Speziellen das Verfahren der konjugierten Gradienten. Eigentlich ebenfalls ein direktes Verfahren, liefert es in endlichen Wiederholungen einer Rechenvorschrift im Umfang der Problemgröße die exakte Lösung. Dabei hat es die Eigenschaft, bei einem gut konditioniertem Gleichungssystem sich anfangs schnell der exakten Lösung zu nähern. Oft kann die Anwendung der Iterationsvorschrift mit ausreichend genauer Lösung abgebrochen werden, deutlich früher als die Durchführung von Iterationsschritten im vollen Umfang der Problemgröße.
Ein wichtiger Aspekt des Verfahrens der konjugierte Gradienten ist dessen Parallelisierbarkeit. In jeder Iteration hat die Durchführung einer dünn besetzten Matrix-Vektormultiplikation den deutlich größten Rechenaufwand. Diese Operation kann durchaus effizient parallelisiert werden. Dies führt zu der Idee, die Matrix-Vektormultiplikation auf einer GPU durchzuführen, den Rest auf dem gastgebenden Rechner. Diese scheitert jedoch an der teuren Kommunikation zwischen GPU und Rechner, die die Geschwindigkeitsvorteile der Berechnung der Matrix-Vektormultiplikation auf der GPU aufhebt. Um Geschwindigkeitsvorteile durch Benutzung einer GPU zu erhalten, müssen deshalb die Iterationen des Verfahrens der konjugierten Gradienten komplett auf der GPU durchgeführt werden, ohne Datenaustausch zwischen Rechner und GPU währenddessen.
Im Rahmen dieses Projektes wurde das Verfahren der konjugierten Gradienten auf einer GPU-Architektur implementiert und konnte auf einer GPU-Karte die Lösung eines Poissonproblems drei mal schneller berechnen als auf einem CPU-Knoten mit zwölf Kernen. Knackpunkt hierbei ist jedoch das Poissonproblem, das sich von den typischen Problemen in der Strukturmechanik unterscheidet. So sind die Koeffizientenmatrizen letzerer Probleme oft schlechter konditioniert.
Dies führt zur Notwendigkeit der Präkonditionierung der Koeffizientenmatrix. Einfache Präkonditionierungsverfahren sind das Jacobi- oder Block-Jacobi-Verfahren. Deren Präkonditionierungsmatrizen lassen sich effizient innerhalb der GPU-Implementierung des Verfahrens der Konjugierten Gradienten anwenden. Jedoch reicht diese Präkonditionierung oft nicht aus für Koeffizientenmatrizen der Strukturmechanik.
Besser verhält sich die Präkonditionierung durch unvollständige Cholesky-Zerlegung. Dabei wird die Zerlegung der Koeffizientenmatrix in eine Dreiecksmatrix fehlerhaft durchgeführt, um möglichst die dünn besetzte Struktur zu erhalten. Der Vorgang der Zerlegung selber ist schwer parallelisierbar, muss aber nur einmal zur Lösung eines Problemes durchführt werden.
Die Anwendung der Dreiecksmatrix und deren Transponierten in Form des Vorwärts- und Rückwärtseinsetzens muss in jedem Iterationsschritt erfolgen. Sie ist ebenfalls nicht leicht parallelisierbar und führt zu einer schlechteren Rechenleistung auf der GPU als das Verfahren der konjugierte Gradienten ohne Präkonditionierung.
Die Frage nach der Wahl eines guten Präkonditionierungsverfahrens bezüglich der Rechenleistung auf einem GPU-System und der Konvergenzrate für industrielle Anwendungen wie der Strukturmechanik wird im Rahmen dieses Projektes betrachtet.
