Optimizing Geometric Multigrid Methods with Evolutionary Computation
For many linear and nonlinear systems that arise from the discretization of partial 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 framework. We demonstrate our approach by constructing multigrid solvers for the steady-state heat equation with constant and variable coefficients that consistently perform better than common V- and W-cycles.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Automating the Design of Multigrid Methods with Evolutionary Program Synthesis
Many of the most fundamental laws of nature can be formulated as partial differential equations (PDEs). Understanding these equations is, therefore, of exceptional importance for many branches of modern science and engin…
Code GenerationProgram SynthesisAutomated Grammar-based Algebraic Multigrid Design With Evolutionary Algorithms
Although multigrid is asymptotically optimal for solving many important partial differential equations, its efficiency relies heavily on the careful selection of the individual algorithmic components. In contrast to rece…
Towards Automated Algebraic Multigrid Preconditioner Design Using Genetic Programming for Large-Scale Laser Beam Welding Simulations
Multigrid methods are asymptotically optimal algorithms ideal for large-scale simulations. But, they require making numerous algorithmic choices that significantly influence their efficiency. Unlike recent approaches tha…
Evolutionary AlgorithmsNeural Multigrid Architectures
We propose a convenient matrix-free neural architecture for the multigrid method. The architecture is simple enough to be implemented in less than fifty lines of code, yet it encompasses a large number of distinct multig…
Surrogate Modeling of Fluid Dynamics with a Multigrid Inspired Neural Network Architecture
Algebraic or geometric multigrid methods are commonly used in numerical solvers as they are a multi-resolution method able to handle problems with multiple scales. In this work, we propose a modification to the commonly-…