Evolving Algebraic Multigrid Methods Using Grammar-Guided Genetic Programming

Dinesh Parthasarathy · 2024

Read Evolving Algebraic Multigrid Methods Using Grammar-Guided Genetic Programming by Dinesh Parthasarathy (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-05852.txt.

Introduction

Dinesh Parthasarathy and co-authors evolve solver methods in a 2024 computing paper. Multigrid methods solve large equation systems fast, but their speed hinges on hand-picked parts and standard cycle shapes. The team instead bred new cycles with genetic programming guided by grammar rules.

Their flexible cycles choose smoothers and weights freely at each step. The evolved methods were built into a standard solver library and tuned for two jobs: a standalone solver for a lopsided three-dimensional problem, and a preconditioner inside a multiphysics code. The bred cycles beat the standard V, F, and W shapes on efficiency. The work shows that automated search can find solver designs humans would not try.

Catalog record

CREATORDinesh Parthasarathy
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-05852

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Evolving Algebraic Multigrid Methods Using Grammar-Guided Genetic Programming Thanks: Presented at the Copper Mountain Conference on Iterative Methods, April 2024. Dinesh Parthasarathy Abstract Multigrid methods despite being known to be asymptotically optimal algorithms, depend on the careful selection of their individual components for efficiency. Also, they are mostly restricted to standard cycle types like V-, F-, and W-cycles. We use grammar rules to generate arbitrary-shaped cycles, wherein the smoothers and their relaxation weights are chosen independently at each step within the cycle. We call this a flexible multigrid cycle. These flexible cycles are used in Algebraic Multigrid (AMG) methods with the help of grammar rules and optimized using genetic programming. The flexible AMG methods are implemented in the software library of hypre, and the programs are optimized separately for two cases: a standalone AMG solver for a 3D anisotropic problem and an AMG preconditioner with conjugate gradient for a multiphysics code. We observe that the optimized flexible cycles provide higher efficiency and better performance than the standard cycle types. keywords Algebraic Multigrid Methods, Genetic Programming, Context-Free Grammar † † runningheads: Evolving AMG Methods Using Grammar-Guided Genetic Programming / Dinesh Parthasarathy In collaboration with: Wayne Bradford Mitchell, Harald Köstler, 1 Introduction Multigrid methods are a class of highly efficient algorithms for solving large systems of discretized partial differential equations. The selection of algorithmic components in a multigrid method plays an important role in determining its efficiency. The task of designing an efficient multigrid method is a non-trivial one. Leveraging the recent advances in AI ( AI ), efforts have been made to find optimal multigrid components, such as smoothers [ 6 ] , intergrid operators [ 5 , 9 , 8 , 7 ] , and coarsening schemes [ 14 ] . We take a complementary approach and construct efficient multigrid cycles from a set of available multigrid components. Traditional multigrid methods employ recursive cycle types such as V-, W-, F, or the more recent \kappa -cycles [ 1 ] . However, we use a so-called flexible multigrid cycle , which can arbitrarily cycle up or down in a non-recursive manner. Also, the choice of smoothers and their relaxation weights can be made individually for each step in the cycle (Fig 1(b) ). These flexible cycles are challenging to hand-tune due to their extensive search space, but they can be formulated as a program optimization task. This way, we aim to exploit the inherent flexibility in the cycling structure, with the intent of discovering methods more efficient than the standard cycling types. Schmitt et al. use a similar approach to construct efficient grammar-guided GMG ( GMG ) methods [ 13 , 12 ] . This involves the automatic generation of GMG programs evolved using genetic programming. We adapt this methodology to construct efficient AMG ( AMG ) methods. This approach is used to optimize an AMG method as a solver for a 3D anisotropic problem and then as a preconditioner with PCG ( PCG ) for a multiphysics simulation. The constructed methods are evaluated and compared to optimized reference methods with standard AMG cycling. (a) Standard multigrid cycles (b) Flexible multigrid cycles Figure 1 : Visual representation of the cycling structure in a multigrid method. The color of the node denotes the smoother type with its relaxation weights indicated inside. 2 Background GP ( GP ) is a research area in AI that deals with the evolution of computer code. It is one of the branches of EA , following Darwin’s principle of natural selection. The general approach of GP is to apply a population of programs to a given problem, and compare their performance (fitness) relative to each other. Operators inspired by genetics (crossover, mutation) are applied to selected programs from the population (parents) such that in time better programs (offsprings) emerge by evolution. This principle is applied iteratively for multiple generations until a desirable population of programs is obtained [ 2 , 11 ] . In problems where the programs are required to conform to a specific structure (for eg. multigrid methods), grammar rules can be used to constrain the evolutionary process such that only valid programs are produced. G3P ( G3P ) is an extension of traditional GP systems that use CFG to impose such constraints on the initial population and subsequent genetic operations. Exploiting domain knowledge using CFG helps in eliminating invalid programs and speeds up the optimization process [ 15 , 10 ] . 3 Method Consider a system of linear equations Au=f , with a coarser level system A_{c}u_{c}=f_{c} , for the residual equations. Every step during the solve phase of an AMG method can be written in the form v^{i+1}\leftarrow v^{i}+\omega B(f-Av^{i}) , where v^{i} is an approximate solution at iteration i , B is an operator and \omega\in\mathbb{R} is a relaxation factor for a smoothing step or a scaling factor for a CGC ( CGC ) step. For instance, a Jacobi smoothing step can be defined as v^{i+1}\leftarrow v^{i}+\omega D^{-1}(f-Av^{i}) , where D=diag(A) . Similarly, the CGC step can be expressed as v^{i+2}\leftarrow v^{i+1}+\omega P{A_{c}}^{-1}P^{T}(f-Av^{i+1}) . Here, P is the interpolation operator that maps the coarse system to the original system of equations and P^{T} is the transpose that maps from the original system to the coarser level. Substituting v^{i+1} from the previous expression here, yields a single expression for a two-grid AMG method with Jacobi pre-smoothing. This approach is extensible to multiple levels, and substituting subexpressions recursively creates a single final expression that maps uniquely to an arbitrary flexible multigrid cycle (Fig. 1(b) ). Schmitt et al. designed a CFG for multigrid methods defining a list of rules to generate such expressions automatically [ 13 ] . We use this CFG to generate different multigrid cycles for a given AMG setup. This lets us automatically generate an initial population of AMG programs and further discover optimal AMG cycles using G3P . 4 Implementation The BoomerAMG 1 1 1 https://hypre.readthedocs.io/en/latest/solvers-boomeramg.html implementation from the software library hypre is used to generate the AMG programs. Additional interfaces are added and implemented so that AMG methods with flexible cycling can be defined and used within the hypre framework 2 2 2 https://github.com/dinesh-parthasarathy/hypre . The AMG expression generated from the CFG is transformed to corresponding input arguments for BoomerAMG . Executing each program returns the solve time and convergence factor as the fitness measure for the optimization. The optimization is performed using the EvoStencils framework 3 3 3 https://github.com/jonas-schmitt/evostencils . This uses the CFG introduced earlier to generate high-level representations of multigrid methods, and the DEAP library 4 4 4 https://deap.readthedocs.io/en/master/ for applying evolutionary algorithms. We adapt this framework to include AMG components from hypre during expression generation. To eliminate redundant AMG setup times during fitness evaluation, the program individuals are grouped into batches of size b , with one setup phase per batch, and then the solve phase for the individual solvers is executed in succession (Fig. 2 ). The batches are distributed across multiple processes using MPI bindings 5 5 5 https://mpi4py.readthedocs.io . Figure 2 : Software setup 5 Experimental Setup We evaluate our approach to discover efficient AMG methods when used as solvers and preconditioners. During the optimization, the AMG setup phase is fixed.

Read the complete text