Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Diagonal dominance — where it appears

The property of a matrix whose every diagonal entry is at least the sum of the magnitudes of the other entries in its row. It is strict where that inequality is strict, and strict dominance is what makes an inverse fall away with distance in the matrix's graph rather than staying flat.

Named by 3 essays across 3 fields — each of them below, with the objects they name alongside it.

02468101210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹singular value, in orderσ ⁄ σ₁eight digitsrenumberedin the separator's orderthe same cliff, from the other endσ₂ ⁄ σ₁0.062σ₄ ⁄ σ₁1.3·10⁻⁴σ₆ ⁄ σ₁1.5·10⁻⁸renumbered σ₄ ⁄ σ₁0.63rank at 10⁻⁸6the same entriesin two orders

The cliff behind the count

The fill's rank is an integer between three and six across every separator two dense half-eliminations can afford, and this field has already recorded that a handful of such integers cannot carry a law. The singular values underneath are real numbers. They say the cliff's first step is 23.0 at a separator of eleven, 19.1 at fifteen and 16.2 at twenty-three — and that a control with no differential operator behind it gives 14,672.

sparsity · Fill 10⁻⁴10⁻³10⁻²10⁻¹100.250.50.751anisotropy εsmoothing factor μpoint + fully-line + fullpoint + semi-y⅓, the one-dimensional answertwo routes, three curvesgap between the repairs2.2·10⁻¹⁶scan against closed form2.2·10⁻¹⁶the dashed curve lies on the solid one beneath itone repair, written two ways

Smoothing a whole line at once

Solve every grid line in the strong direction exactly rather than sweeping over it, and the smoothing factor goes from 0.9993 back to 0.3340 — which is the one-dimensional answer, on a problem that is not one-dimensional. The repair replaces one ε in the closed form by a one.

iterative · Anisotropy 110¹10²10³10⁴10⁵10⁶10¹10²10³10⁴10⁵spread of resistances, largest ÷ smallest possiblecondition number, unit diagonalleast-resistance treebreadth-first treegreatest-resistance treenode equationsspread resistances make the loops easyand the nodes hard

Spread resistances make the loops easy

Scaled to a unit diagonal, the loop equations on the least-resistance tree get easier as a network's resistances spread — from 120 to 5.44 over six decades — and stop depending on the grid's size, while the node equations of the same flow get harder, from 538 to 4.6·10⁴. The spread that ruins the range-space formulation rescues the null-space one, though the loops' density means the work saved is a factor of two, not the factor of nine the iteration counts suggest.

orthogonality · Null space basis

Named alongside it

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

AnisotropyBlock jacobiCondition numberConjugate gradientsFourier modesGraph laplacianGreens functionGroundingKernel matrixLine relaxationLow-rank approximationNested dissection

All concepts