The thread: Exact ground truth — page 6
The halves were the price
One level of nested dissection followed by minimum degree was worse than both no dissection and full dissection on a grid, and the explanation offered was the separator's dense block sitting on every path. That predicted a sign: a separator found from the graph, rather than read off the coordinates, should make the penalty larger. It makes it smaller at every size — 44,116 against 53,508 at 24×24 — and the separator is not where the difference is: both first separators have 24 vertices and cost exactly 4,900. What differs is the path through the halves. Minimum degree takes 48,608 through a rectangular half of the 24×24 grid, longer than its 41,072 through the whole grid, and 39,216 through a triangular one.
Eigenvalues, singular values, rankThe series that has to be squared back
The Taylor series for the matrix exponential is not wrong — every term is computed correctly — and on Moler and Van Loan's two-by-two its largest term is 5.4 million times the answer it sums to. The method that replaces it scales the matrix down and squares the result back, and both halves of that sentence cost: too few squarings and the approximant is out of range, too many and each one doubles the rounding.
Least squares, and the road not to takeA multiplier is a force
A third constraint nearly parallel to the first made the multipliers of a constrained fit rise in exact proportion to κ(B), which looked like the conditioning measured a second, dearer way. It was not. Give the third constraint a datum that asks for nothing new and, at the same κ(B) = 4.6·10¹², the multipliers are eighteen thousand times smaller; give it a strain δ and they are 0.0133 δ/ε², a force on a lever of length ε. What they measure is what the constraint asks. What they do not measure is the error of the best route, which sits at the same level whether the constraint asks for nothing or for a displacement of 3·10⁹.
Methods that were designed apartA tail from Tikhonov and a corner from truncation
Below half the answer, conjugate gradients beat Tikhonov at a matched count of directions by up to 69 per cent, and the proposed measurement was the sharpness p of a roll-off between Tikhonov and truncation that matches the iteration there. Any p from 2 to 4 closes the gap to a tenth; truncation, the family's limit, reopens it to a third. But no p describes the iteration. Its filter has Tikhonov's slope exactly in its tail and a local sharpness of 2 to 5 on its shoulder, and a single fitted p is a compromise that drifts from 2.3 at the first step to 1.7 at the answer.
The matrix a constraint makesAn augmentation read in the smallest eigenvalue
An augmented Lagrangian preconditioner's least work sat at γ = 1, 10⁴ and 1 on three systems, and two of the three optima sat where the smallest generalised eigenvalue was about 0.06 — which suggested a rule written in ν rather than γ. On twenty-four systems whose norms are all one, the least-work γ spans seven decades and ν at the optimum spans a factor of thirty, so there is no one ν. There is still a rule: take the smallest γ at which ν reaches 0.03, and the median system pays 7 per cent over its least work and the worst 29, where the best single γ pays 61. Its price is digits — twelve times the best forward error on the median system, 4,561 times on the worst.
Structure, and the solver that cannot see itThe staircase a separable kernel builds
A block-circulant preconditioner took 18, 21, 22, 21, 19 and 18 steps on a 10 × 10 Toeplitz-block-Toeplitz system as the correlation rose from 0.5 to 0.98 and the unpreconditioned count rose from 43 to 178 — the parameter that makes the problem hard was the one the solver did not notice. That kernel factorises. The isotropic kernel with the same correlation along each axis does not, and on it the preconditioned count climbs 17, 22, 27, 29, 33, 36, while the preconditioner buys a factor of 1.4 where it bought ten. The reason is the spectrum's shape: a product of two one-dimensional spectra is a staircase of ten treads, and a kernel that is not a product gives a ramp of thirty-eight.
Reduction, and what a model is forA mode that rings is counted twice
Balanced truncation's bound, twice the sum of the discarded Hankel singular values, was attained at every order on the heat model — a formula for the error rather than a bound on it. On six lightly damped oscillators it is loose at every order but the last, by factors between 1.3 and 5, at every damping from 0.7 to 0.01. The reason is visible in the singular values: a mode that rings contributes two of them, nearly equal, and removing the mode costs about what removing one would. The last mode's bound over its error is 2.02, 2.00 as the damping falls to 0.03 and 0.01. The equality was a property of modes with one singular value each.
Regularisation, and the answer that is chosenMore samples take the floor and leave the dip
GCV's catastrophic misses on fine grids were blamed on squareness: on an n × n system the residual and n − t both reach zero as λ does, and their ratio can dip there. With more samples than unknowns neither reaches zero, and the prediction was that the dip would be gone by construction. Half of it is. The minimum at the floor of the scale, 21 draws in 240 on square systems, is gone at every ratio. The interior dip is not — 28, 20, 13, 8 and 4 draws at one to four samples per unknown — and at four per unknown one draw still misses the oracle by 877 times.
Exact arithmetic, and what it costs insteadThe digits between the two searches
A lattice relation search run at N digits and again at N/10 never agrees with itself on a relation among the rounding, but it does agree on 62 approximate relations at fifteen digits or fewer — accidents that really are the shortest vector there, and that dropping a digit was said to be unable to dislodge, since a combination that cancels to D digits cancels to D − 1. It cancels, but it stops being the shortest. Two digits apart the accepted accidents fall to 17 and three digits apart to 5, while the relations kept fall from 711 of 755 to 652 and 602 — every one of the losses at fifteen digits or fewer. Past a double's sixteen digits the separation costs nothing and buys nothing.
When the index is a tupleThe rank that stops being typical
A random 2 × 2 × 2 tensor has rank two with probability π/4 and rank three otherwise, and the sentence has no analogue for matrices. It is the first of a family. An n × n × 2 tensor is a pencil of two slices, and it has rank n exactly when the pencil's eigenvalues are all real, n + 1 otherwise. Over draws, the share of rank n is 0.786 at n = 2, 0.500 at 3, 0.264 at 4, 0.039 at 6, 0.004 at 8 and none of 4,000 at 10 — falling like e^(−0.087n²) — because the mean number of real eigenvalues grows only like the square root of n, to Edelman, Kostlan and Shub's closed form within two per cent. Both ranks stay typical in theory; in practice the lower one disappears.
Orthogonality, measuredThe residual the appended block cannot remove
Appending b as one more block made block modified Gram–Schmidt solve least squares as well as Householder, ten million times better than the same Q through Qᵀb at κ = 10⁸ — on problems with no residual. Give b a component outside the range and every stable route's error rises with it, while Qᵀb's, already at κ²u, does not move. The appended block's advantage then falls as one over the residual: 5,400 at a relative residual of 10⁻⁴, 54 at a per cent, none at one. It never falls behind Householder by more than a factor of four. What the residual decides is whether the extra block is worth its synchronisations, and the answer is yes up to a residual of about a per cent.
Exact arithmetic, and what it costs insteadWhat reading the next pivot buys
In a fraction-free elimination every pivot is paid for twice — it multiplies every entry of its own step and divides every entry of the next — and the rule that picks the smallest pivot entry left a median 20 per cent above the least arithmetic any row order reaches. A rule that charges two steps ahead brings the median matrix to within 2.5 per cent, and on one matrix of twenty-four costs 1.87 times the least, worse than the smallest pivot ever does. Charging three steps ahead finds the least of all 40,320 orders on thirteen matrices and is never more than 27 per cent above it. And none of it pays: choosing that way costs forty to two hundred and sixty times the elimination it chooses.
Iterating, instead of factorisingExact along one axis
The tuned diffusion makes the answer exact at every node, and in two dimensions it holds at exactly one flow angle. Five degrees off the grid the relative error goes from 1.2·10⁻¹⁴ to 6.9, and by twenty degrees the scheme is worse than the upwinding it was built to improve on.
Eigenvalues, singular values, rankThe vector was what was wanted
Nobody who computes a matrix exponential wants the matrix. They want eᴬᵗb — one vector, the state of a system at a later time. Twenty matrix–vector products get it to sixteen digits on a hundred-by-hundred problem, without ever forming a hundred-by-hundred exponential, and the exponential that does get computed is twenty by twenty.
The eigenvalue problem that is not linearWhere a contour's budget should go
A contour method's ceiling is the number of probes times the number of moments, and the moments are free in solves while the probes are not. Four ways of reaching one ceiling come out four orders apart, the ordering is not monotone, and what separates the best two is not the usual draw but the unlucky one.
When the problem arrives againThe step the two rows owe
A sliding least-squares window can start each step's correction from a fresh solve or from the answer it already has. The answer it has is three orders worse on noisy data, because the exact answer moves by most of itself in a step. The proposal was a start that moves too: the previous answer plus the change the entering and leaving rows imply, two triangular solves from the factor the window keeps. Its start lands exactly where one correction of the carried answer lands — the update is that correction, computed from two rows instead of twenty-four — and one correction after it ends 2.9 to 440 times below the fresh start at κ(A) = 3·10⁶, and level with the carried answer when the data agree exactly.
Two errors, and whose fault they areBalanced is not symmetric
The Sylvester–Kac matrix is made of small integers, so a double holds it exactly, and its eigenvalues are the integers from −(n − 1) to n − 1 in steps of two. Every digit an eigensolver loses on it is therefore the solver's own, and it loses them at exactly the rate first-order perturbation theory predicts: the median error is half the prediction across 1,568 eigenvalues. Balancing, the preprocessing libraries apply for this kind of matrix, divides every condition number by about sixty and leaves their growth untouched, and at order 112 the unbalanced solver returns eighteen complex eigenvalues for a spectrum of integers.
The matrix that is a graphA finer invariant that hears less
The Laplacian spectrum fixes a graph's number of spanning trees and not the group those trees form, so the Smith normal form of the grounded Laplacian is a strictly finer integer invariant — and on the six-vertex pair the spectrum cannot separate, it does: ℤ₁₂ against ℤ₂ ⊕ ℤ₆. Over all 1,022 Laplacian-cospectral pairs of connected graphs on eight vertices it separates 435. The adjacency polynomial, a second spectrum rather than a finer one, separates all of them.
Exact arithmetic, and what it costs insteadThe field decides it, usually
A matrix whose rank depends on the field it is read over was built, the first time, from its invariant factors outward, because random integer matrices never seemed to show the effect. Random 0/1 matrices show it at almost every size that is not tiny. At twenty rows, 99.8% of them are invertible over the rationals, 29% modulo two, 56% modulo three — and 71% of the ones the rationals call invertible are singular modulo two. Modulo two they obey, corank by corank, the law for uniformly random matrices over that field; modulo three and five, which their entries cannot fill, they converge to that field's law anyway.
Where the flop count stopped predicting the timeThe circle between two eigenvalues
A contour count's error is not approximately governed by the nearest eigenvalue; it is exactly one closed-form term per eigenvalue, and summing those terms reproduces the quadrature to a millionth at 1,720 radius and point pairs. Three things follow. The rate is the ratio of the two moduli the circle sits between, not a distance, so two circles 0.2 from their nearest eigenvalue converge three times apart. Ten digits cost about 21 points divided by log₁₀ of that ratio, 71 points with twelve eigenvalues inside and 3,476 with six. And the best circle is not halfway: at the geometric mean of two eigenvalues on one ray their two terms are equal and opposite, and ten digits cost 27 points where the midpoint needs 84.
The matrix that is a graphEach spectrum hears the other's pairs
Pairs of graphs with the same Laplacian spectrum share a spanning-tree count, so the critical group could only tell them apart by how that count factors — and did on two pairs in five. Turn the census round, to the 733 pairs of eight-vertex graphs with the same adjacency spectrum, and the tree count is free to differ. It does on 717 of them, by a median of six per cent. The critical group separates exactly those 717 and not one more: on all sixteen pairs whose counts agree, including a non-cyclic one, the two graphs have the same group. And the Laplacian spectrum separates all 733, as the adjacency spectrum separated every Laplacian pair.
Least squares, and the road not to takeThe scale that only moved a pivot
Multiply the constraint rows of a saddle-point system until its multipliers are the size of its solution, and the extra error the route was blamed for — 4.6·10⁻⁴ against the null-space route's 1.8·10⁻⁸ — falls to 3.3·10⁻⁸. The prediction holds and its reason does not. A scale of ten does what a scale of 6·10⁵ does; hold the elimination's row order fixed and nine decades of scale move the error by less than a factor of five. What the scale changed was which row partial pivoting took at the second step, and taking the constraint rows first does the same job with no scale at all.
Orthogonality, measuredThe worst residual belongs to the route
Every stable least-squares route's error rises with the residual at about a fiftieth of the bound κ²uρ, and the question left open was whether a residual aimed at the weak directions closes the gap. It can be aimed exactly: the map from residual to error is, on these problems, one direction and rounding. Aimed, Householder's constant rises from a median of 0.014 to 0.11 — √(m − n) = 6.9 times a typical direction, at 32, 64 and 128 rows to three figures — and stops a factor of nine short of the bound. The direction is each route's own: aimed at one, another route draws a fifth of its worst. And aimed at the appended block, the one-per-cent rule that made it worth its extra block falls to half a per cent, with the block twelve times behind Householder on the same data.
When the problem arrives againA target the residual can promise
A caller who wants inexact Newton's answer to six digits usually passes 10⁻⁶ as the residual tolerance, and on five problems at four targets that misses by 7 to 35,000 times. Divide the target by a condition number and it is met on every cell where a residual can certify it — and the condition number need not be known: the Ritz values conjugate gradients produces on the way give the Jacobian's own, settled by the sixth Newton step and within eleven per cent of the truth at the end, and two to nineteen times below the linear part's. Stopped that way, with the usual floor under the forcing term, the run lands within a fifth of its target and is cheaper on 16 of 19 cells than the unfloored run stopped by someone who knows the answer.