Automating the Design of Multigrid Methods with Evolutionary Program Synthesis

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.