EvoStencils: a grammar-based genetic programming approach for constructing efficient geometric multigrid methods
Open Access
- 3 September 2021
- journal article
- research article
- Published by Springer Nature in Genetic Programming and Evolvable Machines
- Vol. 22 (4) , 511-537
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 microarchitecture.Keywords
Funding Information
- Friedrich-Alexander-Universität Erlangen-Nürnberg
This publication has 31 references indexed in Scilit:
- Optimizing the number of multigrid cycles in the full multigrid algorithmNumerical Linear Algebra with Applications, 2010
- RooflineCommunications of the ACM, 2009
- Component‐based iterative methods for sparse linear systemsConcurrency and Computation: Practice and Experience, 2006
- A Novel Multigrid Based Preconditioner For Heterogeneous Helmholtz ProblemsSIAM Journal on Scientific Computing, 2006
- Numerical solution of saddle point problemsActa Numerica, 2005
- A Genetic Search for Optimal Multigrid Components Within a Fourier Analysis SettingSIAM Journal on Scientific Computing, 2003
- Completely Derandomized Self-Adaptation in Evolution StrategiesEvolutionary Computation, 2001
- Genetic programming as a means for programming computers by natural selectionStatistics and Computing, 1994
- Multi-level adaptive solutions to boundary-value problemsMathematics of Computation, 1977
- A relaxation method for solving elliptic difference equationsUSSR Computational Mathematics and Mathematical Physics, 1962