Locally Weighted Coarse-Grid Correction for Nonsymmetric Algebraic Multigrid

Algebraic multigrid (AMG) solves the huge sparse linear systems that come from discretized physics by alternating two steps. A cheap local smoothing pass removes jagged error. A coarse-grid correction then solves a much smaller version of the problem to remove smooth error. For symmetric problems such as diffusion, the coarse correction provably never makes the error worse. For nonsymmetric problems such as advection-dominated flow, it can. The correction becomes an oblique projection, which can amplify some error components, and smoothing may not be able to undo the damage. The usual remedies either redesign the transfer operators between grids at setup time, or wrap the whole cycle in an outer Krylov solver like GMRES and let it absorb the damage.

We propose a third option that works inside the cycle and costs about one extra sparse matrix-vector product per level. Split the coarse correction into a few spatial pieces. Rescale each piece by a weight chosen on the fly to minimize the residual. Then add the pieces back. The amplification in nonsymmetric problems is concentrated in particular modes and regions, for example near recirculation or along misaligned characteristics. A single global damping factor must therefore sacrifice good corrections everywhere to suppress bad ones somewhere. Spatially resolved weights need not. By construction the weighted correction is never worse in residual norm than either doing nothing or applying the standard correction. That turns a detrimental step into a guaranteed non-increasing one.

Core Claim

Write the coarse correction at one level as $v = P e_c$, where $P$ is interpolation and $e_c$ the coarse-grid solution. Let $r$ be the current residual, and partition the fine degrees of freedom into $G$ groups $S_1,\dots,S_G$, taken from a graph partition of the coarse-point neighborhoods. Let $v_g$ be $v$ restricted to $S_g$. The update is $x \leftarrow x + \sum_g w_g v_g$, with weights

$$ w^\star = \arg\min_{w \in \mathbb{R}^G} \Big\| r - \sum_{g=1}^{G} w_g A v_g \Big\|_2 . $$

The supports are disjoint, so all products $A v_g$ together cost one pass over $A$. Solving for $w^\star$ is then a $G \times G$ least-squares problem, with $G$ between 4 and 64.

The residual 2-norm equals the error in the $A^*A$ norm. Both $w=0$ and $w=\mathbf{1}$ are feasible choices, so the coarse stage can never increase that error and never does worse than the unweighted correction. This is the normal-equations norm in which Manteuffel and Southworth built nonsymmetric two-grid theory. The guarantee holds even when the transfer operators fail the approximation properties that theory requires.

The substantive claim goes further than this safety guarantee. When coarse-grid amplification is spatially localized, a modest number of groups should recover most of the convergence lost to it. A single scalar weight ($G=1$) should not. The method should also reduce how much work an outer Krylov solver has to do on top of the best current transfer operators.

Relation to Prior Work

The motivation comes from the analysis of non-orthogonal coarse correction. Southworth and Manteuffel characterize when $\Pi = P(R^*AP)^{-1}R^*A$ is orthogonal in a chosen inner product. Related analyses (Manteuffel et al.; Southworth et al.) explain why the correction amplifies error once orthogonality is lost. Empirical reports of plateaus and divergence (Kramer et al.; Tareq-Uz-Zaman et al.) show the problem is practical. All of this work treats the fix as a setup-time property of $R$ and $P$. We instead correct the step at solve time, given whatever $R$ and $P$ exist.

Our method sits on top of the setup-time constructions, not against them:

  • ℓAIR approximates ideal restriction locally and excels in advection.
  • ClAIR adds mode constraints to handle diffusion. It still reports large approximation constants in diffusion-heavy regimes and relies on an outer Krylov method.
  • Generalized AMGr uses sparse approximate inverses and coarse-point relaxation for anisotropy, with static thresholds.

Each leaves fixed operators and some residual detriment. Our weighting targets exactly that residual detriment.

The closest relative in spirit is De Sterck et al.. They remove coarse-grid amplification in parallel-in-time advection by fitting coarse operators with offline least squares on structured stencils. Our least-squares problem is solved online, per cycle and per level, on unstructured spatial operators. It fits step weights rather than operator entries.

From the convergence-acceleration literature we borrow one lesson, not machinery. Variable-density AMP showed that treating error that varies across scales as uniform stalls an iteration, while tracking it per subband speeds convergence by more than 5x. Self-updating damping in MIDE and the energy-stabilized steps of AEPG show that adaptive step control beats fixed damping. Both, however, use a scalar. Our groups play the role of VDAMP's subbands, but defined in space and fitted by exact residual minimization rather than by heuristic or variance estimates.

Research Program

The first deliverable is the weighted cycle itself, implemented in an existing AMG code with ℓAIR, ClAIR and generalized-AMGr hierarchies. Weighting is applied at every level of a V-cycle. The weights change from cycle to cycle, so the cycle is a nonlinear preconditioner and must be wrapped in flexible GMRES rather than GMRES. We will measure what this costs.

Groups are built once at setup. The default partitions the graph of coarse-point neighborhoods into $G$ contiguous pieces. A variant orients pieces along the dominant flow direction, which a strength-of-connection graph exposes.

The second deliverable is a diagnostic study. For each problem and hierarchy we record two quantities in the unweighted cycle: the per-cycle, per-level residual ratio across the coarse stage, and its spatial distribution. This tells us whether amplification exists in practice for modern hierarchies and whether it is localized. If amplification is spatially uniform, the scalar $G=1$ version should match the grouped one and the idea reduces to known scalar damping.

The third deliverable is analysis on model problems. For constant-coefficient advection-diffusion with periodic boundaries, we compute the two-grid error propagation operator's convergence factor as a function of $G$, using the weights the minimization selects on the slowest modes. The goal is to explain how many groups are needed relative to the length scale of amplification.

We will also test whether the weights carry information that could inform truncation decisions in ℓAIR. That would address the open problem of heuristic truncation without error bounds.

Baselines

The naive reference is the unweighted cycle with each hierarchy (ℓAIR, ClAIR, generalized AMGr), used as a stationary iteration and as an FGMRES preconditioner.

The strongest existing competitor depends on the regime:

  • Advection-dominated: ℓAIR/AIR preconditioning GMRES. Sivas et al. report "iteration counts remained nearly constant" up to millions of unknowns at $\nu = 10^{-6}$ on space-time HDG.
  • Mixed and diffusion-dominated: ClAIR with an outer Krylov method, which was designed for the full parameter range. Its reported figures are operator complexity of 1.34–1.51 versus 2.20–2.87 for ℓAIR on Poisson. No reported result was found on Lacuna for ClAIR convergence factors in the mixed advection-diffusion regime, so we will generate those numbers ourselves.
  • Anisotropic diffusion: generalized AMGr. Zaman et al. report a two-grid convergence factor of 0.116 at angle $\pi/4$ (down from about 0.96 for classical AMGr), and 0.04–0.07 on isotropic Poisson.

All methods share the same hierarchy, the same smoother and sweep counts, and the same stopping tolerance. Each Krylov method gets an equal tuning sweep over restart length. Cost is counted in work units per digit of residual reduction, with the extra matrix-vector product and $G\times G$ solves charged to our method.

The key ablation sequence isolates spatial resolution as the ingredient:

  1. Fixed $\omega$ tuned per problem by grid search.
  2. Scalar minimal-residual weight ($G=1$).
  3. Grouped weights at increasing $G$.

Beating a baseline means at least one of two outcomes at matched hierarchy. The first is fewer work units per digit than the best-tuned outer Krylov method on problems where the diagnostic shows coarse-stage amplification. The second is equal work at a much smaller restart length, and therefore smaller memory. On problems such as anisotropic diffusion, where amplification may be absent, matching the 0.116 factor at negligible overhead counts as no harm, not as a win.

Why not just…?

Why not just wrap the cycle in GMRES? This is the real threat. Outer GMRES chooses one global combination of past preconditioned residuals per outer iteration. It cannot assign different weights to different regions on coarse levels within a cycle. It also pays orthogonalization and storage that grow with restart length, a burden Ali et al. acknowledge when their constants grow large. Still, a long-restart GMRES may fully absorb localized amplification. We will settle this by sweeping restart lengths 5, 10, 30 and unrestarted, comparing work and memory against FGMRES with the weighted cycle. If unrestarted GMRES on the unweighted cycle wins on work at every scale, we will report that our contribution is limited to the memory-constrained regime.

Why not just use a fixed or scalar adaptive damping factor? Zhao et al. show fixed damping is fragile and needs tuning, which argues for adaptivity. It does not show that spatial resolution is needed. The $G=1$ minimal-residual weight is exactly the scalar adaptive alternative and is our central ablation. If $G=1$ matches larger $G$ on recirculating flow, we abandon the grouped version.

Why not just build better transfer operators? ClAIR and generalized AMGr are the right first line of defense, and we run on top of them rather than replacing them. Their own reports of large approximation constants and static thresholds suggest some detriment survives. The diagnostic study measures how much does survive. If it is negligible for ClAIR across the Péclet range, the method has value only for cheaper hierarchies, and we will say so.

Why not just solve the normal equations with symmetric AMG? Doing so squares the condition number and densifies the operator (Constantine et al.; Manteuffel et al.). We use $A^*A$ only as the norm being minimized, never as an assembled matrix.

Proposed Experiments

We test on five problem families drawn from the cited benchmarks:

  • 2D recirculating flow with upwind discontinuous Galerkin, as used for ℓAIR, with closed streamlines.
  • Steady advection-diffusion sweeping the Péclet number from diffusion- to advection-dominated, the ClAIR setting.
  • Rotated anisotropic diffusion across angles, including $\pi/4$, and the four-quadrant reaction problem, from generalized AMGr. Prior two-level factors there are below 0.6 and three-level factors below 0.8.
  • Isotropic Poisson on unstructured triangulations, as a no-harm check.
  • Space-time HDG advection-diffusion at $\nu = 10^{-6}$, following Sivas et al.

Metrics are:

  • asymptotic convergence factor;
  • work units per digit including operator complexity and weighting overhead;
  • outer iterations and peak Krylov memory;
  • iteration growth under refinement;
  • the measured coarse-stage residual ratio.

Three checks decide the outcome. The first asks whether the unweighted coarse stage actually amplifies residuals on recirculating and mixed-regime problems with ClAIR and ℓAIR, and whether that amplification is spatially concentrated. If not, the premise fails. The second asks whether grouped weights with $G$ around 16–64 beat $G=1$ and tuned fixed $\omega$ on those problems. If not, scalar damping suffices. The third asks whether the weighted cycle under small-restart FGMRES matches or beats the best-restart GMRES on the unweighted cycle in work per digit, while keeping iteration counts flat under refinement. Only a yes on all three supports the claim. Problems with no amplification, such as Poisson and anisotropic diffusion, should show no degradation from the 0.04–0.07 and 0.116 factors reported for generalized AMGr.