Organizations: Department of Mathematics, Emory University · Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, P.O. Box 808, L-561, Livermore, CA 94551
Algebraic multigrid (AMG) methods are widely used for solving large sparse linear systems, but their efficiency depends strongly on interacting setup and solve parameters. Effective parameter choices typically depend on the problem. We develop a phase-aware online autotuning method for hypre's BoomerAMG to reduce cumulative time-to-solution over sequences of related linear systems. A LinUCB-based contextual bandit selects mixed-type parameters for AMG hierarchy construction using a shared cost model over PDE descriptors and configuration encodings. A recursive LSTDQ controller uses residual and timing observations to estimate the AMG solve time within each attempt and adapt relaxation weights between multigrid cycles. Both learners update from ongoing solves without offline pretraining. Across grids of sizes 403, 603, and 803, the joint autotuning method reduces total runtime, including recurring learner computation, by 36.1-43.3% for diffusion problems and 19.8-31.0% for diffusion-advection problems over sequences of 5000 linear systems, relative to the reference BoomerAMG default configuration. On a variable-flow diffusion-advection benchmark comprising 30,000 systems on a 603 grid, 2 systems fail to converge with joint autotuning, compared with 1677 for the reference configuration, under their respective attempt budgets.
Figures & tables
Parameter
Type
Role
Reference
Setup parameters
strong_threshold
0≤r<1
Strength-of-connection threshold.
0.25
max_row_sum
0<r<1
Row-sum criterion related to diagonal dominance.
0.9
coarsen_type
c
Coarsening algorithm.
10
interp_type
c
Interpolation algorithm.
6
trunc_factor
r≥0
Interpolation truncation factor.
0.0
Table 1: Representative BoomerAMG parameters and reference settings used in this study. Here r , i , and c denote real-valued, integer-valued, and categorical parameters, respectively.
Symbol
Meaning
t,T
Problem index and number of problems in the sequence.
j,Jt,Jmax
Attempt index, number of attempts on problem t , and maximum attempt budget.
k,Kmax
Number of completed cycles within an attempt and the per-attempt cycle limit.
at,j
Setup configuration selected for attempt (t,j) .
wt,j,k
Relaxation weight applied to cycle k+1 of attempt (t,j) .
ϱt,j,k
Relative residual after k completed cycles of attempt (t,j) .
Table 2: Main notation for problem indices, parameter choices, and runtime accounting.
Symbol
Parameter
Values
a1
strong_threshold
0,0.05,…,0.95
a2
max_row_sum
10−6,0.05,0.10,…,0.95
a3
trunc_factor
0,0.05,…,0.95
a4
P_max_elmts
2,4,6,8,12,16
a5
agg_num_levels
0,1,2
a6
coarsen_type
0,2,3,6,8,10
Table 3: Setup search space for a=(a1,…,a8) . Coarsening and interpolation values are algorithmic labels. Aggressive-interpolation truncation and row-limit controls remain fixed at zero.
Figure 1: Online LinUCB–LSTDQ autotuning of BoomerAMG. The contextual bandit selects the AMG setup between solve attempts, while recursive LSTDQ selects the relaxation weight between V-cycles within a fixed hierarchy. Failed learned configurations trigger retries and, after the retry budget is exhausted, a fixed Default fallback. Both learners retain information across the problem sequence and optimize the cumulative recorded runtime.
Online (1–5000)
Frozen (5001–6000)
Method
Setup
Solve
Learner overhead
Total-time reduction
Total-time reduction
Diffusion, 403
The default
57.4
24.9
0.0
—
—
LSTDQ
57.4
17.5
2.0
6.5±0.5 %
8.1±0.7 %
LinUCB
21.9
40.7
3.1
20.2±0.7 %
28.4±1.3 %
LinUCB–LSTDQ
20.7
25.6
6.2
36.1±1.0 %
47.0±1.7 %
Table 4: Online runtime decomposition and total-time reductions during the online (problems 1–5000) and frozen (problems 5001–6000) phases. Setup and solve execution include all attempts, and learner overhead includes recurring setup- and solve-learner computation. Time columns are in ms per problem and average the six seed-level means. Both reduction columns report the mean ± sample standard deviation of paired total-time reductions relative to the default, including learner overhead; positive values favor the learned method.
Figure 2: Runtime decomposition on 603 diffusion across six seeds. Paired stacks show setup execution, setup-learner overhead, solve execution, and solve-learner overhead. Labels report total runtime as mean ± sample standard deviation of seed-level means (ms/problem), for the online phase (problems 1–5000) and the frozen phase (problems 5001–6000).
Figure 3: Online runtime and break-even behavior. (a) Joint-method break-even problem indices across six seeds per case. The break-even problem index is the first index from which the joint method’s cumulative total runtime remains below the default’s through problem 5000. Open points show individual seeds; whiskers and labels give the minimum–maximum range. The red point identifies the run illustrated in (b,c). (b,c) Illustrative 603 diffusion run, seed 3: cumulative total runtime and percentage reduction relative to the default, over problems 1–5000 in (b) and 1–2500 in (c). All executed attempts and recurring learner computation are included. Curves are unsmoothed prefix sums; the inset enlarges problems 1–1000. The black vertical guide in (c) marks the break-even problem index, 357. Legend values give online-phase runtime in seconds.
Figure 4: First-attempt setup choices and relaxation weights selected by LinUCB–LSTDQ in the illustrative 603 diffusion run, seed 3. Columns correspond to problems 1–2500. (a) Setup parameters a1,…,a8 , defined in Table 3 . (b) Rows correspond to zero-based cycle indices, increasing downward. White cells indicate that the first attempt has terminated. Cycles from retries and the default fallback are omitted.
Symbol
Parameter
Default
LinUCB–LSTDQ
Reduction
a1
strong_threshold
0.25
0.95
a2
max_row_sum
0.90
0.95
a4
P_max_elmts
4
2
a7
interp_type
Extended+i (6)
Standard (8)
Setup execution (ms)
308.84
58.54
81.0%
Grid complexity
1.676759
1.971565
−17.6 %
Table 5: Setup configuration, hierarchy statistics, and runtime for the 603 diffusion problem 2275, seed 3. Only setup parameters that differ from the default are shown. Both methods converge on their first attempt. Total time includes learner overhead; the per-problem total-time reduction is 72.7%. This selected best case is illustrative rather than an average performance result. Grid complexity is the ratio of total unknowns across levels to fine-grid unknowns. Operator and memory complexities are the ratios of total operator nonzeros and total operator-plus-interpolation nonzeros, respectively, to fine-grid operator nonzeros.
Figure 5: Adaptive relaxation on 803 diffusion, seed 5, for consecutive problems A, B, and C (1563, 1564, and 1565). (a) Recorded LinUCB–LSTDQ weights; crosses mark random exploratory actions, and the horizontal black line marks w=1 . (b–d) Residual histories for problems A–C, respectively, comparing LinUCB–LSTDQ (colored) with the paired default (black). The three residual panels share axis scales. Dotted lines mark the convergence tolerance. Legend percentages give total-time reductions relative to the default on the same problem, including learner overhead. All three joint-method solves succeed on their first attempt and are shown through convergence.
Method
Failures after attempt
Total-time reduction
j=1
j=2
j=3
j=4
Default ( Jmax=1 )
1677
—
—
—
—
LSTDQ ( Jmax=2 )
777
26
—
—
9.8±5.6%
LinUCB ( Jmax=4 )
810
62
44
28
50.8±2.9%
LinUCB–LSTDQ ( Jmax=4 )
1152
138
69
2
54.1±2.1%
Table 6: Variable-flow diffusion–advection on the 603 grid, over 30,000 problems across six seeds. Failure columns give the numbers of problems remaining unsolved after each attempt; italicized counts mark final failures. The last permitted attempt uses the default recovery for LSTDQ, LinUCB, and LinUCB–LSTDQ. The final column gives total-time reductions relative to the paired default as mean ± sample standard deviation across six seeds, including all executed attempts and recurring learner overhead.
Figure 6: First-attempt native solve-time reduction relative to fixed w=1 on matched joint-selected hierarchies. (a) 603 diffusion. (b) 603 variable-flow diffusion–advection. Open points show results from the six final learner states; diamonds and whiskers give their mean and sample standard deviation. Each value is computed from summed costs on 100 problems. Both panels use the same horizontal scale; all first-attempt times are included regardless of convergence.
Diffusion
Variable flow
Policy/reference
Time reduction
Failure rate
Time reduction
Failure rate
Fixed w=1
39.6±1.5 %
0.5 %
23.6±5.8 %
5.2 %
Global best fixed
8.5±2.1 %
0.2 %
0.4±6.1 %
1.0 %
Per-problem best fixed
5.9±2.0 %
0.0 %
−10.6±7.0 %
0.2 %
Periodic (2.85,1.10)
−2.8±3.8 %
0.3 %
25.8±6.0 %
43.0 %
Frozen LSTDQ
—
0.2 %
—
0.3 %
Table 7: Frozen-LSTDQ first-attempt native solve-time reduction relative to matched-hierarchy references (%). Reductions are mean ± sample standard deviation across the six final learner states for each 603 problem family. Positive values favor LSTDQ. Failure rates are computed over 600 first attempts per policy and family.
Figure 7: Recorded weights for fixed w=1 , the per-problem best fixed weight, period-two (2.85,1.10) , and frozen LSTDQ on identical joint-selected hierarchies. The illustration uses seed 1. All panels contain the same 100 problems, ordered by decreasing first-attempt cycle count for w=1 , with case ID breaking ties. Cycle zero is at the top; white cells follow primary-attempt termination. Recovery cycles are omitted.
Hyperparameter optimization selects model and training settings to improve predictive performance, efficiency, or reliability under limited evaluation budgets.
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.
Dinesh Parthasarathy, Wayne Mitchell, Arjun Gambhir +2
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
The scalable solution of large sparse linear systems is a bottleneck in scientific computing and graph analysis. While algebraic multigrid (AMG) offers optimal linear scaling, its performance is severely constrained by the trade-off between the sparsity and convergence quality of coarse-grid operators. Classical AMG heuristics struggle to balance these objectives, often sacrificing stability or performance for sparsity. We propose RAPNet, a graph neural network (GNN) framework that resolves this trade-off by learning to generate sparse, robust coarse operators directly from the sparse algebraic system. Key to our approach is a level-wise training strategy that enables learning from small subgraphs and generalization to million-node domains, bypassing the bottlenecks of prior neural AMG attempts. RAPNet executes exclusively during the solver setup phase, ensuring that the solve phase retains its favorable computational properties. We show that our method outperforms classical non-Galerkin baselines on diverse PDE discretizations and graph Laplacians, making it particularly effective for multi-query tasks such as eigenproblems, time-dependent simulations, and inverse or design problems.
Yali Fink, Ido Ben-Yair, Lars Ruthotto +1
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.
We propose a reinforcement learning (RL) framework for \xy{responsive} precision tuning for linear solvers, which can be extended to general algorithms. The framework is formulated as a contextual bandit problem and solved using incremental action-value estimation with a discretized state space to select optimal precision configurations for computational steps, \xy{retaining} precision and computational efficiency. To verify its effectiveness, we apply the framework to iterative refinement for solving linear systems Ax=b. In this application, our approach dynamically chooses precisions based on calculated features from the system while maintaining acceptable accuracy and convergence. In detail, an action-value estimator takes discretized features (e.g., approximate condition number and matrix norm) as input and outputs estimated action values, from which a policy selects the actions (chosen precision configurations for specific steps), optimized via an ε-greedy strategy to maximize a multi-objective reward to balance accuracy and computational cost. Empirical results demonstrate effective precision selection, \xy{increasing the use of lower-precision arithmetic} while maintaining accuracy comparable to double-precision baselines. \xy{We further evaluate the learned policies in a compiled CPU GMRES-IR implementation using FP16, FP32, and FP64 arithmetic for solver-level native validation.} The framework generalizes to diverse out-of-sample data and provides insights into applying RL precision selection to other numerical algorithms, advancing mixed-precision numerical methods in scientific computing. To the best of our knowledge, this is the first work on precision autotuning with RL with verification on unseen datasets.
Erin Carson, Xinye Chen
Charles University Prague, Czech · Sorbonne Université, CNRS, LIP6 Paris, France