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 s-step 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.

Large sparse linear systems arise in many complex and computationally intensive problems across various scientific fields. High Performance Computing (HPC) and highly parallelizable iterative methods are important tools for solving these systems efficiently. Communication – the process of moving data within the HPC system – can become a significant bottleneck when solving very large problems, which motivated the development of communication-avoiding iterative methods. At the same time, randomization has had a profound impact on numerical linear algebra in recent years. Randomization techniques work with many existing algorithms, often providing improved scalability and orders-of-magnitude speedups over deterministic approaches. With these aspects in mind, this master’s thesis investigates ideas from randomized numerical linear algebra applied to communication-avoiding iterative linear system solvers. In particular, we explore state-of-the-art deterministic and randomized s-step Generalized Minimal Residual (GMRES) methods and propose a novel randomized s-step variant called RTBGS-GMRES that improves performance in the construction of the basis for the solution subspace while minimizing the number of global synchronizations in parallel computing environments. We compare our novel method with the state-of-the-art randomized and deterministic s-step GMRES methods in terms of numerical stability, convergence, performance, and scalability. Numerical experiments on a large cluster show that with suitable parameter settings the randomized GMRES methods generally outperform the parallel deterministic s-step method BCGSI2-GMRES. Our novel RTBGS-GMRES method outperforms the other methods and achieves speedups of about 2× and about 4× over BCGSI2-GMRES for two different basis types.