Online Autotuning of Algebraic Multigrid via Contextual Bandits and Reinforcement Learning
Organizations: Department of Mathematics, Emory University · Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, P.O. Box 808, L-561, Livermore, CA 94551
Abstract
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 , , and , 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 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 | Strength-of-connection threshold. | ||
| max_row_sum | Row-sum criterion related to diagonal dominance. | ||
| coarsen_type | Coarsening algorithm. | ||
| interp_type | Interpolation algorithm. | ||
| trunc_factor | Interpolation truncation factor. | ||
| Symbol | Meaning |
|---|---|
| Problem index and number of problems in the sequence. | |
| Attempt index, number of attempts on problem , and maximum attempt budget. | |
| Number of completed cycles within an attempt and the per-attempt cycle limit. | |
| Setup configuration selected for attempt . | |
| Relaxation weight applied to cycle of attempt . | |
| Relative residual after completed cycles of attempt . |
| Symbol | Parameter | Values |
|---|---|---|
| strong_threshold | ||
| max_row_sum | ||
| trunc_factor | ||
| P_max_elmts | ||
| agg_num_levels | ||
| coarsen_type |
| Online (1–5000) | Frozen (5001–6000) | ||||
| Method | Setup | Solve | Learner overhead | Total-time reduction | Total-time reduction |
| Diffusion, | |||||
| The default | 57.4 | 24.9 | 0.0 | — | — |
| LSTDQ | 57.4 | 17.5 | 2.0 | % | % |
| LinUCB | 21.9 | 40.7 | 3.1 | % | % |
| LinUCB–LSTDQ | 20.7 | 25.6 | 6.2 | % | % |
| Symbol | Parameter | Default | LinUCB–LSTDQ | Reduction |
|---|---|---|---|---|
| strong_threshold | 0.25 | 0.95 | ||
| max_row_sum | 0.90 | 0.95 | ||
| P_max_elmts | 4 | 2 | ||
| interp_type | Extended+i (6) | Standard (8) | ||
| Setup execution (ms) | 308.84 | 58.54 | 81.0% | |
| Grid complexity | 1.676759 | 1.971565 | % | |
| Method | Failures after attempt | Total-time reduction | |||
|---|---|---|---|---|---|
| Default ( ) | 1677 | — | — | — | — |
| LSTDQ ( ) | 777 | 26 | — | — | |
| LinUCB ( ) | 810 | 62 | 44 | 28 | |
| LinUCB–LSTDQ ( ) | 1152 | 138 | 69 | 2 | |
| Diffusion | Variable flow | |||
|---|---|---|---|---|
| Policy/reference | Time reduction | Failure rate | Time reduction | Failure rate |
| Fixed | % | % | % | % |
| Global best fixed | % | % | % | % |
| Per-problem best fixed | % | % | % | % |
| Periodic | % | % | % | % |
| Frozen LSTDQ | — | % | — | % |
Hyperparameter Optimization
Hyperparameter optimization selects model and training settings to improve predictive performance, efficiency, or reliability under limited evaluation budgets.
See all 178 papers