Pith. sign in

REVIEW 3 major objections 6 minor 1 cited by

Evolving Algebraic Multigrid Methods Using Grammar-Guided Genetic Programming

T0 review · 3 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that arbitrary-shaped multigrid cycles, generated by a context-free grammar and optimized by genetic programming, beat standard V-, F-, and W-cycles as both standalone AMG solvers and conjugate-gradient preconditioners.

desk verdict A useful G3P-to-AMG adaptation with an overclaimed abstract; the flexible-cycle advantage is real in the experiments but confounded with per-step smoother/weight tuning. read the letter →

arxiv 2412.05852 v1 pith:R4JLCBPV submitted 2024-12-08 cs.CE cs.AIcs.NAmath.NA

Dinesh Parthasarathy , Wayne Bradford Mitchell , Harald Köstler This is my paper · ORCID
classification cs.CEcs.AIcs.NAmath.NA MSC 65N5565F10
keywords algebraicmultigridflexiblecyclesgrammar-guidedgeneticprogrammingcontext-freegrammarParetooptimizationpreconditioninganisotropicdiffusionevolutionaryalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to show that the hand-designed cycle types of algebraic multigrid, namely V-, W-, and F-cycles, are a narrow slice of a much larger design space, and that searching that space automatically yields faster solvers. It represents each AMG solve as a program generated by a context-free grammar, in which every step can choose its own smoother, relaxation weight, and direction up or down the grid hierarchy. A genetic programming loop optimizes these flexible-cycle programs against two objectives, solve time per iteration and convergence factor, for two cases: a standalone AMG solver for a 3D anisotropic diffusion problem and an AMG preconditioner wrapped in conjugate gradient for a multiphysics simulation. In both cases the optimized flexible cycles are reported to beat the standard cycle types in solve time, and the evolved solvers keep their advantage across problem sizes, right-hand sides, anisotropy values, and later time steps of the simulation.

What carries the argument

The central object is the flexible multigrid cycle, generated by a context-free grammar as a program in which each step is either a smoothing step with a chosen smoother (Gauss-Seidel forward or backward, or Jacobi) and a relaxation weight, or a coarse-grid correction with a chosen scaling factor. Each program expression maps to a single final iteration operator by recursively substituting the two-level update, so executing the program corresponds to an arbitrary up-down traversal of the grid hierarchy rather than a recursive V/W/F pattern. The grammar constrains the genetic programming search to syntactically valid multigrid programs, while the evolutionary loop (NSGA-II, population 256, 100 generations) drives the search toward Pareto-optimal trade-offs between per-iteration cost and convergence.

What would settle it

Re-run the same grammar-guided search with the grammar restricted to standard recursive V-, W-, and F-cycles, using the same population size, generations, and fitness budget; if the best standard-cycle program matches or beats the evolved flexible cycles on the same test problems, the claimed superiority of flexible cycles collapses. As a cheaper check, tune the reference cycles' relaxation weights and smoother counts with the same per-cycle search effort and see whether the gap in Tables 6.1 and 6.2 mostly closes.

Watch

Extended reading notes

Core claim

The central claim is that a flexible multigrid cycle, an arbitrary non-recursive sequence of smoothing and coarse-grid correction steps each with its own smoother and relaxation weight, can be optimized by grammar-guided genetic programming to be more efficient than standard V-, W-, and F-cycles. Expressed as programs generated from a context-free grammar, flexible cycles are evolved for AMG using a population of 256 individuals over 100 generations, with a two-objective fitness measuring solve time per iteration and convergence factor. From the resulting Pareto front the authors select two standalone solvers and one preconditioner, and these outperform the standard-cycle reference methods on nearly every test case, including weak scaling to 2744 processes. Interestingly, the evolved standalone solvers converged to V-cycle-like structures, while the preconditioner case evolved a different structure, and the selected preconditioner retained its performance on time steps other than the one used for optimization.

Load-bearing premise

The load-bearing premise is that the standard-cycle baselines were tuned fairly, so the evolved cycles' better solve times reflect the flexible representation rather than extra search effort.

Editorial extensions

If this is right

  • AMG users can replace hand-picked V-, W-, and F-cycles with evolved flexible cycles tailored to a problem class and obtain lower solve times or iteration counts, as shown in Tables 6.1 and 6.2.
  • The evolved standalone solvers keep their advantage across different right-hand sides, anisotropy values, and grid sizes, and scale weakly to 2744 processes with roughly half the solve time of the best standard-cycle reference.
  • Because the optimization produces a Pareto front rather than a single solver, users can pick between a fast-converging cycle and a cheap-per-iteration cycle depending on the problem budget.
  • A single evolved preconditioner, optimized at one time step of a multiphysics simulation, outperforms standard-cycle preconditioners at later time steps of the same run.
  • Flexible cycles can be expressed as grammar-generated programs and executed in a production AMG implementation, so the search method can attach to existing solver infrastructure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One inference beyond the paper's claims: the reported advantage may come as much from per-step smoother and weight freedom as from the non-recursive cycle shape, since the paper does not run a search confined to standard cycles.
  • A second inference: the same grammar could be broadened to include the AMG setup phase (coarsening, interpolation), which the paper fixes; the authors list this as a future direction.
  • Third, the Pareto front of evolved cycles is a reusable dataset, so a meta-learner could be trained to select a cycle for an unseen problem instance, a use the paper mentions but does not implement.
  • Fourth, for time-dependent simulations, an evolved preconditioner that generalizes across time steps could be re-optimized at intervals rather than at a single early step, potentially tracking matrix drift.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes using grammar-guided genetic programming (G3P) to evolve "flexible" algebraic multigrid (AMG) cycles in which the smoother type, relaxation weight, and scaling factor can differ at each step of the cycle. The flexible cycles are implemented in the hypre library via an extended interface, and the search is carried out with the EvoStencils framework and DEAP. The method is optimized for two use cases: a standalone AMG solver for a 3D anisotropic problem (Section 5.1) and an AMG preconditioner for PCG in a multiphysics code (Section 5.2). The paper reports that the evolved solvers G3P-1 and G3P-2 and the preconditioner G3P-3 outperform standard V-cycles on several test problems, and that the evolved cycles are V-cycle-like in structure (Fig. 6.4).

Significance. If the central claim were fully supported, the paper would make a useful contribution to automated AMG design: it demonstrates a concrete grammar-based search over AMG components embedded in a widely used library, and it tests the evolved methods out-of-sample on different right-hand sides, anisotropy values, problem sizes, and time steps. The implementation in hypre and the use of public frameworks (EvoStencils, DEAP) are positive elements for reproducibility, and the Pareto-front formulation is a reasonable way to maintain diversity during the search. However, the significance is currently limited by two issues: the headline claim is broader than the experimental evidence, and the comparison to standard cycles is confounded by simultaneous variation of cycle shape, smoother choice, and relaxation weights.

major comments (3)
  1. [Abstract; §6.1, Table 6.1] The abstract and Section 7 claim that optimized flexible cycles provide higher efficiency and better performance than standard cycle types, but Table 6.1 on the 400^3 grid shows that G3P-1 is slower than all listed V-cycles for f=1 (30.36 s versus 26.18–27.27 s) and for f=rand (20.91 s versus 15.24–18.28 s). The claim should be restricted to the selected representative solvers and to the conditions where dominance actually holds, or the conclusion should be reworded.
  2. [§5 (Table 5.1a) and §6.1 (Table 6.1, footnote 9)] The comparison is confounded: the flexible programs can choose among Gauss-Seidel forward, Gauss-Seidel backward, and Jacobi smoothers, with relaxation weights and scaling factors taken from the grid (0.1, 0.15, ..., 1.9), while the reference V-cycles are described only by the number of Gauss-Seidel sweeps and no weight optimization is reported. The observed speedups may therefore be due to the extra smoother/weight degrees of freedom rather than to the flexible cycle shape. A controlled ablation is needed, for example evolving flexible cycles with weights fixed to 1.0, or applying the same smoother/weight search to standard V-cycles, to determine whether the cycle-shape flexibility itself is the source of the improvement.
  3. [§6.1, Fig. 6.4 and §7] The paper's own evidence weakens the attribution to flexible cycling: both G3P-1 and G3P-2 converged to V-cycle-like structures (Fig. 6.4), and Section 7 states that it is not fully understood which components (smoothers, relaxation weights, cycle structures) exert the most influence on optimality. Without an attribution analysis or an ablation, the central claim about arbitrary cycle shape is not isolated from the other evolved parameters.
minor comments (6)
  1. [Title page] The title contains spurious spaces: "EVOL VING ALGEBRAIC MUL TIGRID..." should read "EVOLVING ALGEBRAIC MULTIGRID...".
  2. [§5, footnote 8] The random right-hand side f=rand is described as a vector with random coefficients and unit 2-norm, but no random seed or averaging protocol is reported; please state whether the reported times are single runs or averages.
  3. [§1 and §6.1] The introduction refers to "optimized reference methods," but the tuning protocol for the V-cycles is not described beyond footnote 9; a sentence explaining how V(2,1), V(3,2), and V(3,3) were selected would make the comparison easier to assess.
  4. [§6.2, Table 6.2] The text says G3P-3 "outperforms" the standard preconditioners for all time steps except t=2,5,7,8, where V(1,1) is equally effective; since the table shows equal solve times at those steps, the wording "ties" would be clearer than "exceptions."
  5. [Figures 6.1 and 6.3] The right panels in Figures 6.1 and 6.3 use small fonts and overlapping labels; enlarging the legends or restructuring the plots would improve readability.
  6. [Throughout] There are minor typographical errors such as "Eventhough" and "inspite" that should be corrected to "Even though" and "in spite of."

Circularity Check

1 steps flagged · score 2.0 of 10

One in-sample row of Table 6.1 is selected on the same fitness used to evolve G3P-1/G3P-2; the rest of the evaluation is out-of-sample, so the paper is not significantly circular.

  1. fitted input called prediction [Section 6.1, Table 6.1 (original 100^3 row, f=0, a=0.001)]
    "From the pool of Pareto optimal solutions, we select two well-performing solvers: i. G3P-1, a fast-converging solver (Fig. 6.4a), ii. G3P-2, a cost-effective solver (Fig. 6.4b), albeit with slower convergence. ... For the original problem size, the optimized solvers G3P-1 and G3P-2 exhibit the fastest and second-fastest solving times, respectively. They outperform reference methods across all problem variants."

    The standalone-solver optimization in Section 5.1 uses exactly the 100x100x100 problem with a=0.001, b=c=1, f=0, and Section 4 defines the fitness as solve time and convergence factor. G3P-1 and G3P-2 were then chosen from the Pareto front of that same optimization. Consequently, the first column of Table 6.1 (f=0, a=0.001, original grid) is an in-sample fit, not an independent evaluation. Presenting that row as part of the claim that the solvers 'outperform reference methods across all problem variants' folds the selection objective into the evidence. The remaining columns with different f and anisotropy values, the 400^3 case, and the weak-scaling study are genuine out-of-sample checks, so this is a partial, row-level issue rather than a collapse of the whole claim.

full rationale

The paper's central claim is the output of a stochastic search, not a derivation: the flexible AMG programs are evolved by genetic programming against a fitness function (solve time per iteration and convergence factor), and the comparison to V(2,1), V(3,2), V(3,3), etc. is then made on the same solver. The only step that reduces to its own input by construction is the in-sample row of Table 6.1: G3P-1 and G3P-2 were selected using performance on the exact 100^3, a=0.001, f=0 problem that appears as the first evaluation column. This is a fitted-input-reported-as-evidence pattern for that row. It is not load-bearing for the paper's overall generalization claim, because the paper separately shows out-of-sample performance on different anisotropies, different right-hand sides, a 400^3 grid, a weak-scaling study, and later time steps in the multiphysics case. The self-citations to Schmitt et al./EvoStencils are tool and grammar citations, not uniqueness arguments, and they do not by themselves force the observed speedups. The paper also honestly disclaims knowledge of which components (smoothers, weights, cycle structure) drive optimality, which is a validity limitation about attribution but not a circularity. Overall the central derivation is self-contained against external benchmarks, so a score of 2 reflects the single in-sample evaluation row rather than any deeper circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The paper's central claim depends on the evolutionary search being sufficiently thorough and on fair comparison baselines; both are assumptions that the paper supports only partially. No new physical entities or ad hoc mathematical objects are introduced.

free parameters (3)
  • Flexible cycling depth = top 5 levels = 5 levels
    Section 5: 'We enable cycle flexibility for the top five levels and use a V (1, 1) cycle on the coarser levels.' This hand-chosen truncation limits the search space and could exclude beneficial deep flexibility.
  • Relaxation weight grid (0.1 to 1.9, step 0.05) = discrete set
    Table 5.1a: 'Relaxation weights (0.1, 0.15, 0.2, ..., 1.9)'; discretization is a modeling choice that affects which cycles are reachable.
  • Scaling factor grid (0.1 to 1.9, step 0.05) = discrete set
    Table 5.1a lists the same discrete grid for coarse-grid correction scaling factors, restricting the search.
assumptions (4)
  • domain assumption The grammar of Schmitt et al. (2021) generates all relevant flexible multigrid cycles
    Section 3: 'We use this CFG to generate different multigrid cycles for a given AMG setup.' If the grammar excludes beneficial cycle shapes, the search space is incomplete; the paper does not validate this.
  • domain assumption The reference standard cycles are representative optimized baselines
    Section 6.1: 'compared to optimized reference methods with standard AMG cycling'; however, the optimization of reference cycles is not described, and fixed cycle types may not have received equivalent tuning.
  • domain assumption The AMG setup phase (coarsening, interpolation, restriction) is fixed and not part of the optimization
    Section 5: 'During the optimization, the AMG setup phase is fixed.' The evolved cycles' advantage is conditional on this setup; different setups might change the ranking.
  • standard math Each multigrid step can be expressed as a linear correction with a scalar weight
    Section 3: 'Every step during the solve phase of an AMG method can be written in the form v_{i+1} <- v_i + w B(f - A v_i)'; this is standard operator notation for smoothing and coarse-grid corrections.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Evolving Algebraic Multigrid Methods Using Grammar-Guided Genetic Programming." pith.science (2026). https://pith.science/paper/R4JLCBPV

@misc{pith2026241205852,
  author       = {Pith},
  title        = {Pith review of: Evolving Algebraic Multigrid Methods Using Grammar-Guided Genetic Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R4JLCBPV}},
  note         = {Machine review of arXiv:2412.05852}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2412.05852 by the authors.

Figure 1.1
Figure 1.1. Visual representation of the cycling structure in a multigrid method. The [PITH_FULL_IMAGE:figures/full_fig_p002_1_1.png] view at source ↗
Figure 4.1
Figure 4.1. Software setup 4. Implementation. The BoomerAMG1 implementation from the software li￾brary 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 framework2 . The AMG expression generated from the CFG is trans￾formed to corresponding input arguments for BoomerAMG. Executing each program returns the… view at source ↗
Figure 6.1
Figure 6.1. Mean and standard deviation of the minimum objective function values [PITH_FULL_IMAGE:figures/full_fig_p005_6_1.png] view at source ↗
Figures from the paper (3 more)
Figure 6.2
Figure 6.2. Figure 6.2: Weak scaling of a 3D anisotropic poisson problem. [PITH_FULL_IMAGE:figures/full_fig_p007_6_2.png]
Figure 6.3
Figure 6.3. Figure 6.3: Mean and standard deviation of the minimum objective function values [PITH_FULL_IMAGE:figures/full_fig_p007_6_3.png]
Figure 6.4
Figure 6.4. Figure 6.4: The structure of the G3P methods. The color of the node denotes the type [PITH_FULL_IMAGE:figures/full_fig_p008_6_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Towards Automated Algebraic Multigrid Preconditioner Design Using Genetic Programming for Large-Scale Laser Beam Welding Simulations

    cs.CE 2024-12 conditional novelty 4.0 of 10

    Genetic programming designs flexible algebraic multigrid cycles that speed up large-scale laser beam welding simulations by up to 60% over default BoomerAMG and 25% over a hand-tuned configuration.

Reference graph

Works this paper leans on

15 extracted references · 5 canonical work pages · cited by 1 Pith paper

  1. [1]

    A vnat and I

    O. A vnat and I. Yavneh, On the recursive structure of multigrid cycles, SIAM J. Sci. Comput., 45 (2023), pp. S103–S126

    work page 2023

  2. [2]

    Banzhaf, Artificial Intelligence: Genetic Programming , Elsevier, 2001, p

    W. Banzhaf, Artificial Intelligence: Genetic Programming , Elsevier, 2001, p. 789–792, https: //doi.org/10.1016/b0-08-043076-7/00557-x, http://dx.doi.org/10.1016/B0-08-043076-7/ 00557-X

    doi:10.1016/b0-08-043076-7/00557-x 2001

  3. [3]

    De Sterck, R

    H. De Sterck, R. D. F algout, J. W. Nolting, and U. M. Yang, Distance-two interpolation for parallel algebraic multigrid , Numerical Linear Algebra with Applications, 15 (2007), p. 115–139, https://doi.org/10.1002/nla.559, http://dx.doi.org/10.1002/nla.559

    doi:10.1002/nla.559 2007

  4. [4]

    De Sterck, U

    H. De Sterck, U. M. Yang, and J. J. Heys , Reducing complexity in parallel algebraic multigrid preconditioners, SIAM Journal on Matrix Analysis and Applications, 27 (2006), p. 1019–1039, https://doi.org/10.1137/040615729, http://dx.doi.org/10.1137/040615729

    doi:10.1137/040615729 2006

  5. [5]

    Greenfeld, M

    D. Greenfeld, M. Galun, R. Basri, I. Yavneh, and R. Kimmel , Learning to optimize multigrid PDE solvers , in Proceedings of the 36th International Conference on Machine Learning, K. Chaudhuri and R. Salakhutdinov, eds., vol. 97 of Proceedings of Machine Learning Research, PMLR, 09–15 Jun 2019, pp. 2415–2423, https://proceedings.mlr.press/ v97/greenfeld19a.html

    work page 2019

  6. [6]

    Huang, R

    R. Huang, R. Li, and Y. Xi, Learning optimal multigrid smoothers via neural networks, SIAM J. Sci. Comput., 45 (2023), pp. S199–S225

    work page 2023

  7. [7]

    Katrutsa, T

    A. Katrutsa, T. Daulbaev, and I. Oseledets , Deep multigrid: learning prolongation and restriction matrices, 2017, https://arxiv.org/abs/1711.03825

    arXiv 2017

  8. [8]

    Katrutsa, T

    A. Katrutsa, T. Daulbaev, and I. Oseledets , Black-box learning of multigrid parameters , Journal of Computational and Applied Mathematics, 368 (2020), p. 112524, https://doi. org/10.1016/j.cam.2019.112524, http://dx.doi.org/10.1016/j.cam.2019.112524

    arXiv 2020

Show all 15 references
  1. [9]

    I. Luz, M. Galun, H. Maron, R. Basri, and I. Yavneh , Learning algebraic multigrid using graph neural networks , in Proceedings of the 37th International Conference on Machine Learning, ICML’20, JMLR.org, 2020

    2020

  2. [10]

    Manrique, J

    D. Manrique, J. R ´ıos, and A. Rodr ´ıguez-Pat´on, Grammar-Guided Genetic Programming, IGI Global, 2009, p. 767–773, https://doi.org/10.4018/978-1-59904-849-9.ch114, http:// dx.doi.org/10.4018/978-1-59904-849-9.ch114

    2009 doi

  3. [11]

    Orlov, M

    M. Orlov, M. Sipper, and A. Hauptman , Genetic and Evolutionary Algorithms and Pro- gramming: General Introduction and Application to Game Playing , Springer New York, 2009, p. 4133–4145, https://doi.org/10.1007/978-0-387-30440-3 243, http://dx.doi.org/10. 1007/978-0-387-30440-3 243

    2009 doi

  4. [12]

    Schmitt and H

    J. Schmitt and H. K¨ostler, Evolving generalizable multigrid-based helmholtz preconditioners with grammar-guided genetic programming, in Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’22, ACM, July 2022, https://doi.org/10.1145/3512290. 3528688, htt...

    2022

  5. [13]

    Schmitt, S

    J. Schmitt, S. Kuckuk, and H. K¨ostler, Evostencils: a grammar-based genetic programming approach for constructing efficient geometric multigrid methods, Genetic Programming and Evolvable Machines, 22 (2021), p. 511–537, https://doi.org/10.1007/s10710-021-09412-w, http://dx.do...

    2021 doi

  6. [14]

    Taghibakhshi, S

    A. Taghibakhshi, S. P. MacLachlan, L. Olson, and M. West, Optimization-based algebraic multigrid coarsening using reinforcement learning , ArXiv, abs/2106.01854 (2021), https: //api.semanticscholar.org/CorpusID:235313621

    2021 arXiv

  7. [15]

    P. A. Whigham, Grammatically-based genetic programming, 1995, https://api.semanticscholar. org/CorpusID:14127572

    1995

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.