Hybrid Geometric-Algebraic Matrix-Free Multigrid on Spacetrees
Marion Weinzierl · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2013
Linear solvers are the motor for many computer simulations that are based on partial differential equations (PDEs).For a wide range of problems, multigrid solvers belong to the most efficient ones.Their convergence rate is mostly independent of the mesh size of the underlying problem discretisation, and thus they have optimal complexity.During the last two decades, there has been a strong focus on algebraic multigrid, which can easily employ accurate unstructured grids and is very robust.But increased accuracy requirements, complex models, and huge amounts of data from engineering, scientific or, e.g., medical applications require the use of supercomputers.Their architecture forces researchers to rethink their algorithms and data handling.For example, algebraic multigrid suffers from a serious performance decrease on parallel architectures, due to high setup costs and communication overhead, unstructured data access, indirect addressing, and a large memory footprint.Therefore, the less robust geometric multigrid is now reconsidered.For the data, spacetrees have turned out to not only provide fast data access but also an efficient structure for performing the computations.This work combines the advantages of geometric and algebraic multigrid.It defines the solver on a geometrically coarsened structured grid, but instead of geometric multigrid operations the much more robust BoxMG by Dendy using operatordependent intergrid transfer operators and Petrov-Galerkin coarse-grid operators is used.The solver is implemented on a spacetree as underlying data-and computational structure, ensuring efficient data handling, data locality, and low communication overhead.It is integrated into and parallelised in the PDE solver framework Peano, which has a small memory footprint and is very memory-efficient.This results in a robust solver that is tailored to high performance computers. ZusammenfassungLineare Löser sind der Motor für viele Computersimulationen, die auf Partiellen Differentialgleichungen (Partial Differential Equations, PDEs) basieren.Für eine Vielzahl von Problemen gehören Mehrgitterlöser zu den effizientesten Lösern.Ihre Konvergenzrate ist meist unabhängig von der Gitterweite der zugrundeliegenden Problem-Diskretisierung.In diesem Sinne haben sie optimale Komplexität.Während der letzten beiden Jahrzehnte bestand eine starke Fokussierung auf algebraisches Mehrgitter, das problemlos mit unstrukturierten Gitter umgehen kann und sehr robust ist.Jedoch erfordern erhöhte Genauigkeitsanforderungen, komplexe Modelle und riesige Datenmengen aus Ingenieurs-, Wissenschafts-oder Medizinanwendungen die Verwendung von Großrechnern.Deren Architektur führt dazu, dass Wissenschaftler ihre Algorithmen und die Datenverwaltung und -verarbeitung überdenken müssen.Algebraisches Mehrgitter, z.B., erfährt auf parallelen Architekturen einen ernsthaften Leistungseinbruch.Dieser liegt in hohen Setup-Kosten, Zusatzkosten für die Kommunikation, unstrukturiertem Datenzugriff, indirekter Adressierung und einem hohen Speicherverbrauch begründet.Infolgedessen wird seit einiger Zeit das weniger robuste geometrische Mehrgitter wieder in Betracht gezogen.Als Datenstruktur haben sich Spacetrees bewährt, da sie nicht nur schnellen Datenzugriff gewährleisten, sondern auch eine effiziente Rechenstruktur darstellen.Diese Arbeit kombiniert die Vorteile von geometrischem und algebraischem Mehrgitter.Sie definiert den Löser auf einem geometrisch vergröberten Gitter, anstelle von geometrischen Mehrgitteroperationen wird jedoch das viel robustere BoxMG von Dendy, welches operator-abhängige Intergrid-Transfer-Operatoren und Petrov-Galerkin-Grobgitteroperatoren verwendet, eingesetzt.Der Löser wird auf einem Spacetree als zugrundeliegende Daten-und Rechenstruktur implementiert, wodurch eine effiziente Datenverarbeitung, Datenlokalität und geringe Kommunikationskosten gewährleistet sind.Er wird in das PDE-Löser-Framework Peano, das einen geringen Speicherverbrauch hat und sehr speichereffizient ist, integriert und darin parallelisiert.Dadurch erhalten wir einen robusten Löser, der die Anforderungen von Hochleistungsrechnern erfüllt. DanksagungAn dieser Stelle möchte ich mich bei den Leuten bedanken, die mich während der Zeit meiner Promotion begleitet und unterstützt haben.Meinen Prüfern Hans-Joachim Bungartz, Irad Yavneh und Miriam Mehl danke ich für die Übernahme dieses Amtes.Hans danke ich inbesondere für seine Funktion als mein Doktorvater und die Anregungen und Anmerkungen zu dieser Arbeit, außerdem für seine Unterstützung während meines Mutterschutzes und der Elternzeit.Vielen Dank an Miriam für die Diskussionen und die ausführlichen Hinweise und Verbesserungsvorschläge zu meiner Arbeit.Irad danke ich für all das, was ich von ihm über Mehrgitteralgorithmen lernen durfte, für sein Engagement und die Zeit, die er sich für unsere Zusammenarbeit genommen hat, für seine Anleitungen und seine Hinführung zum BoxMG-Algorithmus, der nun einen Grundpfeiler dieser Arbeit darstellt.Außerdem danke ich ihm, seiner Familie und seiner Forschungsgruppe (hier insbesondere Eran Treister) für die unglaubliche Gastfreundschaft während meines Forschungsaufenthalts in Haifa.Meinen Kollegen Christoph Riesinger und Tobias Weinzierl danke