1. Title of the Publications
Article A:
Evolving Generalizable Multigrid-Based Helmholtz Preconditioners with Grammar-Guided Genetic Programming
Article B:
EvoStencils: a grammar-based genetic programming approach for constructing efficient geometric multigrid methods
2. Author Information
Jonas Schmitt
Chair for System Simulation, Friedrich-Alexander-Universität Erlangen-Nürnberg, Cauerstraße 11, 91058 Erlangen, Germany
email: jonas.schmitt@fau.de
phone: +49 9131 85 27910
Sebastian Kuckuk
Chair for System Simulation, Friedrich-Alexander-Universität Erlangen-Nürnberg, Cauerstraße 11, 91058 Erlangen, Germany
email: sebastian.kuckuk@fau.de
phone: +49 9131 85 67294
Harald Köstler
Chair for System Simulation, Friedrich-Alexander-Universität Erlangen-Nürnberg, Cauerstraße 11, 91058 Erlangen, Germany
email: harald.koestler@fau.de
phone: +49 9131 85 28359
3. Corresponding Author
Jonas Schmitt
jonas.schmitt@fau.de
4. Paper Abstracts
Article A:
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.
Article B:
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 microarchitecture.
5. Competition Criteria
(D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created.
(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.
(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
(G) The result solves a problem of indisputable difficulty in its field.
6. Statement Why the Results Satisfy the Criteria (D), (E), (F) and (G)
For the sake of clarity, we consider the individual competition criteria in order of importance instead of alphabetic order.
(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.
Since the invention of modern computers, a long succession of algorithms for solving partial differential equations (PDEs) numerically has been developed by the leading experts in the field. A good overview of the variety of numerical solvers that have been invented within the last century is, for instance, provided in [1]. If properly constructed, multigrid methods, to this day, represent the most efficient methods for solving PDEs, which has been demonstrated in numerous applications [2,3]. While many different multigrid variants have been developed and reported in the literature, in Article A, we demonstrate that our grammar-based approach can discover multigrid methods of novel structure and superior efficiency compared to all known variants for a long-standing and outstandingly difficult problem, the indefinite Helmholtz equation. In addition, in Article B, we show that the same approach can also be successfully applied to several other common PDEs.
[1] Saad, Y. (2003). Iterative methods for sparse linear systems. Society for Industrial and Applied Mathematics.
[2] Gmeiner, B., Rüde, U., Stengel, H., Waluga, C., & Wohlmuth, B. (2015). Towards textbook efficiency for parallel multigrid. Numerical Mathematics: Theory, Methods and Applications, 8(1), 22-46.
[3] Trottenberg, U., Oosterlee, C. W., & Schuller, A. (2000). Multigrid. Elsevier.
(G) The result solves a problem of indisputable difficulty in its field.
The difficulty of solving the indefinite Helmholtz equation numerically is well-known and reported in many publications, such as [4]. In Article A, we demonstrate that the multigrid preconditioners evolved by our approach are able to handle Helmholtz problems of tremendous size and difficulty, for which all known multigrid variants fail to achieve convergence.
[4] Ernst, O. G., & Gander, M. J. (2012). Why it is difficult to solve Helmholtz problems with classical iterative methods. Numerical analysis of multiscale problems, 325-363.
(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
For the indefinite Helmholtz equation considered in Article A, a functioning multigrid preconditioner was only discovered in 2006 by Erlangga et al. [5], which currently represents one of the most cited works in this area.
Furthermore, while Poisson's equation, as considered in Article B, now represents a widely-used model problem for multigrid methods, the study of this equation led to the original invention of multigrid by Fedorenko and Brandt [6]. Therefore, the automatic discovery of competitive numerical methods for solving this equation can be regarded as an achievement on its own.
[5] Erlangga, Y. A., Oosterlee, C. W., & Vuik, C. (2006). A novel multigrid based preconditioner for heterogeneous Helmholtz problems. SIAM Journal on Scientific Computing, 27(4), 1471-1492.
[6] Brandt, A. (1977). Multi-level adaptive solutions to boundary-value problems. Mathematics of computation, 31(138), 333-390.
(D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created.
While we have only briefly analyzed the algorithmic structure of the multigrid methods discovered in Article A, the two methods reported in this work comprise novel computational patterns that have not yet been reported in any other publication. This observation represents a strong argument that a further mathematical analysis of the discovered computational structures has the potential to lead to the discovery of a class of entirely new multigrid methods.
7. Full Citation
Article A:
Schmitt, J., & Köstler, H. (2022). Evolving Generalizable Multigrid-Based Helmholtz Preconditioners with Grammar-Guided Genetic Programming. arXiv preprint arXiv:2204.12846.
To appear in "GECCO '22: Proceedings of the 2022 Genetic and Evolutionary Computation Conference" under the following DOI: https://doi.org/10.1145/3512290.3528688
Article B:
Schmitt, J., Kuckuk, S., & Köstler, H. (2021). EvoStencils: a grammar-based genetic programming approach for constructing efficient geometric multigrid methods. Genetic Programming and Evolvable Machines, 22(4), 511-537.
DOI: https://doi.org/10.1007/s10710-021-09412-w
8. Prize Money Breakdown
If any prize money is granted, it should be awarded entirely to the first author of both papers (Jonas Schmitt). This decision was made in mutual agreement between all authors.
9. A Statement Indicating Why this Entry Could Be the "Best"
Many of the most fundamental laws of nature can be formulated as partial differential equations (PDEs). Understanding these equations is, therefore, foundational for many branches of modern science and engineering. Since, for many PDEs, it is unknown whether a general solution exists, the efficient approximate solution of these equations represents one of humanity's greatest challenges. Within Article A and B, we demonstrate that grammar-guided genetic programming (GGGP) is capable of evolving multigrid methods of novel structure that achieve strong generalization and efficiency in solving PDE-based problems.
Even though generalization is one of the main goals of automated solver generation, artificial intelligence-based methods often fail to achieve it. Recently, especially data-driven and physics-informed machine learning models have made enormous progress in solving PDEs. While these methods have shown promise in replacing classical numerical solvers, they typically rely on a fixed-size neural network and can, thus, not easily be generalized to other problem sizes.
In contrast, the representation of a solver in a symbolically-manipulable formal language allows us to apply the same method to problems of different size without adapting its internal structure. We utilize this property to implement an evolutionary search method that enables the systematic generalization of multigrid to a given problem domain. Furthermore, as our newly-developed formal representation of multigrid methods can easily be translated into a human-readable format, it can be understood and analyzed by a domain expert. To investigate whether our approach can be successfully applied to challenging PDEs, in Article A, we consider an outstandingly-difficult benchmark problem, the indefinite Helmholtz equation, for which we evolve solvers that achieve superior generalization and efficiency compared to all known multigrid variants.
Finally, in both of our papers, we demonstrate that our implementation of GGGP, which is freely available in the form of the open-source library EvoStencils [7], can be scaled up on recent clusters and supercomputers. In particular in Article A, we perform each experiment on eight nodes with a total number of 384 CPU cores of SuperMUC-NG, currently one of the largest supercomputing systems in Europe.
[7] EvoStencils: https://github.com/jonas-schmitt/evostencils
10. Evolutionary Computation Type
GGGP (Grammar-Guided Genetic Programming)
11. Publication Date
Paper A: The publication has been unconditionally accepted at GECCO 2022. As a proof, the list of accepted papers can already be found on the GECCO website: https://gecco-2022.sigevo.org/Accepted-Papers
Paper B: Published on September 03, 2021.