Automating the Design of Multigrid Methods with Evolutionary Program Synthesis

Language
en
Document Type
Doctoral Thesis
Granting Institution
Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Technische Fakultät
Issue Date
2024
Authors
Schmitt, Jonas
Editor
Publisher
FAU University Press
ISBN
978-3-96147-732-6
Abstract

Many of the most fundamental laws of nature can be formulated as partial differential equations (PDEs). However, since the general solution of many PDEs is unknown, the efficient approximate solution of these equations is one of humanity's greatest challenges. While multigrid represents one of the most effective methods for solving PDEs numerically, in many cases, the design of an efficient or at least working multigrid solver is an open problem. This thesis demonstrates that grammar-guided genetic programming, an evolutionary program synthesis technique, can discover multigrid methods of unprecedented structure that achieve a high degree of efficiency and generalization. For this purpose, we develop a novel context-free grammar that enables the automated generation of multigrid methods in a symbolically-manipulable formal language, based on which we can apply the same multigrid-based solver to problems of different sizes without having to adapt its internal structure. Treating the automated design of an efficient multigrid method as a program synthesis task allows us to find novel sequences of multigrid operations, including the combination of different smoothing and coarse-grid correction steps on each level of the discretization hierarchy.

Abstract

Viele der grundlegendsten Naturgesetze können als partielle Differentialgleichungen (PDGs) formuliert werden. Da jedoch die allgemeine Lösung vieler PDGs unbekannt ist, stellt die effiziente Näherungslösung dieser Gleichungen eine der größten Herausforderungen der Menschheit dar. Obwohl Mehrgitterverfahren eine der effektivsten Methoden zur numerischen Lösung von PDGs darstellen, ist der Entwurf eines effizienten oder zumindest funktionierenden Mehrgitterlösers in vielen Fällen ein offenes Problem. In dieser Arbeit wird gezeigt, dass grammatikgeleitete genetische Programmierung, eine evolutionäre Programmsynthesetechnik, zur Entdeckung von Mehrgitterverfahren bisher unerreichter Struktur führen kann, welche zudem einen hohen Grad an Effizienz und Generalisierung erreichen. Zu diesem Zweck entwickeln wir eine neuartige kontextfreie Grammatik, welche die automatisierte Generierung von Mehrgitterverfahren in einer symbolisch manipulierbaren formalen Sprache ermöglicht, auf deren Grundlage wir denselben mehrgitterbasierten Löser auf Probleme unterschiedlicher Größe anwenden können, ohne seine interne Struktur anpassen zu müssen. Die Behandlung des automatisierten Entwurfs effizienter Mehrgitterverfahren als Programmsyntheseproblem erlaubt es uns neuartige Sequenzen von Mehrgitteroperationen zu finden, einschließlich der Kombination von verschiedenen Glättungs- und Grobgitterkorrekturschritten auf jeder Ebene der Diskretisierungshierarchie.

Series
FAU Studien aus der Informatik
Series Nr.
19
Description

Parallel erschienen als Druckausgabe bei FAU University Press, ISBN: 978-3-96147-731-9

DOI
URN
Faculties & Collections
Zugehörige ORCIDs