Automated Grammar-based Algebraic Multigrid Design With Evolutionary Algorithms

Dinesh Parthasarathy; Wayne Mitchell; Arjun Gambhir; Harald Köstler; Ulrich Rüde

cs.CEMar 18, 2026

Automated Grammar-based Algebraic Multigrid Design With Evolutionary Algorithms

Authors: Dinesh Parthasarathy, Wayne Mitchell, Arjun Gambhir, Harald Köstler, Ulrich Rüde

Organizations: Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Erlangen, Germany · Lawrence Livermore National Laboratory, USA · CERFACS, Toulouse, France and Department of Applied Mathematics, VSB-Technical University of Ostrava, Ostrava, Czech Republic

Abstract

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 recent approaches that can optimize certain multigrid components using deep learning techniques, we adopt a complementary strategy, employing evolutionary algorithms to construct efficient multigrid cycles from proven algorithmic building blocks. Here, we will present its application to generate efficient algebraic multigrid methods with so-called flexible cycling, that is, level-specific smoothing sequences and non-recursive cycling patterns. The search space with such non-standard cycles is intractable to navigate manually, and is generated using genetic programming (GP) guided by context-free grammars. Numerical experiments with the linear algebra library, hypre, demonstrate the potential of these non-standard GP cycles to improve multigrid performance both as a solver and a preconditioner.

Figures & tables

Figure 1: A high-level overview of the proposed automated AMG design workflow: given an input problem, the approach uses grammars, evolutionary algorithms, and high-performance solvers to generate flexible AMG cycles. Nodes in the resulting cycles are color-coded to indicate different smoothing operations.

Figure 3: An overview of the software setup for the automated AMG design.

solver	ordering	$S^{pre}$	$\nu_{1}$	$S^{post}$	$\nu_{2}$	$w_{i}$	$w_{o}$
default	lexicographic	$S^{l_{1}}_{\text{GSF}}$	1	$S^{l_{1}}_{\text{GSB}}$	1	n/a	n/a
tuned 1	C-F	$S^{l_{1}}_{\text{GSF}}$	1	$S^{l_{1}}_{\text{GSF}}$	1	n/a	n/a
tuned 2	C-F	$S^{H}_{\text{GSF}}$	1	$S^{H}_{\text{GSF}}$	1	1.1	0.9
tuned 3	lexicographic	$S^{l_{1}}_{\text{GSF}}$	1	$S^{l_{1}}_{\text{GSF}}$	1	n/a	n/a
tuned 4	C-F	$S^{l_{1}}_{\text{Jacobi}}$	1	$S^{l_{1}}_{\text{Jacobi}}$	1	n/a	n/a
tuned 5	lexicographic	$S^{H}_{\text{GSF}}$	1	$S^{H}_{\text{GSF}}$	1	1.1	0.9

Table 1: BoomerAMG parameters for default and tuned reference AMG solvers.

Panel of Figure 4 — Figure 4: Evolution of AMG individuals with respect to cost per iteration and convergence rate , progressing from an initial random population to the final generation (clockwise from top left: initial population , generation 1 , generation 10 , generation 100 ). The dots represent the individuals, and are colored separately, representing each of the five independent runs of the G3P algorithm.

Panel of Figure 5 — Figure 5: AMG cycling structure for the selected GP solvers, excluding the depiction of weighting parameters $\omega_{i}$ , $\omega_{0}$ , $\omega$ , and $\alpha$ .

configuration			default		tuned 1		tuned 2		tuned 3		tuned 4		tuned 5		tuned 6
$c_{1}$	$c_{2}$	$c_{3}$	T(ms)	N	T(ms)	N	T(ms)	N	T(ms)	N	T(ms)	N	T(ms)	N	T(ms)	N
1	1	1	381	22	375	19	351	17	349	21	403	16	324	18	379	18
1	1	1e-3	399	19	276	11	289	11	279	14	295	9	280	13	258	10
1	1	1e-5	398	19	275	11	288	11	278	14	298	9	280	13	256	10
1	1e-3	1e-3	365	21	190	9	194	9	219	13	178	7	236	13	236	11
1	1e-3	1e-5	365	21	189	9	193	9	219	13	178	7	235	13	236	11

Table 2: Performance of reference solvers (top) and GP solvers (bottom) for different anisotropy configurations from eq. 15 with

10^{6}

unknowns.

	default		tuned 1		tuned 2		tuned 3		tuned 4		tuned 5		tuned 6
$N_{d}$	T(ms)	N	T(ms)	N	T(ms)	N	T(ms)	N	T(ms)	N	T(ms)	N	T(ms)	N
100	402	19	259	11	275	11	276	14	286	9	278	13	258	10
200	485	20	336	12	324	11	342	15	387	10	317	13	330	11
300	530	21	380	13	368	12	352	15	448	11	350	14	406	13
400	572	22	460	15	452	14	395	16	496	12	361	14	448	14
500	591	22	573	17	498	15	419	17	550	13	404	15	489	15

Table 3: Weak scaling results of the anisotropic Poisson problem, from the initial problem

\tilde{\mathcal{D}}

with

10^{6}

unknowns scaled to

10^{9}

unknowns, for reference solvers (top) and GP solvers (bottom).

Figure 6: Convergence plots of GP -31, default

V(1,1)

, and ‘tuned-1’

V(1,1)

AMG solver on problem

\tilde{\mathcal{D}}

(left), and the eigenvalue distribution of the respective iteration matrices on a smaller

10^{3}

variant (right).

Panel of Figure 7 — Figure 7: Initial conditions of the zrad3D problem. A source is applied to the left side of the block as it is pictured above. As the problem evolves, radiation flows through the block, and the matter and radiation fields come into equilibrium with each other.

Figure 8: (Left) Final population of evolved PCG programs, shown as blue dots, with the resulting Pareto front highlighted in red line. (Right) Comparison of solve time and CG iterations between the selected GP-PCG programs and the reference PCG configurations for the proxy $\tilde{\mathcal{D}}$ .

Figure 9: Visual representation of the GP-57 AMG preconditioner cycle.

Figure 10: Performance of GP-PCG solvers compared to reference solvers, measured over the first 40 time steps of the zrad3D problem with

10^{6}

DOFs.

	default		tuned		GP-57		speedup
DOFs	T(s)	N	T(s)	N	T(s)	N	$\eta_{1}$	$\eta_{2}$
1M	9.0	267	8.8	373	5.4	172	1.66	1.63
8M	12.4	323	11.8	433	7.7	210	1.60	1.53
64M	15.2	387	14.7	519	9.2	240	1.66	1.60

Table 4: Weak scaling results of default, tuned and GP preconditioned CG solvers for the zrad3D problem evaluated over the first

40

time steps on the RZHound system.

Figure 11: (Left) The relative contribution of diagonal versus off-diagonal elements in the system matrix throughout the simulation. (Right) CG convergence of the electron conduction problem with a simple diagonal preconditioner.

Figure 12: CG convergence on the radiation diffusion (left) and electron conduction (right) systems across the simulation, using the hybrid solver interface with the GP-57 preconditioner, and a convergence threshold set to

0.65

Automated Algorithm Discovery

Automated algorithm discovery develops methods that generate and test executable algorithms for optimization, science, software, and machine learning.

See all 170 papers

Acceleration of an algebraic multigrid pressure solver using graph neural networks
Jun 17, 2026Eric Chillón, Artur K. Lidtke, Nguyen Anh Khoa Doan +1Graph Neural Networks PDE Solving
Faculty of Mechanical Engineering, Delft University of Technology, The Netherlands · Maritime Research Institute Netherlands, The Netherlands · Department of Aeronautics, Imperial College London, United Kingdom
RAPNet: Accelerating Algebraic Multigrid with Learned Sparse Corrections
May 26, 2026Yali Fink, Ido Ben-Yair, Lars Ruthotto +1Graph Neural Networks Partial Differential Equations
Institute for Interdisciplinary Computational Sciences, Faculty of Computer and Information Science, Ben-Gurion University of the Negev, Be’er Sheva, Israel · Department of Mathematics and Computer Science, Emory University, Atlanta, GA, USA.
Graph Neural Multilevel Preconditioners for Iterative Solvers
Jul 30, 2026Zechen Zhang, Rui Peng Li, Yousef SaadGraph Neural Networks
University of Minnesota Minneapolis, MN, USA · CASA, Lawrence Livermore National Laboratory Livermore, CA, USA

Jun 17, 2026J/K move · Enter open · S save

Acceleration of an algebraic multigrid pressure solver using graph neural networks

Eric Chillón, Artur K. Lidtke, Nguyen Anh Khoa Doan, Bernat Font

Faculty of Mechanical Engineering, Delft University of Technology, The Netherlands · Maritime Research Institute Netherlands, The Netherlands · Department of Aeronautics, Imperial College London, United Kingdom

Graph Neural Networks PDE Solving Computational Fluid Dynamics

Open paper AskPDF arXiv

Solving the pressure-Poisson equation remains the primary computational bottleneck in incompressible unstructured flow solvers primarily due to the inherent sensitivity of traditional linear solvers to mesh irregularities. This work introduces a data-driven algebraic multigrid (AMG) smoother that uses a modified graph convolutional isomorphism network (GCIN). The graph neural network predicts optimal polynomial coefficients to construct a sparse pseudo-inverse operator across diverse grid topologies. The coefficients are optimized to reduce the residual after each V-cycle iteration. By directly capturing the algebraic structure of the system from the sparse coefficient matrix, the proposed method maintains the solver's linearity while adapting to local anisotropies in unstructured grids. Our framework demonstrates significant performance gains by reducing the number of V-cycles required for a given tolerance and delivering wall-clock speedups from 4% to 37% across diverse benchmarks. Notably, the model exhibits robust generalization by maintaining efficiency on meshes up to 128 times larger than those seen in training, and by accelerating the solver's convergence on unseen industry-relevant problems such as the AirfRANS dataset.

Abstract

Automated Algorithm Discovery

Explore similar work

Acceleration of an algebraic multigrid pressure solver using graph neural networks

RAPNet: Accelerating Algebraic Multigrid with Learned Sparse Corrections

Graph Neural Multilevel Preconditioners for Iterative Solvers