Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Negative curvature — where it appears

A direction along which a quadratic model decreases without bound, which stops conjugate gradients and is what a trust-region method wants. It is a failure for a method minimising a quadratic and a gift for one minimising over a region, since it points at the direction the model decreases along.

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

significand bits10³10⁴10⁵10⁶10⁷10⁸10⁹10¹⁰κ(A)87892634456329625911109435761199127514162024every matrix positive definiteruns producing a false certificate14of runs in total72never above, in significand bits12first κ at eight bits10⁵the comparison was correctand what it proved was not true

Deciding that a zero has arrived

The previous tolerances were offers — accept this much error, save this much work. A detection threshold is not an offer, because both directions are failures. One matrix here has three genuinely near-invariant subspaces, and the constant somebody typed decides which of them the recurrence stops at; at eight significand bits the same kind of constant produces a proof of something false.

error · Deliberate zero at ε = 10⁻¹⁰Bunch–Kaufman, |L||D||Lᵀ| ÷ A6.7rook (bounded), |L||D||Lᵀ| ÷ A9.310⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110²10⁴10⁶10⁸10¹⁰coupling εsizeBunch–Kaufman: multiplierBunch–Kaufman: productrook (bounded): multiplierrook (bounded): productdashed: ‖|L||D||Lᵀ|‖ ÷ ‖A‖the multipliers grow and the product does not

Where the multipliers go

Bunch–Kaufman bounds the growth in D and not the entries of L, and the warning attached to that is that everything which later uses the factors inherits the size of L. On a matrix built to make those entries 1.2 over ε, they reach 1.2·10¹⁰ while the solve's backward error stays at 1.6·10⁻¹⁶, |L||D||Lᵀ| stays at 6.7 times ‖A‖, and a step of refinement changes nothing. The large multipliers are where the rule has put the matrix's ill-conditioning. A direction of negative curvature read from those factors finds 7·10⁻¹⁶ of the curvature that is there; the bounded rule's finds 13%.

elimination · Cholesky μ = −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. With two negative curvatures, the prediction was that hiding both is paid for by the faster, and that hiding only the faster leaves the slower one's race to run. The first half holds to half a per cent on three pairs, and to one and a half on two whose curvatures differ by a factor of two and of 1.2. The second does not: hiding either direction alone moves the verdict by a fixed handful of steps, the same at two decades as at sixteen, because the direction left in view is already growing. Only the intersection of the two hyperplanes hides anything — and it hides less than either curvature can alone, 1,127 steps at worst against 2,907, with random right-hand sides' slowest at 79 against 417.

constraint · Quasi-definite fractions of the curvaturebounded rule's direction, every ε0.14nearest zero at ε = 10⁻⁸, ÷ λ10⁻¹⁶10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹coupling ε|quotient| ÷ |smallest eigenvalue|Bunch–Kaufman's directionthe bounded rule'seigenvalue nearest zeroinverse iteration goes where the eigenvalue nearest zero isa solve amplifies the smallest, not the most negative

A curvature direction the factors cannot refine

A direction of negative curvature read from Bunch–Kaufman's factors held 7·10⁻¹⁶ of the curvature that was there, and the bounded rule's held 14 per cent. The prediction was that a few steps of inverse iteration with the same factors would recover it from either. One step leaves both under a thousandth, and two put both on positive curvature, at the eigenvalue nearest zero — because a solve amplifies the smallest eigenvalue in magnitude, not the most negative. What recovers the curvature is the matrix, not its factors: Lanczos from either direction reaches ninety-nine per cent in six to nine products at every coupling, and power iteration from Bunch–Kaufman's direction has not reached a tenth after sixty.

elimination · Cholesky 012345678-7-5-3-11357conjugate gradient steppᵀAp ⁄ pᵀpλₘᵢₙ = -0.1positive: a step existsnegative: a certificate existsone matrix, two questionsstep it turns at6quotient there-0.027share of λₘᵢₙ recovered0.27λₘᵢₙ, by construction-0.1MINRES steps on the same system37the division that cannot be doneis the answer to a different question

The division that cannot be done

Conjugate gradients divides by pᵀAp at every step, and on a matrix that is not positive definite that number can be zero or negative. The guard against it has been here from the first essay and described it as a failure. In the method that made conjugate gradients famous it is the single most valuable object the iteration can produce, and it costs six matrix–vector products.

iterative · Breakdown 10⁻³10⁻²10⁻¹1024681012size of the negative eigenvalue, −λproducts before the test firesharder to find, and milder8 spectra, n = 50products at the largest λ3products at the smallest10smallest share of λ recovered0.14largest0.34the one that hidesis the one that matters least

A proof that does not ask how large the matrix is

Proving a Hessian indefinite costs three matrix–vector products when the negative eigenvalue is 3 and nine to eleven when it is a thousandth, and that pair of numbers barely moves across a fourfold range in n. The factorisation that settles the same question costs a third of n³, which grows by a factor of sixty-four over the same range.

iterative · Breakdown 110¹00.30.60.91.2trust-region radius Δshare of the exact model decreasethe exact subproblem7 radii, n = 60share at the smallest radius0.95share at the largest0.3products, at most8radii stopped by the curvature4a few products against an eigendecompositionand most of the decrease

The certificate that arrives soonest is worth least

The more negative a Hessian's smallest eigenvalue, the sooner conjugate gradients meets a direction of negative curvature — and the less of the exact trust-region decrease that direction turns out to be worth. At λₘᵢₙ = −10 the step arrives after two products and gets 39.6 per cent; at −10⁻³ the same two products get 89.8, and the whole sweep costs eight.

iterative · Trust-region

Named alongside it

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

CertificateIndefinite matrixKrylov subspaceConjugate gradientsEigenvaluesBackward errorBunch–KaufmanCholeskyIterative refinementLDLᵀ factorisationMatrix-freeMINRES

All concepts