Skip to main content
Back

FAU Erlangen Evolves AMG Solvers That Beat Hand-Tuned Baselines by 2.1x

Genetic programming builds unconventional algebraic multigrid cycles from proven building blocks, outperforming hand tuned solvers by up to 2.1x in hypre benchmarks.

Pro

  • Grammar-guided genetic programming evolves non-recursive AMG cycles from proven building blocks in EvoStencils
  • Evolved cycles integrate non-intrusively with hypre's BoomerAMG, no neural networks required
  • Search space of ~10^23 cycle configurations is intractable to tune by hand
  • Multi-objective NSGA-II optimizes cost per iteration and convergence rate simultaneously
  • Achieves up to 2.1x speedup over default hypre and 1.8x over hand tuned V-cycles
  • Generalizes across problem sizes to 10^9 unknowns and adapts to time-stepping simulations

Algebraic multigrid (AMG) is one of those quietly essential algorithms holding up much of scientific computing. It solves the giant sparse linear systems that fall out of discretized partial differential equations, and it does so with near-linear complexity in the number of unknowns. Getting good performance depends on a stack of interlocking choices, smoothers, cycle types, relaxation weights, coarsening strategies, that even experts struggle to tune by hand.

A team from FAU Erlangen-Nuremberg, Lawrence Livermore National Laboratory, and CERFACS is proposing a different route. Rather than learning multigrid components with neural networks, they use grammar-guided genetic programming to evolve entire AMG cycles from a library of proven algorithmic pieces, and the evolved cycles beat both default and hand-tuned baselines in the widely used hypre solver library.

Overview of grammar-guided evolutionary AMG design workflow

Why hand tuning falls off a cliff

Standard multigrid cycles like V, W, or F cycles are recursive: the same smoothing pattern gets applied at every level of the grid hierarchy. That is convenient, but it leaves a lot of performance on the table. The authors define flexible cycling as arbitrary, non-recursive sequences of smoothing and coarse-grid correction with a different smoother allowed at each step.

With five flexible levels, up to three pre/post smoothing steps, and six admissible smoothers, the number of possible cycles is roughly 2 x 10^23, and that is a conservative estimate assuming a fixed topology. No human is searching that space by intuition.