Automating the Design of Multigrid Methods with Evolutionary Program Synthesis

dc.contributorKöstler, Harald
dc.contributorMachado, Penousal
dc.contributorFey, Dietmar
dc.contributor.advisorKöstler, Harald
dc.contributor.authorSchmitt, Jonas
dc.date.accessioned2024-05-13T06:22:23Z
dc.date.available2024-05-13T06:22:23Z
dc.date.issued2024
dc.descriptionParallel erschienen als Druckausgabe bei FAU University Press, ISBN: 978-3-96147-731-9
dc.description.abstractMany 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.en
dc.description.abstractViele 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.de
dc.format.extentxvi, 222 Seiten
dc.identifier.isbn978-3-96147-732-6
dc.identifier.urihttps://open.fau.de/handle/openfau/31086
dc.identifier.urihttps://doi.org/10.25593/978-3-96147-732-6
dc.language.isoen
dc.provenanceFriedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Technische Fakultät
dc.publisherFAU University Press
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectmultigrid
dc.subjectgenetic programming
dc.subjectautomated algorithm design
dc.subjectprogram synthesis
dc.subjectformal grammar
dc.subjectcomputer simulation
dc.subjectartificial intelligence
dc.subjectMehrgitterverfahren
dc.subjectGenetische Programmierung
dc.subjectProgrammsynthese
dc.subjectFormale Grammatik
dc.subjectComputersimulation
dc.subjectKünstliche Intelligenz
dc.subject.ddcDDC Classification::0 Informatik, Information und Wissen, allgemeine Werke::00 Informatik, Wissen und Systeme::006 Spezielle Computerverfahren
dc.subject.ddcDDC Classification::0 Informatik, Information und Wissen, allgemeine Werke::00 Informatik, Wissen und Systeme::003 Systeme
dc.subject.ddcDDC Classification::5 Naturwissenschaften::51 Mathematik::518 Numerische Analysis
dc.subject.ddcDDC Classification::0 Informatik, Information und Wissen, allgemeine Werke::00 Informatik, Wissen und Systeme::005 Softwareentwicklung, Software, Daten, IT-Sicherheit
dc.titleAutomating the Design of Multigrid Methods with Evolutionary Program Synthesisen
dc.titleAutomatisierung des Entwurfs von Mehrgitterverfahren mit Evolutionärer Programmsynthesede
dc.typedoctoralthesis
local.date.accepted2023-12-14
local.publisherplaceErlangen
local.sendToDnbfree
local.series.nameFAU Studien aus der Informatik
local.series.number19
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Jonas_Schmitt_Diss_FAU.pdf
Size:
1.95 MB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
19.04 KB
Format:
Item-specific license agreed to upon submission
Description:
Faculties & Collections