Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Positive definite — where it appears

The property that xᵀAx is positive for every nonzero x, required by conjugate gradients of both the matrix and its preconditioner. It is worth more than precision here: it removes the pivot search, halves the arithmetic, and makes the growth factor exactly one.

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

10²110¹10²size niterations to 10⁻¹⁰λₘᵢₙ(C) changes signno preconditionerStrang's circulantthe preconditioner's own spectrumλₘᵢₙ(C) at n = 16-0.4λₘᵢₙ(C) at n = 32-0.14λₘᵢₙ(C) at n = 640.016λₘᵢₙ(C) at n = 1280.051λₘᵢₙ(C) at n = 2560.053left of the line the repair costs stepsright of it, the count stops counting n

A preconditioner that changes sign

Strang's circulant preconditioner takes Toeplitz conjugate gradients from 179 steps to 10 at n = 256. At n = 64 on the same family it takes 66 steps to 109 — worse than doing nothing. Between those rows the preconditioner's smallest eigenvalue crosses zero, and nothing in the published account of the method mentions that it can be negative.

structure · Preconditioning 10²110¹10²size niterations to 10⁻¹⁰λₘᵢₙ(C) changes signno preconditionerStrang's circulantthe preconditioner's own spectrumλₘᵢₙ(C) at n = 16-0.4λₘᵢₙ(C) at n = 32-0.14λₘᵢₙ(C) at n = 640.016λₘᵢₙ(C) at n = 1280.051λₘᵢₙ(C) at n = 2560.053left of the line the repair costs stepsright of it, the count stops counting n

The circulant that cannot be indefinite

The previous essay found a preconditioner taking 117 steps against an unpreconditioned 59, because its smallest eigenvalue was −0.173. Average the two diagonals instead of choosing between them and the count is 7, 8, 9, 10, 10 across a factor of sixteen in size.

structure · Toeplitz 10¹10³10⁵10⁷10⁹10¹¹110¹10²10³10⁴condition number of the matrixgrowth factorbound 2^11partial pivotingCholeskyno pivot to gain fromCholesky growth, every κ1Cholesky interchanges0partial pivoting, worst9the bound, 2^112048both eliminations reach the same growthand only one of them had to swap to get there

A factorisation with nothing to pivot for

Cholesky's growth factor is not bounded by one. It is equal to one, at every size and every condition number, and the two-line reason is why the algorithm needs no pivoting at all — not "usually gets away without it". Its only failure is the square root of a non-positive number, which is exactly the test for definiteness, and in floating point that test moves with the precision.

elimination · Cholesky -12-11-10-9-8024681012log₁₀ of how nearly dependent the columns areverdicts that disagreed, of 40724103which one is correctmatrices tested200verdicts disagreed26fused was right9unfused was right17lower part: thefused build was righta sign has no last digitso a verdict has nowhere to hide

A matrix that is definite on one machine

Two hundred Gram matrices, two conforming builds, and twenty-six of them get different answers to "is this positive definite". The exact verdict, from determinants in BigInt rationals, says the fused build is right nine times and the other one seventeen.

machine · Fma contraction ‖QᵀQ − I‖ of the implied Qκ = 10⁸, Cholesky0.37κ = 10⁸, sweep8.5·10⁻⁹κ = 10¹⁰, Cholesky1.3κ = 10¹⁰, sweep3·10⁻⁷κ = 3·10¹⁰, Choleskyrefusedκ = 3·10¹⁰, sweep6.7·10⁻⁶κ = 10¹², Cholesky1.5κ = 10¹², sweep1.4·10⁻⁴the safe run is the one that failsrefusals in the range1wholly non-orthogonal returns2the pivot it refused on-6.5·10⁻¹⁷one of these outcomes is safeand it is the refusal

The licence is not the boundary

Cholesky QR is licensed by κ²u ≪ 1, which reaches equality at κ = 9.5·10⁷ in double precision. At 10⁸ the factor it returns is already 0.37 away from orthogonal, and it goes on returning factors as far as 10¹³ — refusing at scattered condition numbers in between, at different ones for eight columns and for six.

machine · Algorithm selection

Named alongside it

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

Circulant preconditionerClustered spectrumCondition numberConjugate gradientsGram matrixPreconditioningToeplitz matrixUnit roundoffAlgorithm selectionBackward errorCholeskyCholesky factorisation

All concepts