title: Automating the Design of Multigrid Methods with Evolutionary Program Synthesis
title: Automatisierung des Entwurfs von Mehrgitterverfahren mit Evolutionärer Programmsynthese
Creators: name: Schmitt, Jonas
Publisher: name: FAU University Press
Year: 2024
Subjects: subject: multigrid
subject: genetic programming
subject: automated algorithm design
subject: program synthesis
subject: formal grammar
subject: computer simulation
subject: artificial intelligence
subject: Mehrgitterverfahren
subject: Genetische Programmierung
subject: Programmsynthese
subject: Formale Grammatik
subject: Computersimulation
subject: Künstliche Intelligenz
subject: DDC Classification::0 Informatik, Information und Wissen, allgemeine Werke::00 Informatik, Wissen und Systeme::006 Spezielle Computerverfahren
subject: DDC Classification::0 Informatik, Information und Wissen, allgemeine Werke::00 Informatik, Wissen und Systeme::003 Systeme
subject: DDC Classification::5 Naturwissenschaften::51 Mathematik::518 Numerische Analysis
subject: DDC Classification::0 Informatik, Information und Wissen, allgemeine Werke::00 Informatik, Wissen und Systeme::005 Softwareentwicklung, Software, Daten, IT-Sicherheit

description: Parallel erschienen als Druckausgabe bei FAU University Press, ISBN: 978-3-96147-731-9
description: 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.
description: 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.