Numerical Linear Algebra
where the algebra stops being the arithmetic
The collection

Every essay — page 25

Essays 577 to 586 of 586, in the same order.

The matrix a constraint makes

Every difficult matrix in the other fields was difficult for a reason the arithmetic supplied: a Hilbert matrix arrives ill conditioned, a Wilkinson matrix grows under elimination, a kernel matrix is dense. Ask a problem to minimise something subject to a constraint and the matrix that results is difficult for a reason the algebra supplies. Its zero block is the second derivative of a Lagrangian with respect to its own multipliers, so no pivot order removes it and no precision changes that; its inertia is known before anything runs; and Cholesky does not fail somewhere on it, it fails at the first constraint row, on a number the problem already contained. Then the field's second surprise, which is the opposite one: an interior-point method drives the condition number of this matrix to 10¹⁵ deliberately, and the answer keeps fifteen digits — because the number that describes the error is not the one every library prints.

10⁻¹⁷10⁻¹⁶10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶|h|, the curvature of H along the weak directionσ at which the count is first wrong10⁻⁴10⁻³10⁻²10⁻¹110¹10²no interchangesLDLᵀ of Krank tolerancethrough Z: right to 10⁻¹⁶10 × 4, eight draws per curvatureh = -1·10⁻⁴: LDLᵀ first wrong at σ1.8·10⁻¹¹h = -0.01: LDLᵀ first wrong at σ1.8·10⁻¹⁰h = -1: LDLᵀ first wrong at σ1.4·10⁻⁹h = -100: LDLᵀ first wrong at σ1.8·10⁻⁸the pair's small eigenvalue is σ²/|h|the count loses it long before the rank does

A constraint the count stops seeing

Let one constraint drift towards being a combination of the others and the inertia of the saddle-point matrix keeps its promise only while σ²/|h| can be resolved — σ the constraint's smallest singular value, h the curvature along the direction it barely constrains.

7 figures · Saddle-point systems, essay 5 κ(A) = 10⁸, 152 saddlespassed, ordinary63passed, on wrong counts57passed, always510⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹10⁻⁴10⁻²110²10⁴10⁶10⁸curvature needed, μshift applied ÷ μordinary schedulenull space on wrong countsnull space alwaysbelow the dashed line a saddle was certifiedthe arbitrated shift sits at twice the need

A loop that asks the null space why

An inertia-correction loop sees only an integer, and two different faults produce the same wrong one: curvature that needs a shift, and a constraint too weak for the count to see.

5 figures · Saddle-point systems, essay 6 μ = −0.01, δ = 7saddle's growth a step0.0014minimum's fall a step0.014residual verdict, step6205010015020010⁻¹10¹refinement steprelative residual, relative errorsaddle, residualsaddle, errorminimum, residualminimum, errorthe pivot signs call both of these a minimumthe residual does not

The residual turns before the error doubles

Regularise a saddle-point matrix past the Hessian's most negative eigenvalue and its pivot signs certify every shallow saddle as a minimum; refinement against the unregularised matrix keeps the test, as a rate, and a saddle at a hundredth of the regularisation grows by only 1.0014 a step — 485 steps to double.

6 figures · Quasi-definite, essay 4 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 γ.

5 figures · Block preconditioning, essay 5 rounding finds every hidden saddleμ = −0.01: share zero, verdict at step2723μ = −0.1: share zero, verdict at step1102μ = −1: share zero, verdict at step18110¹10²10³decades of the growing direction removed from the right-hand sidestep the verdict settles0246810121416allμ = −0.01μ = −0.1μ = −1dashed: the growth against the slowest contractiona decade of hiding is a fixed number of steps

The right-hand side that hides the saddle

Refinement against an unregularised saddle-point matrix gives the second-order verdict the pivot signs cannot, from step 62 on the shallowest saddle — for one right-hand side.

5 figures · Quasi-definite, essay 5 μ = −0.1 and −0.01both hidden: steps a decade81the faster direction's race81the slower direction's race14710¹10²10³decades of the hidden directions removedstep the verdict settles0246810121416allboth directions hiddenonly the faster hiddenonly the slower hiddenμ = −0.1 aloneμ = −0.01 alonedashed: a single saddle of each curvatureone hyperplane hides nothing

One hyperplane hides nothing

Iterative refinement against a saddle-point matrix gives its verdict when the growing direction overtakes the minimum's slowest decay, and a right-hand side with that direction removed delays it by a fixed number of steps a decade.

5 figures · Quasi-definite, essay 6 10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1inner accuracy τdistance from one, or residualJordan pairs: √τresidual, step 2: τthe rest: τdashed: slope ½ and slope 1 through the measurementsthe split is a square root, the residual is not

A square root the residual does not pay

With the exact Schur complement, the triangular saddle-point preconditioner puts every eigenvalue at one in Jordan blocks of size two, and GMRES finishes in two steps.

5 figures · Block preconditioning, essay 6 10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1inner tolerance τ, on the residualenergy error delivered, medianerror = toleranceκ(H) = 100κ(H) = 10⁴κ(H) = 1dashed: the error the tolerance would suggesta tolerance is a bound, not an accuracy

A tolerance is not an accuracy

A fixed perturbed block predicted what an inexact inner solve would do to a triangularly preconditioned saddle-point system: a two-step residual growing like the inner tolerance, a constant a few times the model's, and a step rule exact to one step on nine runs in ten.

5 figures · Block preconditioning, essay 7 0246810121416neverno extra rowsthe guess as it standsa basis chosen by z/sregularised, δ = 10⁻¹⁰basis point, any multipliers2 extra rowsthe guess as it stands3 of 6a basis chosen by z/sregularised, δ = 10⁻¹⁰4 of 6basis point, any multipliers4 extra rowsthe guess as it stands6 of 6a basis chosen by z/s4 of 6regularised, δ = 10⁻¹⁰4 of 6basis point, any multipliers8 extra rowsthe guess as it stands6 of 6a basis chosen by z/s5 of 6regularised, δ = 10⁻¹⁰5 of 6basis point, any multipliersfirst iterate whose crossover certifiessix programmes a row; QP shown, LP the samethe multipliers are a set

The multipliers were a set

A crossover that solves the equality problem an interior-point iterate's diagonal suggests, then certifies the answer, refuses a guess with more active rows than unknowns — which a degenerate vertex produces as a matter of course.

5 figures · Interior-point conditioning, essay 5 0246810121416182022slack exactly zerothe guess as it stands××××××a basis by the diagonal×××××regularised××××××the set questionslack 10⁻⁶the guess as it standsa basis by the diagonalregularisedthe set questionslack 10⁻⁸the guess as it stands××××××a basis by the diagonalregularised××××××the set questionslack 10⁻¹⁰the guess as it stands××××××a basis by the diagonalregularised××××××the set questionslack 10⁻¹²the guess as it stands××××××a basis by the diagonalregularised××××××the set questionslack 10⁻¹⁴the guess as it stands××××××a basis by the diagonal×××××regularised××××××the set questioniterate from which every later iterate certifies× at the right: never settles in the runlate where the rows are near, not on

The row that was nearly there

Move the spare rows of a degenerate vertex off it by 10⁻⁶ to 10⁻¹⁴ and the set question still certifies the last iterate of every run, as predicted.

5 figures · Interior-point conditioning, essay 6