The thread: Where the algebra stops being the arithmetic — page 11
The same zero, and nothing was found
Change the recurrence by two lines and the divisor stops being a norm. It becomes an inner product of two vectors from two different sequences, and an inner product of two different vectors is zero on a whole hyperplane — with neither vector anywhere near zero, nothing invariant, and nothing converged. The arithmetic event is identical and the meaning is opposite.
Elimination, and the swapThe doubling is in the row already
Interleave d copies of Wilkinson's matrix and every pivot rule that looks up to d eliminations ahead walks into growth 2^(n/d − 1); escaping costs a look one step deeper, and a deeper look multiplies its trial eliminations. Rook pivoting looks no further than the present step and escapes every one of them — growth exactly 2 at every deferral and every size — for 3.2 times partial pivoting's comparisons whatever the deferral. The doubling a look-ahead hunts for in the future is already visible in the row in front of it. And the leak that was supposed to let the two-step rule escape was placed where no pivot is ever chosen: at every size up to one, it changes nothing.
Orthogonality, measuredThe budget cannot finish the tree
The least-resistance spanning tree makes a network's loop equations well conditioned and its loops long, and the long loops cost a direct solver up to twice the breadth-first tree's factor work. A tree that refused any arc whose loop would run past a budget — 24 arcs, twice the breadth-first tree's longest — was predicted to keep the conditioning within twice the least tree's and save a third of the extra work. It keeps the conditioning and saves nothing. Every budget that binds leaves parts of the network it cannot join, the arcs it refused are needed to finish the tree, and they close loops as long as the least tree's. Half the least tree's loops are already as short as the property behind its conditioning allows; the slack is in the other half, and a greedy budget cannot reach it.
Sparsity, and what elimination costsThe baseline was the interchanges
Small pivots along grid rows gave a fixed fill-reducing plan twice the saving over the natural order that scattered ones did, for a factor of the same size, and the reading was that the natural order did badly on rows. Turning the lines to run along columns was predicted to bring the natural order below 1,000 entries, leave the plan within 3 per cent of 907, and drop the saving to the scatter's. It misses on all three: 1,008, 977 and 3.1 per cent. What the natural order paid for on rows was its own interchanges. Offered by position, as a dense code offers it, every Bunch–Kaufman interchange moves a row out of sequence, and on rows that costs 125 entries at three in ten and 191 at half — the most of any layout at every share. Kept to the grid's index, the natural order barely notices the layout, and the row lines' saving halves to 9.0 per cent.
Exact arithmetic, and what it costs insteadEach column divides by the prime
Square random 0/1 matrices are almost always invertible over the rationals and invertible modulo a small prime only at that field's uniform law — so at twenty rows, 72% of the rationally invertible ones are singular modulo two. A few extra columns were predicted to remove most of that field-dependence modulo three and five. They remove it modulo every prime, at the rate the law for uniformly random matrices states: each extra column divides the share that falls short by about the prime. Four columns take the loss modulo two from 72% to 6.5% and modulo three from 45% to under 1%. The leading square block, meanwhile, keeps its square-matrix odds exactly — a rectangular matrix's rank is decided by all its maximal minors together, and only their greatest common divisor has to be prime to p.
Neither sparse nor denseA line at the real kernel's slope
The rank of an oscillatory block between two equal segments grew like the square root of the Fresnel number up to F = 16, and was predicted to turn into a straight line past F ≈ 30 with a slope near two — one wave for each of the two directions a real kernel travels in. It is a straight line, from F ≈ 16 on, but its slope is 1.47, not two. Two directions would count twice the waves one does; but the incoming wave's band of directions is the outgoing one's reflection, the two overlap in the middle of the block, and the area of their union is 1.40 F. What lies above that line grows like a logarithm, and at small F it is the whole rank — which is all the square-root law ever was.
Reduction, and what a model is forThe edge sits where the cells meet the flow
On a convection–diffusion mesh graded towards its outflow, the nodal numerical range reaches into the right half plane, and Galerkin reduced models fail. The account was that the edge lives in the cells where diffusion and convection are comparable, and drawing the eigenvector that attains it says the account is right: on every operator whose mesh has a cell Péclet number above one, the eigenvector peaks where that number is between a half and one and a quarter, just downstream of where it crosses one, and the outflow layer's five smallest cells hold under four per cent of it. The other question has a short answer too. A one-sided stencil scaled by a cell width is dissipative in nodal coordinates only if its weights do not grow downstream, and a consistent one must grow there: the only dissipative weight is the constant one, which is wrong by up to four units of the derivative.
When the index is a tupleThe penalty walks the same curve
A rank-two fit to a random 2 × 2 × 2 tensor of rank three has no best answer: its error falls towards the tensor's distance to the boundary along a law, d + C/s², while its terms grow without limit. A penalty on the term sizes restores a best answer, and the prediction was that its error at terms three times the tensor's norm would sit within ten per cent of the law's d + C/9 — on the assumption, unproved, that the unbounded fit's path is already the best trade between size and error. On twelve tensors the penalised fit's error at that size is within 1.1 per cent of the law, and every penalised fit with terms past two and a half times the norm lies on the same curve. The assumption holds as far as a penalty can test it. And the penalised fit needs tens of thousands of sweeps to settle where the unbounded fit arrives in at most 144, so the cheap way to a bounded fit is to stop the unbounded one when its error reaches the law's price — not when its terms reach the bound, which on four tensors of twelve happens before the fit has found the boundary at all.
Iterating, instead of factorisingThe 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.
The arithmetic underneathAn octave to land in
A window read off a chain's own rates kept an eight-bit recurrence exact to sixty octaves, and its width, falling towards zero, was predicted to mark where it would stop being exact, to within an octave. It stops two to seven octaves earlier, as soon as the window is narrower than the octave a power-of-two rescale moves by. The rule that aims every step, predicted to outlast it, fails too, once the value it aims at no longer fits. A window computed for each step separately never narrows below 4.8 octaves, reproduces the unbounded exponent on every depth at which the format can still store the chain, and makes the fewest rescales of the three.
The eigenvalue problem that is not linearAn interior root needs its own scaling
A cubic matrix polynomial with three groups of eigenvalues needed only two reductions: the leading one kept the middle group at every separation. A quartic has two interior groups, and the prediction was that the leading reduction would keep both, so that two reductions would still do. At eight decades between groups it keeps neither — both interior groups are wrong in the second digit — and no unscaled route keeps the second group at all. Two reductions still suffice, but each must be scaled at an interior tropical root: the trailing one at the second root for the lower two groups, the leading one at the third for the upper two. And the second companion pencil, predicted to keep the middle groups as the reversed polynomial does, loses them as the first pencil does.
Sparsity, and what elimination costsA clique has no order
Ordering a dissection's pieces with their separator in view cut the critical path by a quarter, and the next proposal was to order the separator's own vertices by how much fill each carries in. On every separator the dissections here produce — the grid's rows, its level-set diagonals, and the level sets of three irregular graphs of 300 vertices — twenty-four shuffles of the separator's order give the same factor to the last entry. The reason is one line of graph theory: once the pieces are eliminated, a separator whose vertices all touch one connected piece is a clique, and a clique's order changes nothing. The order matters only on a separator that is not a clique, and the one built here to be that — two grid rows thick — loses to a separator of one row under every order tried. The separator's size is the decision; its order is not one.
Elimination, and the swapA definite pivot sits at the mean
On a positive-definite matrix every Cholesky pivot is at or above the smallest eigenvalue, so a shift read off the smallest pivot always has to be pushed down, and it was predicted to need a median of four pushes and to be usable unpushed on none. The second half holds on all ninety matrices measured. The first does not: shrinking by a quarter at a time takes a median of six to ten steps, because the smallest pivot sits within a factor of two of the spectrum's harmonic mean, and the harmonic mean sits four to nine times above the smallest eigenvalue. The push was a device for the indefinite case, which has no floor to aim at. A definite matrix does, and halving towards zero gets below the spectrum in a median of two to four.
Reduction, and what a model is forA weight is not a location
On a mesh graded towards a convection–diffusion operator's outflow, the edge of the numerical range in nodal coordinates lives in the cells where diffusion and convection are comparable, and weighting the inner product by cell size everywhere moves it into the left half plane. The prediction was that the weight is only needed where the edge lives: cell sizes over the nodes whose cell Péclet number is between a quarter and two, and one elsewhere, would make the range dissipative at every grading and repair every failed model. It does the opposite. From a grading of ten the band-only weight's edge is positive, and from thirty it is further right than the nodal edge it was meant to repair — 144 against 8.9 at Péclet 100. Its edge eigenvector leaves the transition and sits at the weight's own step, where it rises from 0.16 to 1; and its models fail on thirteen placements to the nodal twenty-three. The cell sizes work because they are the one diagonal weight that makes the centred convection stencil skew, row by row, and any other — stepped, ramped over half the mesh, or the reverse — leaves a symmetric part where it departs.
Regularisation, and the answer that is chosenThe search finds a join, not the join
A smooth arch joined to a staircase is reconstructed 10 to 31 per cent better by a pair of penalties split at the join — the second difference before it, the first after — than by any uniform mixture, when the join is at three quarters and the penalty is told where it is. A search that tries every join and keeps the one generalised cross-validation likes best was predicted to find it within two grid points on every draw and keep two thirds of the gain. Left to itself, GCV collapses on three draws of twenty-four, choosing a first-difference strength of 10⁻⁴ and twenty times the error. With both strengths floored at a thousandth it finds the join within two points on seven draws of eight — and keeps a third of the gain, because the strengths it picks are not the error's. And where the join was at a quarter, so that splitting there buys nothing, it puts the join past the staircase's last step instead, and that split beats the best uniform pair by up to fifteen per cent: a structure nobody had told it about.
Neither sparse nor denseSeparated, and narrower
The cos(κr)/r block between two facing segments has a rank that turns linear in the Fresnel number with a slope near 1.4, not the 1.9 of a real kernel's two directions, because the band of directions the source is seen over overlaps its own reflection through zero. Shift the source along its line until the target sees it entirely to one side, and the bands were predicted to separate and the slope to rise to 1.9, the change happening near half a segment's length. The bands do separate: from an offset of one length the union is exactly twice the band. But the band has narrowed by the same factor, because the source is now seen obliquely, and the separated union is no wider than the overlapping one was. The rank's slope is 1.58 at one length, 1.67 at its steepest between a half and three quarters, and 0.92 at two lengths. At every offset it runs 0.1 to 0.2 above the union's slope: the phase-space count tracks it, and the count was never going to double.
Eigenvalues, singular values, rankAn eigenvalue that arrives twice
A matrix with forty distinct eigenvalues, handed to Lanczos for eighty steps, returns twenty-five extra copies of thirteen of them — the largest arriving five times. Every copy is accurate to 1.9·10⁻⁸ relative. No arithmetic error was made, nothing overflowed, and a caller counting eigenvalues gets the wrong multiplicity from a computation in which no individual number is wrong.
Iterating, instead of factorisingThe residual the method reports
Conjugate gradients prints a relative residual of 6.9·10⁻²¹. The unit roundoff is 1.1·10⁻¹⁶, so that is not a small residual and not a large one — it is not a residual. The vector the method is holding at that step has ‖b − Ax‖/‖b‖ = 5.1·10⁻¹⁰, and nothing in the run says so.
Elimination, and the swapA vertex, not an order
A definite matrix's smallest Cholesky pivot sits at the harmonic mean of its spectrum, and the prediction was that a localised bottom would change that for the pivoted factorisation alone: on a path with one weak edge, taking the largest diagonal first would land within a factor of 1.2 of the smallest eigenvalue while the unpivoted pivot stayed at the mean. On the prediction's own family neither rule comes within a factor of three, because a weak edge does not localise the bottom on a vertex — it splits it over the shorter piece, and the best pivot any order can reach is the smallest eigenvalue times that piece's length. Where the bottom really does sit on one vertex, both rules land within two per cent, the unpivoted one wherever in the order that vertex happens to fall. The pivot counts the vertices the bottom lives on; the order chooses nothing.
Exact arithmetic, and what it costs insteadA graph is alternating modulo two
Random 0/1 matrices are invertible modulo two at the uniform law's rate, 0.289, and a random graph's adjacency matrix was predicted to follow the symmetric law instead, about 0.42. At twenty vertices it does: 0.409 of 3,000 graphs. At twenty-one it is zero, and at every odd order from nine to twenty-one, on every graph. An adjacency matrix has a zero diagonal, so modulo two it is alternating, its rank is even, and its determinant is the parity of the graph's perfect matchings — of which a graph with an odd number of vertices has none. The law it follows is the alternating one, which the symmetric law matches only at even order; put a coin on the diagonal and the symmetric law returns at every order. Modulo three and five, where a zero diagonal is only a constraint, graphs reach the symmetric law from below by sixteen vertices, as predicted.
The eigenvalue problem that is not linearThe middle root has no neighbour to lean on
A quartic matrix polynomial's four groups of eigenvalues, up to eight decades apart, were all kept by two scaled reductions of its companion pencil — the trailing one at the second tropical root for the lower pair, the leading one at the third for the upper pair. For a quintic the same pair was predicted to keep the middle group as well up to six decades, and to fail at eight, making the quintic the first polynomial that needs three. The pair keeps the four outer groups to six decades on both families, as predicted, and never keeps the middle group at all — not at eight decades, six, four or even two. Scaled at the middle root, both end coefficients shrink together, as 10 to the minus three times the separation, so every reduction that inverts one end of the pencil is far from the middle. Where the middle group is kept, it is by a reduction centred on it: on the structured family the leading reduction at the third root keeps it at every separation, and with the scaled trailing one that makes two routes again — not the predicted two. On the generic family none of thirteen routes keeps it at four or six decades.
Sparsity, and what elimination costsThe spare vertices lean one way
Every separator a dissection drew on grids and sparse geometric graphs was a clique once its pieces were eliminated, so the order inside it changed nothing; only a separator two rows thick, built by hand, was not. On geometric graphs at twice the density, level-set separators were predicted to come out several vertices thick where the level crosses a dense patch, with vertices touching only one side — failing the clique condition, making their order matter by more than five per cent, and paying more for trimming than for any order. On twenty-four graphs at three densities the spare vertices are there: up to thirteen in one separator. Not one separator fails the clique condition, because on every graph the spare vertices all touch the same piece, and two vertices that share a piece are joined through it. No shuffle of any separator moves the fill or the work by a single entry. Trimming the spare vertices into the piece they touch shortens the critical path by up to 48 per cent — and denser graphs have fewer of them, not more.
The arithmetic underneathTwice the block, half the depth
An eight-bit chain kept exact by a window per step was predicted to keep exactness with one exponent shared by two states, and to lose it with four from the depth where four of its steepest steps span more than the narrowest window, 4.8 octaves. Blocks of two fail on four chains of five, at 66 to 114 octaves. Blocks of four fail at 35 to 66, two to three times deeper than the predicted 13 to 26. Every block size fails within three octaves of the depth where its block's window empties, and that depth is 4.0 to 4.6 octaves for each state a block holds.
Eigenvalues, singular values, rankA good curve and a bad verdict
The diagonal of a column-pivoted R is famous for the one matrix it is wrong about. On that matrix it is right about thirty-nine of its forty entries — every |rₖₖ| within a factor of six of the σₖ it stands for — and wrong by 4·10⁶ at the fortieth, which is the only one a rank verdict ever reads.