Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Augmented lagrangian — where it appears

A saddle-point system with a multiple of the constraint term added to its leading block, which leaves the solution unchanged because the constraints hold there. Its weight, usually written gamma, trades how well the preconditioned system clusters against how badly the leading block is conditioned.

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

-1-0.500.511.520eigenvalue of P⁻¹K1 − φ1φS never formedγ1smallest ν0.056furthest from φ, 1 − φ0.57MINRES steps11an exact Schur approximation, bought by changing Hthe golden ratio without S

Where the augmentation puts the cost

Add γAᵀA to the objective block of a saddle-point system and its Schur complement tends to I/γ, so the cheapest possible approximation becomes the right one and the golden-ratio spectrum arrives — within 7.6·10⁻⁶ at γ = 10⁶. MINRES falls from 21 steps to 6. The inner solve with the augmented block rises from 14 conjugate gradient steps to 43, their product does not fall at all, and the answer loses seven and a half digits on the way.

constraint · Block preconditioning norms all onesmallest least-work γ0.032largest3.2·10⁵10⁻²10⁻¹110¹10²10³10⁴10⁵10⁶the constraint's condition numberleast-work γ10100100010⁴Hessian κ 10Hessian κ 100Hessian κ 10⁴two seeds at every pair of condition numbersseven decades, and no norm to read them from

An augmentation read in the smallest eigenvalue

An augmented Lagrangian preconditioner's least work sat at γ = 1, 10⁴ and 1 on three systems, and two of the three optima sat where the smallest generalised eigenvalue was about 0.06 — which suggested a rule written in ν rather than γ. On twenty-four systems whose norms are all one, the least-work γ spans seven decades and ν at the optimum spans a factor of thirty, so there is no one ν. There is still a rule: take the smallest γ at which ν reaches 0.03, and the median system pays 7 per cent over its least work and the worst 29, where the best single γ pays 61. Its price is digits — twelve times the best forward error on the median system, 4,561 times on the worst.

constraint · Block preconditioning

Named alongside it

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

Block preconditionerConjugate gradientsExact ground truthForward errorMINRESSaddle-point systemsSchur complementCondition numberGeneralised eigenvalue problemPreconditioning

All concepts