Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Active set — where it appears

The constraints that hold with equality at the solution of an inequality-constrained problem. Which they are is the combinatorial part of the problem, and an interior-point method finds out by driving a diagonal apart until the two groups are sixteen orders of magnitude away from each other.

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

Also named here as barrier parameter — the same set of essays touches all of them, so they are one junction rather than several.

-14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴3·10¹⁵its relative error10⁻¹⁵κ₂ condensed2.4·10¹⁶its relative error0.31the same step, written two waysand only one of them is solvable

A condition number sent to infinity

An interior-point method manufactures an ill-conditioned matrix on every iteration, deliberately, because the separating of a diagonal is how it discovers which constraints are active. Written one way the answer keeps fifteen digits at a condition number of 3·10¹⁵. Written the other way — the way almost every code writes it — it has none left.

constraint · interior point conditioning -1-0.75-0.5-0.25010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴log₁₀ σ — the barrier's reduction factorresidual after one reused stepconvergedthe pattern free, the factors notentries moved6off-diagonal0survived at σ = 0.996survived at σ = 0.106 steps0 stepsthe few entries that movedare the ones that dominate

What survives one step of the barrier

An interior-point method solves the same system dozens of times with the same pattern and different numbers, and exactly p entries change between one step and the next. The pattern is reusable for ever. The factorisation is reusable for none of them, and the threshold that says so is a reduction factor of about a per cent against schedules that use ten.

sequence · reuse

Named alongside it

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

Barrier parameterCondition numberInterior point methodSaddle-point systemsBackward errorComponentwise condition numberExact ground truthForward errorIterative refinementNormal equationsPreconditioningSequence of solves

All concepts