Solving the indefinite Helmholtz equation is not only crucial for the understanding of many physical phenomena but also represents an outstandingly-difficult benchmark problem for the successful application of numerical methods. Here we introduce a new approach for evolving efficient preconditioned iterative solvers for Helmholtz problems with multi-objective grammar-guided genetic programming. Our approach is based on a novel context-free grammar, which enables the construction of multigrid preconditioners that employ a tailored sequence of operations on each discretization level. To find solvers that generalize well over the given domain, we propose a custom method of successive problem difficulty adaption, in which we evaluate a preconditioner's efficiency on increasingly ill-conditioned problem instances. We demonstrate our approach's effectiveness by evolving multigrid-based preconditioners for a two-dimensional indefinite Helmholtz problem that outperform several human-designed methods for different wavenumbers up to systems of linear equations with more than a million unknowns. }, author = {Schmitt, Jonas and Köstler, Harald}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference}, date = {2022-07-09/2022-07-13}, doi = {10.1145/3512290.3528688}, editor = {Association for Computing Machinery}, faupublication = {yes}, isbn = {9781450392372}, keywords = {Genetic Programming, Multigrid, Preconditioning, Helmholtz Equation, Grammar-Based, Shifted Laplacian, Generalization, Multi-Objective, Partial Differential Equations, Artificial Intelligence}, pages = {1009-1018}, peerreviewed = {Yes}, series = {GECCO '22}, title = {{Evolving} {Generalizable} {Multigrid}-{Based} {Helmholtz} {Preconditioners} with {Grammar}-{Guided} {Genetic} {Programming}}, venue = {Boston, Massachusetts}, year = {2022} } @inproceedings{faucris.310125705, abstract = {We formulate a formal grammar to generate Full Approximation Scheme multigrid solvers. Then, using Grammar-Guided Genetic Programming we perform a multiobjective optimization to find optimal instances of such solvers for a given nonlinear system of equations. This approach is evaluated for a two-dimensional Poisson problem with added nonlinearities. We observe that the evolved solvers outperform the baseline methods by having a faster runtime and a higher convergence rate.}, author = {Parthasarathy, Dinesh and Schmitt, Jonas and Köstler, Harald}, booktitle = {GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion}, date = {2023-07-15/2023-07-19}, doi = {10.1145/3583133.3590734}, faupublication = {yes}, isbn = {9798400701207}, keywords = {Code Generation; Grammar-Guided Genetic Programming; Nonlinear Multigrid Methods}, note = {CRIS-Team Scopus Importer:2023-09-08}, pages = {615-618}, peerreviewed = {unknown}, publisher = {Association for Computing Machinery, Inc}, title = {{Evolving} {Nonlinear} {Multigrid} {Methods} {With} {Grammar}-{Guided} {Genetic} {Programming}}, venue = {Lisbon, PRT}, year = {2023} } @article{faucris.263599216, abstract = {For many systems of linear equations that arise from the discretization of partial differential equations, the construction of an efficient multigrid solver is challenging. Here we present EvoStencils, a novel approach for optimizing geometric multigrid methods with grammar-guided genetic programming, a stochastic program optimization technique inspired by the principle of natural evolution. A multigrid solver is represented as a tree of mathematical expressions that we generate based on a formal grammar. The quality of each solver is evaluated in terms of convergence and compute performance by automatically generating an optimized implementation using code generation that is then executed on the target platform to measure all relevant performance metrics. Based on this, a multi-objective optimization is performed using a non-dominated sorting-based selection. To evaluate a large number of solvers in parallel, they are distributed to multiple compute nodes. We demonstrate the effectiveness of our implementation by constructing geometric multigrid solvers that are able to outperform hand-crafted methods for Poisson’s equation and a linear elastic boundary value problem with up to 16 million unknowns on multi-core processors with Ivy Bridge and Broadwell microarchitectur}, author = {Schmitt, Jonas and Kuckuk, Sebastian and Köstler, Harald}, doi = {10.1007/s10710-021-09412-w}, faupublication = {yes}, journal = {Genetic Programming and Evolvable Machines}, keywords = {Grammar-guided genetic programming; Multigrid methods; Algorithm design; Code generation; Distributed computing}, peerreviewed = {Yes}, title = {{EvoStencils}: a grammar-based genetic programming approach for constructing efficient geometric multigrid methods}, url = {http://link.springer.com/article/10.1007/s10710-021-09412-w}, year = {2021} } @incollection{faucris.264494817, abstract = {Present-day stencil codes are implemented in general-purpose programming languages, such as Fortran, C, or Java, Python or derivates thereof, and harnesses for parallelism, such as OpenMP, OpenCL or MPI. Project ExaStencils pursued a domain-specific approach with a language, called ExaSlang, that is stratified into four layers of abstraction, the most abstract being the formulation in continuous mathematics and the most concrete a full, automatically generated implementation. At every layer, the corresponding language expresses not only computational directives but also domain knowledge of the problem and platform to be leveraged for optimization. We describe the approach, the software technology

differential equations the construction of an efficient multigrid solver is a challenging task. Here

we present a novel approach for the optimization of geometric multigrid methods that is based on

evolutionary computation, a generic program optimization technique inspired by the principle of

natural evolution. A multigrid solver is represented as a tree of mathematical expressions which

we generate based on a tailored grammar. The quality of each solver is evaluated in terms of

convergence and compute performance using automated Local Fourier Analysis (LFA) and roofline

performance modeling, respectively. Based on these objectives a multi-objective optimization is

performed using strongly typed genetic programming with a non-dominated sorting based selection.

To evaluate the model-based prediction and to target concrete applications, scalable implementations

of an evolved solver can be automatically generated with the ExaStencils code generation framework.

We demonstrate our approach by constructing multigrid solvers for Poisson’s equation with constant

and variable coefficients.