Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Semi-coarsening — where it appears

Coarsening a grid in one direction only. It is what repairs a multigrid hierarchy on an anisotropic operator, and it requires knowing which direction the coupling is strong in before the hierarchy is built.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

point · strong in y0.951point · strong in x0.956y-line · strong in y0.037y-line · strong in x0.967semi-y · strong in y0.107semi-y · strong in x0.9661.00 — no convergenceone problem, seen from two sidesy-line, aimed0.037y-line, turned sideways0.97the ratio2631×31 grid, twelve V-cyclesthe direction is in the code, not in the problem

Coarsening in one direction only

Leave the smoother alone and halve only the strong direction, and the smoothing factor is 0.3340 — identical to line relaxation's, at every anisotropy and every weight, to twelve digits. The convergence factors are then a factor of three apart, and at 45° both repairs fail outright.

iterative · Anisotropy the grid the operator came froman edge is a coupling the matrix calls strongkeptinterpolatedwhat the entries decidedcoupling ratio, x against y0.001strong couplings across x0strong couplings along y110rows kept or dropped whole1111×11 grid, θ = 0.25the coarse grid, from the matrix alone

The coarse grid the matrix chooses

Given a tridiagonal matrix and no information about a grid, the coarsening keeps every other point and derives the weights ½, 1, ½ — the operators the geometric method was handed. Given the anisotropic operator, it discovers semi-coarsening, in the right direction, without a coordinate.

iterative · Algebraic multigrid -213284300.250.50.751rotation of the anisotropy (degrees)factor / couplingusableconvergence factoraxis couplingdiagonal couplingthe standard answer, and the anglefactor at 0°0.19factor at 45°0.8axis ÷ diagonal coupling at 45°2the hierarchy reads the matrixand the matrix lost the direction

How much direction there was to lose

At 45° the nine-point stencil hands smoothed aggregation the same wrong hierarchy at every anisotropy — six strong neighbours per interior point, 121 aggregates, the identical partition from ε = 10⁻⁴ to 0.099. The convergence factor that one hierarchy produces runs from 0.802 to 0.581 over the same range.

iterative · Anisotropy 10⁻¹100.20.40.60.8strength threshold θresidual reduction per cycleθ = εsemi-coarseningkept whole rowsfull coarseningone parameter, two methodsbest factor above ε0.053best factor below ε0.1the ratio across the switch231×31 anisotropic operatora switch, not a dial

The switch does not know which side is better

The strength threshold moves the coarsening from full to semi at θ = ε exactly, at every anisotropy. Which of the two converges faster is a separate question with a separate answer, and it changes sign between ε = 0.33 and ε = 0.34 — where nothing whatever happens to the switch.

iterative · Algebraic multigrid

Named alongside it

The objects these essays reach for when they reach for this one.

AnisotropyStrength of connectionAlgebraic multigridCoarse fine splittingConvergence rateGalerkin coarse operatorM-matrixOperator complexityProlongationRotated anisotropyDiscretisationGrid alignment

All concepts