A proof that does not ask how large the matrix is

A symmetric matrix is positive definite or it is not, and there are two ways to find out. One is to attempt a Cholesky factorisation and watch for a pivot that cannot be square-rooted. The other is to run conjugate gradients and watch for a direction along which the curvature pᵀAp is not positive. Both answer the question. They do not answer it in the same currency, and that difference is the whole of what this essay measures.

The factorisation’s cost is a fixed function of the dimension: a third of n³ arithmetic operations, whatever the matrix contains. Nothing about the spectrum makes it cheaper or dearer, and doubling n multiplies it by eight. The iteration’s cost is a count of matrix–vector products, and that count is not a function of n at all. It is a function of where the negative eigenvalue sits in the spectrum.

The reason is the one property a Krylov space has that nothing else does. A space of dimension k built from A and b sees the extremes of the spectrum first, and it does so whatever dimension the space is sitting inside. Adding sixty eigenvalues to the middle of a spectrum changes what the sixtieth Krylov vector contains and changes almost nothing about the third. So the number of products before a direction sees the one negative eigenvalue is set by how far that eigenvalue stands out, and a matrix four times larger with the same negative eigenvalue should cost about the same. That is a claim with a number attached.

The ladder at one size #

The matrix is built to a prescribed spectrum: n − 1 positive eigenvalues spread evenly over one decade from 1 to 10, and one eigenvalue at −λ. Nothing else about it is unusual. The positive part is well conditioned, the right-hand side is a fixed unit vector, and the negative eigenvalue is the smallest in magnitude of the n, which is deliberately the case a spectrum plot draws no attention to.

At n = 40 the products run 3, 4, 5, 6, 7, 8, 9, 9 as λ falls through 3, 1, 0.3, 0.1, 0.03, 0.01, 0.003 and 0.001. Eight spectra, and the ladder climbs by one product for each factor of about three in λ, flattening at the bottom. The trend is the one the rate the condition number predicts is built on and it runs in the reassuring direction: a large negative eigenvalue is large in magnitude, a Krylov space finds large eigenvalues first, and so the indefiniteness that takes longest to detect is the indefiniteness that matters least to an optimiser standing at that point.

That ladder is a fact about λ. The question here is what happens to it when n moves, and the prediction from the Krylov argument is that it should not move much. It is worth being precise about why the prediction is not obvious. The iteration builds its directions by the recurrence that produces them, and every one of them is a vector of length n. A larger matrix gives the negative eigenvalue more company: at n = 20 there are nineteen positive eigenvalues between 1 and 10, and at n = 80 there are seventy-nine of them, so the eigenvalues are four times as densely packed and the initial residual spreads its weight over four times as many eigenvectors. A reasonable guess is that the negative direction is therefore harder to isolate and the count rises.

It does not. The count is not about isolating the eigenvector, only about producing some direction whose curvature is non-positive, and that is a much weaker requirement than resolving an eigenvalue — the distinction the gap decides the eigenvector is entirely about. A direction needs only enough of the negative eigenvector in it that the positive contributions from everything else do not outweigh what it contributes, and since the negative eigenvalue here is the smallest in magnitude, that is a statement about a single ratio and not about a subspace being resolved.

Five sizes were run at eight values of λ each: forty spectra and forty counts. The sizes are 20, 30, 40, 60 and 80, a factor of four from end to end, and the two numbers worth carrying out of the set are the count at the severe end and the count at the mild end. At λ = 3 the certificate arrives after three products at four of the five sizes and after four at the fifth. At λ = 10⁻³ it arrives after eleven products at n = 20, ten at 30, nine at 40, eleven at 60 and ten at 80. A spread of one product at one end and two at the other, across a range over which a third of n³ runs from 2,667 to 170,667.

A quarter of the matrix, and a longer ladder #

At n = 20 the products run 3, 5, 6, 8, 9, 9, 10, 11. The severe end is identical to n = 40 and the mild end is two products worse. A twenty-square matrix takes eleven products to certify what a forty-square matrix certifies in nine.

That is not a rounding of the argument, it is the opposite of the size-driven story. If the count tracked the dimension, the smaller problem would be the cheaper one at every λ, and it is the dearer one at seven of the eight and equal at the other. The reason is visible in the construction: the positive eigenvalues occupy the same decade at both sizes, so at n = 20 they are spread thinly, and the ratio of the largest positive eigenvalue to the negative one is unchanged while the density of the spectrum between them is not. What decides the count is where −λ sits relative to the rest of the spectrum, and the answer at these two sizes is that it sits in slightly different places for reasons that have nothing to do with there being twenty rows rather than forty.

The comparison also settles the units. Eleven products at n = 20 is 8,800 arithmetic operations if the products are dense, against 2,667 for a third of n³. At n = 20 the certificate is the more expensive route in the hardest case, by a factor of about three. That is worth stating plainly because it is the honest reading and it is the shape of the whole comparison: the certificate does not win by being small, it wins by not growing.

Nine products at n = 40 is 28,800 operations against 21,333. Still dearer, by a third. The two costs are converging because one of them is standing still.

Four times as many eigenvalues, one product fewer #

At n = 80 the products run 3, 4, 5, 6, 7, 8, 9, 10. Set that beside n = 20’s 3, 5, 6, 8, 9, 9, 10, 11 and the larger matrix is cheaper at seven of the eight spectra and equal at the eighth. Over a factor of four in the dimension the extreme values of the ladder move from 3–11 to 3–10.

Ten products at n = 80 is 128,000 dense operations against 170,667 for the factorisation, so the certificate is now the cheaper route, and it became cheaper somewhere between n = 40 and n = 80 without any of its own numbers changing. The arithmetic behind the crossover is short. A dense matrix–vector product is about 2n² operations, so k of them cost 2kn², and the ratio to n³/3 is 6k/n. With k held at ten or eleven by the spectrum rather than by the size, that ratio falls like 1/n: it is 3.3 at n = 20, 1.35 at n = 40, 0.75 at n = 80, and it keeps falling.

The ladder does not stop at the largest size the figure draws. Run the same sweep at n = 120, 160, 200, 300 and 400 and the products come back as 4–12, 4–11, 4–11, 4–12 and 3–10. The last of those is the n = 80 ladder exactly, at twenty times the smallest size drawn and against a factorisation cost eight thousand times larger. Nothing in the count knows that n has moved.

And the dense count is the pessimistic one. The reason a trust-region Newton method can run at all on a large problem is that the Hessian is never assembled: the product is computed by a directional derivative of the gradient, or by the structure of the operator, and it costs whatever that costs rather than 2n². On the operators an operator with no entries is about, a product is linear or nearly linear in n, and then eleven products is O(n) work against a factorisation that cannot be started because there is no matrix to factor. That setting is the one a Krylov space for a problem that is not linear assumes throughout, and this measurement is what licenses the assumption.

What moves with n is the sharpness, and it moves without a pattern #

The cost is stable. The quality of the object bought with it is not, and the second half of this measurement is the less comfortable one.

The direction that fires the test has a Rayleigh quotient, and that quotient is not λ_min. It is some share of it, and the share is what says how much of the eigenvalue the direction has actually seen. Across the eight spectra at each size, the shares run:

There is no trend in that column. It is not rising with n, not falling, and not tightening: the worst case runs 6.4, 4.3, 11.5, 0.084 and 24.3 per cent as n runs 20, 30, 40, 60, 80, and the best case runs 33.1, 24.4, 41.9, 28.6 and 34.4. A caller who wanted to know how sharp the certificate would be at a given size has nothing to read off. The one thing that can be said is a floor and it is a low one: across every size and every spectrum drawn here the share stayed above a ten-thousandth, which is enough to prove indefiniteness and is not enough to estimate anything.

The worst case is not a direction that missed the eigenvector #

At n = 60 the products run 4, 5, 7, 8, 9, 9, 11, 11 and three of the eight shares sit under five per cent: 0.084 per cent at λ = 0.01, 4.4 per cent at λ = 0.003, and 0.30 per cent at λ = 0.001. The quotient at the first of those is −8.4·10⁻⁶ against an eigenvalue of −0.01.

Nothing is wrong with that certificate. A vector d with dᵀAd = −8.4·10⁻⁶ is a proof that the matrix is not positive semidefinite, it is checkable in one further product by somebody who did not run the iteration, and it is exactly as much of a proof as the direction at n = 80 whose quotient recovers 34 per cent. The two objects differ in sharpness and not in status, and that is the distinction the word certificate is carrying: a proof is a thing that either holds or does not, in the sense a bound that is proved is about, while an estimate is a thing that is close or far.

The obvious reading of a share of 0.084 per cent is that the direction has barely seen the negative eigenvector, and that reading is wrong. Expanding the triggering direction in the eigenvectors of the matrix, its overlap with the eigenvector belonging to −0.01 is 0.997. It has essentially found the eigenvector. What it has not found is the eigenvalue, and the two are separated by an arithmetic that is worth writing out: the negative eigenvalue contributes −9.944·10⁻³ to the quotient, the remaining five and a half thousandths of squared weight, spread over eigenvalues between 1 and 10, contribute +9.935·10⁻³, and what survives is the difference, −8.4·10⁻⁶.

That is cancellation, in the sense this collection means it everywhere else: two quantities agreeing to three digits, subtracted, leaving a residue whose size says nothing about either of them. It also explains the pattern in the shares, which is that there is none. Taking the worst spectrum at each size and reading the overlap beside the share:

The two columns do not track each other and in one place they run backwards: the direction at n = 20 recovers a larger share of its eigenvalue on an overlap of 0.68 than the direction at n = 60 recovers on an overlap of 0.997. The reason is that when λ is comparable to the positive eigenvalues, as it is at λ = 3, a modest overlap already dominates the sum and the cancellation is partial; when λ is a hundredth of them, a near-perfect overlap still leaves enough positive weight to cancel almost all of it. The share of λ is a measure of the spectrum’s contrast, not of the direction’s quality, and a caller reading it as the second is reading the wrong thing.

It is also the reason the quotient must not be handed onward as a curvature. A trust-region method that scaled a step by the measured curvature would be scaling by a number that is anywhere between a thousandth and two fifths of the truth, with no way to tell which, and the error would be worst exactly where the method is trying to take its longest step. What the method needs from the object is its direction, which is unbounded below in the model; the magnitude is not an input to anything.

One row of the sweep, from inside #

A point on the ladder is a whole iteration, and it is worth seeing one. On the 60×60 matrix with λ = 1 the curvature pᵀAp/pᵀp runs 6.27, 3.16, 2.21, 0.698 and then −0.2437, which is where the iteration stops. Four positive numbers, decreasing, and then a sign change: the divisor conjugate gradients needs has gone away, and what is left in the loop’s own variable is the direction that proves why.

The same figure carries the number that prices the alternative. MINRES on that identical system never forms pᵀAp — it minimises the residual over the same Krylov space rather than the A-norm of the error, so nothing in it needs the matrix to be definite — and it returns the solution in 42 steps. So on this matrix the detection costs five products and the solve costs forty-two, a factor of eight apart, and the early exit is not a small saving on a computation that was going to happen anyway. It is a different computation, finished before the other one is an eighth done. What the forty-two steps buy is a solution vector, whose residual should be read with a small residual is not a small error in mind; what the five products buy is a statement about the matrix.

The relationship between these two numbers is the reason the whole framing matters, and it is set out at one size and five eigenvalues by the division that cannot be done, which reads the same event as an output rather than a failure. That essay holds n at 40 and moves λ. This one holds the question and moves n, and the answer is that the axis it moves along is nearly flat.

Where the comparison stops being fair #

Three things are wrong with reading those numbers as “the iterative route wins”, and each of them is a place the certificate is genuinely the smaller object.

The factorisation answers a larger question. A symmetric indefinite factorisation gives the inertia: how many eigenvalues are negative, not merely that one is. One direction of negative curvature proves at least one and cannot distinguish a matrix with a single negative eigenvalue from one with thirty. Recovering the count means the factorisation, and a factorisation with nothing to pivot for is the account of what it costs to do that stably on the matrices where it is hardest.

A third of n³ is the dense figure and most large matrices are not dense. A sparse Cholesky costs what the fill-in costs, which is decided by the ordering and can be far below n³/3 or, on a bad ordering, close to it. The comparison here is against the dense factorisation because that is the cost a certificate is usually set against; on a banded or well-ordered matrix the factorisation is much cheaper than the table says and the crossover moves out.

And symmetry is not definiteness. The whole question only arises because when symmetry is not enough is the ordinary situation for a Hessian: symmetric by construction, definite only at a minimum, and indefinite at every saddle a non-convex problem contains.

There is a fourth thing, and it is about the measurement rather than the method. The sweep that produced every number above is far more expensive than either route it compares. Each row builds a dense matrix from a prescribed spectrum, which costs about n³ multiply–adds and an orthogonalisation of the same order, and there are eight rows. At n = 200 that is roughly 8n³, some sixty-four million operations, against 2,666,667 for the factorisation it is being set against — the instrument costs twenty-four times the thing it is measuring. The certificate at that size still costs eleven products.

What follows for the methods that use it #

A trust-region Newton method can be budgeted in products. The count does not depend on the dimension, so the budget written for a problem with fifty variables is the budget for one with fifty thousand, and the quantity to reserve is a handful of products rather than a fraction of a factorisation.

A stopping rule must not be built on the quotient. The share of λ recovered is between a thousandth and two fifths with no pattern in n, so a rule reading the magnitude is reading noise. The sign is the output.

The zero that stops the iteration means something different in each of its three settings. Here it is a measurement of the problem. In the same zero and nothing was found it is a recurrence losing contact with itself and producing nothing, and in the zero that means it is finished it is the Krylov space closing with the answer inside it. Three identical divisions by something that has gone to zero, three different pieces of news, and the number itself says which.

And an independence of n is not one phenomenon. This site has now measured three of them and no two have the same mechanism. The multigrid convergence factor of a rate that does not notice the size is flat because the hierarchy grows with the problem; the distortion in the dimension does not appear is independent of the ambient dimension because a projection’s error is decided by the number of points rather than by the space they sit in; and this count is flat because a Krylov space of dimension k reads the ends of a spectrum and is indifferent to what is between them. A reader who collects them as one law will apply it where it does not hold.

The refusal #

The claim this essay is set against is that finding a direction of negative curvature is an eigenvalue computation, so it costs what an eigenvalue computation costs and degrades as the matrix grows. The measurement is right and the blame is wrong: detecting indefiniteness is genuinely an eigenvalue question, and the cost of answering it is set by the position of the eigenvalue rather than by the size of the problem it sits in.

The assertion published against it is the family’s own refusal of a sweep drawn at a size it cannot afford. It is fed a request at n = 200 and must decline it, and the reason it declines is the point: what has become unaffordable at that size is the apparatus that measures the certificate — eight dense matrices built from prescribed spectra, at about 8n³ multiply–adds — and not the certificate, which costs eleven products there and ten at n = 400. A refusal that lets the two be confused would be publishing the instrument’s cost as the method’s.