Parallel algebraic multigrid based on subdomain blocking

Algebraisches Mehrgitter (AMG) bietet Ansätze zur Entwicklung rein algebraischer Verfahren zur effizienten Lösung großer Gleichungssysteme, die auf unstrukturierten, zwei- oder dreidimensionalen Gittern basieren. Während sequentielles AMG zur Lösung von Problemen mit mehreren Millionen Unbekannten benutzt werden kann, setzt eine weitere Erhöhung der Problemgröße eine effiziente Parallelisierung voraus. Weil sich, im Gegensatz zu geometrischen Mehrgitterverfahren, die Vergröberungshierarchie und die zugehörigen Grobgitteroperatoren in einer Aufsatzphase von AMG dynamisch entwickeln, ist eine direkte Parallelisierung sehr kompliziert. Darüberhinaus würde eine "naive" Parallelisierung unvorhersehbare und überaus komplexe Kommunikationsmuster erfordern, mit der Konsequenz einer ernsten Beschränkung der erreichbaren Skalierbarkeit, insbesondere der ohnehin vergleichsweise teuren Aufsatzphase. In diesem Papier betrachten wir eine klassische AMG-Variante, die sich als sehr robust und effizient bei der Lösung großer Gleichungssysteme erwiesen hat, die bei der Diskretisierung elliptischer Differentialgleichungen mit finiten Differenzen oder finiten Volumen entstehen. Basierend auf einer einfachen Partitionierung der Variablen (durch eines der vielen algebraischen Partitionierungstools wie z. B. Metis), schlagen wir einen Parallelisierungsansatz vor, bei dem die Kommunikation minimiert wird ohne in komplexen Anwendungen das Konvergenzverhalten nachhaltig zu verschlechtern. Wir präsentieren Ergebnisse für verschiedene industrielle Anwendungen aus den Bereichen CFD und Ölreservoir-Simulation.

The algebraic multigrid (AMG) approach provides a purely algebraic means to tackle the efficient solution of systems of equations posed on large unstructured grids, in 2D and 3D. While sequential AMG has been used for increasingly large problems (with several million unknowns), its application to even larger applications requires a parallel version. Since, in contrast to geometric multigrid, the hierarchy of coarser levels and the related operators develop dynamically during the setup phase of AMG, a direct parallelization is very complicated. Moreover, a "naive" parallelisation would, in general, require unpredictable and highly complex communication patterns which seriously limit the achievable scalability, in particular of the costly setup phase. In this paper, we consider a classical AMG variant which has turned out be highly robust and efficient in solving large systems of equations corresponding to elliptic PDEs, discretized by finite differences or finite volumes. Based on a straightforward partitioning of variables (using one of the available algebraic partitioning tools such as Metis), a parallelisation approach is proposed which minimizes the communication without sacrificing convergence in complex situations. Results will be presented for industrial CFD and oil-reservoir simulation applications on distributed memory machines, including PC-clusters.