A vertex, not an order

A definite pivot sits at the mean found that on a positive-definite matrix the smallest pivot of a Cholesky factorisation is a poor shift towards the smallest eigenvalue, and why. Each pivot is one over a diagonal entry of an inverse, and a diagonal entry of an inverse, written in the eigenvector basis, is a weighted sum of the reciprocal eigenvalues with weights that add up to one. So the pivot is a weighted harmonic mean of the spectrum. On ninety dense matrices the weights were nearly equal and the smallest pivot sat between 0.45 and 1.44 times the plain harmonic mean, two to twenty-two times above $\lambda_{\min}$.

That essay closed on the one case its matrices could not show. A matrix whose bottom eigenvector is concentrated on a few coordinates puts a large weight on $\lambda_{\min}$ at those coordinates, and a pivot taken there would feel it. The prediction it signed was specific about which factorisation would feel it: “on a path-graph Laplacian with one weak edge, shifted to be definite, the smallest pivot under largest-diagonal-first pivoting lands within a factor of 1.2 of $\lambda_{\min}$ and is a usable shift unpushed, while the unpivoted pivot stays near the harmonic mean — the first family on which the pivoting rule decides whether the factorisation knows the bottom of the spectrum.”

Both halves fail, in opposite directions, and the reason they fail is the same.

Three matrices with a weak link #

Three families of order 24, thirty matrices each. Every matrix has its vertices relabelled by a random permutation before it is factorised, so the natural order carries no information about where anything is; a factorisation without pivoting then takes the vertices in an order that is as good as random, and one with the largest diagonal first takes them in an order the matrix chooses.

• One weak edge. The prediction’s own family: the Laplacian of a path on 24 vertices, every edge of weight one except one of weight $w$ at a random place, plus $10^{-3}$ times the identity so that it is definite. This is the matrix a matrix with no numbers in it built from a graph, with its one exact null vector lifted off zero.
• A vertex on a weak tether. A path of 23 vertices grounded at one end — a unit spring from the first vertex to the ground, which is the device the vertex nobody solves for uses to remove a Laplacian’s kernel — with a 24th vertex hung off a random interior vertex by a spring of weight $w$.
• A well three wide. A path grounded at both ends with a unit potential on every vertex except three neighbouring ones at a random place: the discrete form of a particle in a box with a shallow dip in its floor.

At $w = 10^{-3}$ the three give the three answers in the figure.

On the weak edge, nothing reaches 1.2. Taking the largest diagonal first gives 3.9 to 12.3 times $\lambda_{\min}$, the unpivoted factorisation 4.0 to 12.6, and on no matrix is either nearer $\lambda_{\min}$ than the second eigenvalue. On the tether, everything reaches it — the unpivoted factorisation included. On the well, nothing reaches it, and no order could: the best vertex left to the end gives 2.24 on every matrix.

A weak edge splits the path in two #

The prediction’s premise was that a weak edge localises the bottom eigenvector. It does not, and it cannot. A Laplacian sends the constant vector to zero, whatever its weights, so the constant vector is exactly an eigenvector of the shifted matrix with eigenvalue $10^{-3}$, the smallest. Its share of every vertex is exactly one twenty-fourth, on every one of the thirty matrices and at every weight from $10^{-1}$ to $10^{-4}$. The identity in the earlier essay then caps every pivot taken last at twenty-four times $\lambda_{\min}$ and puts no floor under the share of any vertex that would let it do better.

What the weak edge does is bring the second eigenvalue down. Cut the path at the weak edge and each piece has its own constant vector; joined by a spring of weight $w$, the two pieces’ constants combine into the bottom vector, which is the same on both, and the second, which has one sign on each piece. The second eigenvalue sits above the first by roughly $w$ times the ratio of the path’s length to the two pieces’ lengths, so at $w = 10^{-4}$ it is within two to four per cent of $\lambda_{\min}$. The pair together is localised — not on a vertex but on a piece — and that is what the pivot reads.

A vertex in a piece of $k$ vertices has the pair’s combined weight of about $1/k$, so one over its diagonal entry of the inverse is about $k$ times $10^{-3}$. Leaving the best vertex to the end puts the last pivot at the shorter piece’s length times $\lambda_{\min}$: measured against the shorter piece’s vertex count, the best last pivot is 0.97 to 1.03 times it on all thirty matrices at $w = 10^{-4}$, and 1.03 to 1.31 at $10^{-3}$, where the second eigenvalue has not yet come down to meet the first. The weak edge’s place is random between the third vertex and the twentieth, so the shorter piece has three to twelve vertices, and that is the spread of the dots.

And the second half of the prediction’s test — usable, meaning nearer $\lambda_{\min}$ than $\lambda_2$ — is out of reach on this family for a reason that has nothing to do with pivots. When two eigenvalues are two per cent apart, every shift more than one per cent above the lower is nearer the upper. The gap decides the eigenvector is the account of what such a pair does to inverse iteration: the vector it converges to is only as well determined as the gap allows, and here the gap is the weak edge.

A vertex on a weak spring #

The tether is the family the prediction meant. With the spring at $10^{-3}$, the hung vertex barely moves the rest of the path, and the rest of the path barely moves it: its own Rayleigh quotient is its diagonal entry, the spring’s weight, and the grounded path’s lowest mode costs about $4.5 \cdot 10^{-3}$ — four and a half times as much. So the bottom eigenvector sits on the hung vertex, with 0.994 to 0.999 of its weight there, and its eigenvalue is a little under the spring’s weight: $9.91 \cdot 10^{-4}$ on the matrix the dial below opens on.

Both factorisations find it. With the largest diagonal first, the hung vertex has the smallest diagonal entry of the matrix, so it is taken last, and its pivot is 1.001 times $\lambda_{\min}$ on the matrix shown. Unpivoted, it is taken wherever the relabelling put it — thirteenth on this matrix — and its pivot is 1.009 times $\lambda_{\min}$. The pivots on either side of it are near one and two, the path’s own scale; the hung vertex’s pivot is a single dip three decades below them, and it is the smallest pivot of the factorisation because nothing else in the matrix is anywhere near that small.

Across the thirty matrices the unpivoted smallest pivot is 1.004 to 1.025 times $\lambda_{\min}$, taken at every position from the first to the twenty-fourth; it is taken last on one matrix of thirty. That is 0.05 times the harmonic mean, which on this family is nineteen times $\lambda_{\min}$. The prediction said the unpivoted pivot would stay at the mean. It is twenty times below it, and within two and a half per cent of the bottom.

Turning the dial up shows where that stops. At a tether of $10^{-2}$ the hung vertex’s own cost is now twice the grounded path’s lowest mode; the bottom eigenvector moves off it into the path, its largest share falls to about an eighth, and the smallest pivot under both rules rises to just over twice $\lambda_{\min}$. At $10^{-1}$ the dip in the pivots is gone, the bottom mode is a smooth arch along the path, and the pivots behave like the dense matrices of the earlier essay — falling towards the harmonic mean and stopping there.

Two means of the same weights #

Why the unpivoted pivot needs no help is a fact that was in the earlier essay’s identity all along, one line further on. Write $s_i(v)$ for the share of vertex $v$ in the $i$-th unit eigenvector — the square of that component — so that the shares of any vertex add to one over the eigenvectors. Then

$$\frac{1}{(A^{-1})_{vv}} = \Big(\sum_i \frac{s_i(v)}{\lambda_i}\Big)^{-1}, \qquad a_{vv} = \sum_i s_i(v)\,\lambda_i .$$

The first is a weighted harmonic mean of the spectrum, the second a weighted arithmetic mean with the same weights. The first is the pivot $v$ gets if it is eliminated last. The second is the pivot it gets if it is eliminated first — a Cholesky pivot taken first is just the diagonal entry. A pivot taken anywhere in between lies between the two, because each elimination step subtracts a nonnegative amount from the diagonal entries left behind, and the harmonic mean is where the subtractions stop.

Both means are at least $\lambda_{\min}$. The harmonic one is at most $\lambda_{\min}/s_1(v)$, because its sum contains the term $s_1(v)/\lambda_{\min}$ and every other term is positive; the figure shows that ceiling holding on all 270 last pivots. And both collapse onto $\lambda_{\min}$ as $s_1(v)$ goes to one, at the same rate. When the bottom eigenvector sits on one vertex, that vertex’s diagonal entry is already within a few per cent of $\lambda_{\min}$, the pivot taken there is squeezed between that diagonal entry and something lower, and it does not matter which step of the factorisation it falls on.

The arithmetic end can be read straight off the matrix. On the tethered family the smallest diagonal entry is 1.006 to 1.025 times $\lambda_{\min}$ — a shift as good as the best pivot, before any factorisation has been started. On the well it is 5.9 times, more than twice as far as the worst pivot, and on the weak edge it is a thousand times, because every diagonal entry of a shifted Laplacian is at least one plus the shift while the bottom is the shift alone. The factorisation earns its keep by moving from the arithmetic mean to the harmonic one, and that move is worth a great deal exactly when the bottom is spread and nothing at all when it is not.

So the question the prediction put to the pivoting rule has no work for the pivoting rule to do. Whether a factorisation “knows the bottom of the spectrum” is decided by whether some vertex holds most of the bottom eigenvector; the order decides only whether the pivot read there is the arithmetic or the harmonic mean of the same weights, and with a share near one those are the same number. With a share of a twenty-fourth they are both far away. The cases between are the well.

Where the hung vertex takes the bottom #

The tether’s weight is a dial between the two regimes, and the transition sits where the identity says it should: where the hung vertex’s own cost, the spring’s weight, passes the cost of the grounded path’s lowest mode.

Below the path’s own bottom, $4.47 \cdot 10^{-3}$, the median share is above 0.86 and both rules’ median pivots are within eleven per cent of $\lambda_{\min}$; at a weight of $10^{-3}$, within two. Above it the share falls to an eighth within a factor of two in weight, and the pivots climb with the weight: 2.4 and 2.2 times $\lambda_{\min}$ at $10^{-2}$, 18 and 9.9 times at $10^{-1}$. The median share crosses one half between $3.2 \cdot 10^{-3}$ and $5.6 \cdot 10^{-3}$, astride the path’s bottom.

The dotted curve is the ceiling for a pivot taken last, and the blue curve, whose pivots are all taken last, stays under it. The red curve crosses it above $10^{-2}$, which is not a contradiction: an unpivoted pivot taken early is bounded by the arithmetic mean, not the harmonic one, and once the bottom has spread along the path the arithmetic mean of a vertex’s weights is dominated by the path’s large eigenvalues. Here the order does matter, by a factor of two — and in the regime where neither order gives a usable shift.

A well three wide #

The well is the case between. Its bottom eigenvector is a bump spread over the three vertices with no potential, with 0.37 of its weight on the middle one and 0.25 on each side, and a little leaking into the barrier. The best last vertex is the middle one, and the identity puts its pivot at 2.24 times $\lambda_{\min}$, which is what every matrix shows: the well has the same shape wherever it sits, and the relabelling cannot change a share.

Taking the largest diagonal first leaves one of the three well vertices to the end — they share the smallest diagonal entry, two — but which one is decided by the tie, and on all thirty matrices the rule takes an edge vertex last, with a share of 0.25 and a pivot of 2.62 times $\lambda_{\min}$. The unpivoted factorisation reads 2.24 to 3.91 depending on where the relabelling put the three. Neither is usable: the second eigenvalue is three times the first, so the midpoint is at twice $\lambda_{\min}$ and every pivot here is above it.

The arithmetic gives a rule of thumb that the three families agree on. The bottom eigenvector’s largest share is roughly one over the number of vertices it lives on — a twenty-fourth on the weak edge’s constant vector, one over the shorter piece’s length for the pair the weak edge makes, about one on the tether, a little more than a third on the well — and the best pivot any order can reach is about $\lambda_{\min}$ times that number. A factor of 1.2 needs a bottom that lives on 1.2 vertices.

One factorisation where the bottom is a vertex #

The search from the earlier essays — shrink the shift by 1.25 until $A - \sigma I$ factorises with every pivot positive, which an eigenvalue count that cannot be slightly wrong showed is an exact test of whether $\sigma$ is below the spectrum — costs what the pivot’s distance above $\lambda_{\min}$ says it should.

On the tether, one step of either kind on every matrix: the pivot is within 2.5 per cent of $\lambda_{\min}$, so dividing by 1.25 lands below it and the next factorisation succeeds. On the weak edge, seven to twelve shrinks and two to four halvings, the same counts the dense families gave in the earlier essay. On the well, four to seven shrinks and two halvings. The search does not care which family it is in; it counts the logarithm of the pivot’s distance, and the distance is the number of vertices the bottom lives on.

The tether’s single step is the result the earlier essay was looking for: a factorisation that hands over its own shift, needing one more to confirm it. It gets there with no pivoting at all, which is what makes it cheap. A factorisation that has to pivot for the shift’s sake pays for the comparisons and loses whatever ordering the matrix’s sparsity wanted, and a factorisation with nothing to pivot for is the reminder that a definite matrix has no stability reason to pay either.

What the prediction mistook #

The prediction took the pivoting rule as the instrument and the matrix as the subject. The measurement says it is the other way round. On a definite matrix the pivot at a vertex is fixed between two means of one set of weights, and the weights are the matrix’s — the shares of its eigenvectors on that vertex. A pivoting rule can only choose which vertex is read, and which of the two means it is read at. When the weights put nearly everything on $\lambda_{\min}$ at some vertex, both means are there, and any order finds it as soon as it reaches that vertex. When they do not, neither mean is near, and no order can manufacture a share the matrix does not have.

There is a smaller mistake inside the larger one, and it is worth keeping because it is easy to make. A weak edge sounds like the definition of a localised mode, and on an unshifted Laplacian it is the definition of a good partition — two Laplacians of one graph and the Fiedler vector both read the cut off the second eigenvector. But it is the second eigenvector a weak edge shapes. The bottom one is the constant, and shifting the Laplacian to make it definite shifts every eigenvalue by the same amount and changes no eigenvector. To put the bottom on a vertex the vertex has to be cheap on its own — a small diagonal entry, a soft spring to everything — which is what the tether is and what the weak edge is not. A distance computed by a solve prices the same distinction from the other side: a weakly attached vertex is the one with a large effective resistance to the rest of the graph, and that resistance is a diagonal entry of an inverse.

The earlier essays on shifts read pivots for different reasons. The push a pivot needs belongs to the matrix found the indefinite rules’ most negative pivot too erratic to aim with, because an indefinite pivot is a weighted harmonic mean of numbers of both signs and can be anywhere. A definite pivot cannot be anywhere — it is fenced in by the two means — and this measurement says the fence is narrow exactly when the bottom eigenvector is concentrated, and nowhere else.

What relabelled paths do not show #

All three families are paths, so every vertex has at most three neighbours and every eigenvector is a one-dimensional shape. A two-dimensional grid with a weakly attached vertex would localise the same way — the identity does not care about dimension — but a grid’s own lowest mode is cheaper than a path’s of the same size, so the tether would have to be weaker to take the bottom. The well is the case most likely to mislead at scale: a dip in a potential spread over a patch of a two-dimensional mesh puts a share of one over the patch’s area on its best vertex, and the pivot is that many times $\lambda_{\min}$, which can be hundreds. The relabelling makes the unpivoted factorisation’s order random; a real matrix arrives in an order chosen for its sparsity, and a nested-dissection order tends to eliminate the vertices of a small separator last, which is a choice about the graph and not about the bottom.

Still open: a bottom on two vertices, and a well with an area #

A bottom shared by two vertices. Hang two vertices off the path by springs of $10^{-3}$ and $1.1 \cdot 10^{-3}$, far apart. The bottom eigenvector then sits on one and the second on the other, their eigenvalues ten per cent apart. The prediction with a sign is that both rules’ smallest pivot lands on the weaker spring’s vertex within 2.5 per cent, as on one tether, and is usable on every matrix; but that brought within one per cent of each other, the pair behaves like the weak edge’s pair — the pivot stays within 2.5 per cent of $\lambda_{\min}$ while no shift above it is usable — the first family on which a good pivot and a usable shift come apart.

A well with an area. The rule of thumb says the best pivot is $\lambda_{\min}$ times the number of vertices the bottom lives on. On a 16 by 16 grid with a unit potential everywhere except a square well of side $k$, the prediction is that the best last pivot over $\lambda_{\min}$ grows like $k^2$ — near four times for each doubling of the side, from about 2.5 at a side of two to about 35 at eight — and that the largest-diagonal rule, choosing among the well’s equal diagonal entries by its tie, lands on an edge or a corner of the well and loses a further factor of two or more against the best vertex, as it does by seventeen per cent on the path’s well of three.