17.06.2025, 11:00 Uhr

Universität Wien
Besprechungsraum 4.34
Währinger Str. 29
1090 Wien

Titel: Scalable GMRES methods

Kurzfassung:
Große dünn besetzte lineare Gleichungssysteme sind zentral für viele komplexe und
rechenintensive Probleme in verschiedenen wissenschaftlichen Bereichen. Hochleistungsrechnen
(High Performance Computing, HPC) und hochgradig parallelisierbare
iterative Verfahren sind wichtige Werkzeuge, um diese Systeme effizient zu lösen.
Kommunikation – der Prozess der Datenübertragung innerhalb des HPC-Systems
– kann zu einem erheblichen Engpass werden, insbesondere bei der Lösung sehr
großer Probleme, was die Entwicklung kommunikationsvermeidender iterativer Verfahren
motiviert hat. Gleichzeitig hat die Randomisierung in den letzten Jahren einen
tiefgreifenden Einfluss auf die numerische lineare Algebra gehabt. Randomisierungstechniken
lassen sich in viele bestehende Algorithmen integrieren und bieten häufig
eine verbesserte Skalierbarkeit und Geschwindigkeitssteigerungen im Vergleich zu
deterministischen Ansätzen. Vor diesem Hintergrund untersucht diese Masterarbeit
Ideen aus der randomisierten numerischen linearen Algebra, die auf kommunikationsvermeidende
iterative lineare Systemlöser angewendet werden. Insbesondere betrachten
wir den Stand der Technik bei deterministischen und randomisierten sstep
Generalized Minimal Residual (GMRES) Methoden und schlagen eine neue randomisierte
s-step Variante namens RTBGS-GMRES vor, die die Performance beim
Aufbau der Basis für den Lösungsunterraum verbessert und dabei die Anzahl der
globalen Synchronisierungen in parallelen Rechenumgebungen minimiert. Wir vergleichen
unsere neue Methode mit modernen randomisierten und deterministischen
s-step GMRES-Methoden hinsichtlich numerischer Stabilität, Konvergenz, Performance
und Skalierbarkeit. Numerische Experimente auf einem großen Cluster zeigen,
dass die randomisierten GMRES-Methoden bei geeigneten Parameterwerten die parallele
deterministische s-step Methode BCGSI2-GMRES in der Regel übertreffen.
Unsere neue RTBGS-GMRES Methode übertrifft die anderen Methoden und erzielt
Geschwindigkeitssteigerungen von etwa 2× und etwa 4× gegenüber BCGSI2-GMRES
für zwei verschiedene Basistypen.