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

Every essay — page 23

Essays 529 to 547 of 547, 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.

-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.

8 figures · Interior-point conditioning, essay 1 -18-15-12-9-6-300log₁₀ ‖PKPᵀ − LDLᵀ‖ / ‖K‖share of orderingsbestworstexistence and stabilityfactorise1unregularised0.69worst growth6.4·10⁵growth × γ0.64the ordering is free to chooseand not free of consequence

The regularisation that legalises every order

Perturb a saddle-point matrix's two blocks in opposite directions and it acquires a factorisation with a diagonal D under every symmetric permutation — not under a good one, under all of them.

7 figures · Quasi-definite, essay 1 -5-3-11350eigenvalueHZᵀHZK4 negative — Cholesky of H stops at row 30 negative — a minimum on the constraint(10, 4, 0) = In(ZᵀHZ) + (4, 4, 0)one factorisation, no Zpositive, LDLᵀ of K10negative, LDLᵀ of K4negative in H4negative in ZᵀHZ0the count follows the reduced Hessiannot the Hessian

A minimum the Hessian cannot see

A Hessian with four negative eigenvalues can sit at a constrained minimum, and a Cholesky of it stops at the third row.

7 figures · Saddle-point systems, essay 3 -1-0.500.511.50eigenvalue of P⁻¹Ktriangular [[H, Aᵀ], [0, −Ŝ]] — 1 valuediagonal blkdiag(H, Ŝ) — 3 valuessteps to a residual of 10⁻¹⁰GMRES, triangular2MINRES, diagonal3‖P⁻¹K − I‖54computed |λ − 1| at c = 18.1·10⁻⁸one copy of each value against twoand the counts follow

One eigenvalue and two steps

Put the off-diagonal block back into a block-diagonal saddle-point preconditioner and every eigenvalue of the preconditioned matrix becomes exactly one.

7 figures · Block preconditioning, essay 3 0246810121410⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹interior-point iterationrelative error, and μcertified from iterate 1μthe iterate's errorthe crossover's errorone solve, checkediterations15first certified iterate1iterate error there0.22crossover error there4·10⁻¹⁴the active set arrives long before the digitsand a crossover collects them at once

The active set before the digits

An interior-point method takes fifteen iterations on a quadratic programme with forty constraints, and its iterate has eight correct digits at the eleventh.

8 figures · Interior-point conditioning, essay 2 -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⁶.

7 figures · Block preconditioning, essay 4 01234567910δ added to Hpositive pivots−λmin(H) = 4.67|μ| = 1minimumsaddlewhat the signs are countingminimum, true count10saddle, true count9saddle read as minimum from1.1guarantee needs δ past5.1the signs count ZᵀHZ + δInot the curvature the problem has

A shift that certifies a saddle

On a constrained problem whose Hessian has four negative eigenvalues, a saddle-point matrix is quasi-definite only once H + δI is positive definite — past δ = 5.08 here.

6 figures · Quasi-definite, essay 3 -18-15-12-9-6-300log₁₀ ‖PKPᵀ − LDLᵀ‖ / ‖K‖share of orderingsbestworstexistence and stabilityfactorise1unregularised0.67worst growth5·10⁷growth × γ0.5the ordering is free to chooseand not free of consequence

The perturbation that does the work

A saddle-point matrix made quasi-definite is perturbed in both blocks, and the laws measured for it moved both together.

7 figures · Quasi-definite, essay 2 the damagewell scaled, nothing done0.9110^±3, nothing done0.095never certified, of 62at 10^±3rows to unit norm0.64rows by right-hand side0.6start at the rows0.43012300.250.50.751rows rescaled by 10ᵏshare that certifiesnothing donestart at the rowsrows to unit normrows by their right-hand sidethe grey line is a well-scaled programme with nothing doneboth equilibrations are flat, and below it

Two repairs for one symptom

Rescale a quadratic programme's constraint rows over six decades and the crossover that certified its answer at iterate 1.5 first certifies at 69.8, with two of six programmes never certifying at all.

6 figures · Interior-point conditioning, essay 3 the certificatecertificate, iterate1.5its error1.8·10⁻¹⁴the iterate's own error0.14the tightest μ testμ < 10⁻¹³, iterate15its error1.6·10⁻¹²one attempt ÷ one step0.130246810121410⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹interior-point iterationrelative error returnedμ < 10⁻⁴μ < 10⁻⁶μ < 10⁻⁸μ < 10⁻¹⁰μ < 10⁻¹³the certificatethe iterate it is built fromthe grey line is the certificate's own errorno tolerance on μ reaches it, at any iterate

A test with no tolerance in it

An interior-point method's own stopping test is a tolerance on μ, and at the tightest it can be set to it stops after 15 iterations with 1.6·10⁻¹².

5 figures · Interior-point conditioning, essay 4 10⁻³10⁻²10⁻¹110¹10²10³10⁴10⁵the shift the reduced Hessian neededshift taken ÷ shift needed10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹median of eightexactly enoughκ(A) = 10, eight draws per curvatureworst ratio, curvature 10⁻⁸·²⁵1.8·10⁴worst ratio above 10⁻²7.3trials stopped below the curvature0factorisations a solve, mean3.2above one: more convex than the problemon the floor: the count passed a saddle

The shift that stops at the first right count

A nonconvex solver that finds the wrong inertia adds δI to H and tries again, and the δ it settles on is used as though it measured the curvature it corrects.

7 figures · Saddle-point systems, essay 4 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