Tolerance — where it appears
Named by 23 essays across 6 fields — each of them below, with the objects they name alongside it.
A rank that is a number of digits
Ask a kernel block for two digits and it costs two columns; ask for fourteen and it costs nine. The curve is a straight line at 0.55 columns a decade, and the bound the geometry gives is a straight line too — at 3.32, which is the same shape and six times the price.
Rank is a decision
A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap.
The accuracy worth paying for
Used as a preconditioner, a hierarchical representation gets better at every accuracy — the iteration count falls monotonically all the way to the tightest tolerance. The total work does not. Its minimum sits at a rank-one preconditioner on an easy problem and six decades further along on a hard one.
The zero you are allowed to write
A deflation criterion sets a subdiagonal entry to zero because it is small. A drop tolerance discards an entry of a factor because it is small. A truncation discards a singular value because it is small. Three fields, three vocabularies, no shared arithmetic — and plotted as work saved against error accepted, one curve.
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.
A stopping test is a race
One matrix, one right-hand side, one tolerance, thirteen partition counts — and eleven different iteration counts between 674 and 690. Every run converged, every answer is right to the accuracy asked for, and what differs is the bill.
An accuracy that is a backward error
Every backward error on this site is something an algorithm produced and somebody then measured. This one is a line in the program. Solving with a compressed matrix gives a residual that is the compression's own error, at a slope of 1.000 over ten decades, so the knob that sets the storage sets the backward error directly.
The digit that costs more than the tensor
Ask a three-index reciprocal tensor on six points a side for seven digits and its train is 288 numbers against 216 entries. The break-even rank is n − 1 at all four grids measured, and a train that reaches it fits with exactly n numbers to spare.
The knob that moved two things
Decide how many digits the answer needs, divide by the condition number, and compress to that. It is the one rule licensed in advance here, and its two factors are not the independent inputs it reads as: the partition's leaf moves neither of them and moves the answer by nearly a factor of three, and the only knob here that raises κ halves the ranks while it does so.
The tolerance that buys no agreement
Ask for four more orders of accuracy and you get them — the answers improve by a factor of 1.5 million. The ratio between the best and the worst run is 1.34, 1.48, 1.71 and 1.17 across the same sweep. The band falls and it does not close.
The offset that moved the slope
The accuracy is supposed to lift a storage curve and leave its growth alone. Measured at seven tolerances, the strong partition adds 10.9 numbers per unknown per doubling at two digits and 36.5 at twelve — the growth rate more than triples, so ten decades of accuracy cost 33 per cent more storage at 64 unknowns and 118 per cent at 512.
The partition that does not move
The storage curve's growth rate more than triples between two digits and twelve, and the earlier measurement said so without saying what moves it. There are two candidates and the measurement separates them decisively: the partition is identical at every tolerance — 250 blocks, 156 of them low-rank, 94 dense — and the mean rank rises by exactly one per two decades of accuracy. The slope is 5.11 numbers per unknown per doubling per unit of rank, with a worst residual of 0.03 over six tolerances.
What a regression test can ask for
The machine's own variation on one solve is 3.2·10⁻¹², and the smallest defect whose answers clear it is one part in 10¹². The tolerance exists, it is bracketed on both sides by a factor of 1.42, and it is neither zero nor the 10⁻⁸ that usually gets typed.
A perturbation that moves every coefficient
The backward error of a polynomial eigenpair is measured against perturbations of all three coefficients at once. Restrict it to the one coefficient anybody is willing to move and the same computed answers are stable at one eigenvalue and unstable at another, by a factor that runs from 1.06 to 6,370 across a single spectrum.
Two knobs on one number
The tolerance raises every block's rank and leaves the partition alone. The leaf size does the opposite — it changes how many blocks there are and does not move a single rank. Both act on the same storage, and only one of them has a best setting: at eight digits the least storage is at a leaf of 16 and the largest leaf tried costs 59 per cent more. The best leaf rises with the accuracy, from 4 at two digits to 16 at twelve, and the influence runs only that way.
A second objective that is the first one doubled
Counting the operations a hierarchical product does was supposed to give the leaf size a second optimum, somewhere other than where the storage puts it. The count is 160,128, 139,904, 135,936, 155,136 and 216,064 against stored totals of 80,064, 69,952, 67,968, 77,568 and 108,032 — twice each, at every leaf, exactly. The two objectives cannot disagree, and what separates the leaf that stores least from the leaf that runs fastest is a charge of about 139 operations for reaching a block at all.
A tolerance is priced by the problem
Three tolerances from three fields sit on one pair of axes and agree to within a factor of 5.74. That factor is the ratio of the two curves that cannot move. Change the only problem in the comparison and the third curve's fitted slope swings from 0.188 to 0.040 while the printed spread does not shift by a digit.
A geometry setting that is a second accuracy
The tolerance raises every rank and moves no block; the leaf moves every block and no rank. The constant that decides how far apart two clusters must be before their block may be compressed moves both — 592 blocks at mean rank 3.25 at one end and 94 at mean rank 8.94 at the other — and the storage falls the whole way while the error against the dense matrix rises by a factor of 3.5, at a tolerance that never changed. It has no best setting, and it is not a third knob on the storage.
A prediction that arrives a decade late
A rougher kernel raises every rank, a higher rank raises the side at which compressing a block stops paying, so the leaf that stores least should rise. Across four kernels whose largest rank runs 5, 5, 9 and 10, it is 16 on three of them and a tie between 8 and 16 on the fourth. The prediction is right in sign and out by a decade of tolerance, and the reason is a ceiling: an oscillation multiplies the rank by exactly two — 3 and 6, 4 and 8, 5 and 10, 6 and 12, 7 and 14 — at any frequency, because a cosine of a difference is a rank-two function.
A quarter of the leaf
The leaf that stores a hierarchical matrix most cheaply had been read off a table of nine points, with the suggestion that it depends on the mean rank alone. Across six kernels at five tolerances — thirty cells — it does, once the mean rank is read in the right place. Plotted against the mean rank at a fixed leaf of 16, two cells a tenth of a rank apart want leaves of 8 and 16. Plotted against the rank of the blocks a halving would create, one rule — halve the leaf while that rank is below a quarter of the leaf — predicts the best leaf on 28 of the 30, and the two it misses are the two whose rank sits within three per cent of the threshold. The fractional power the last measurement expected to be rough is smoother than 1/r.
One build tells the leaf
The rule that picks a hierarchical matrix's cheapest leaf — halve it while the rank at half the leaf is below a quarter of the leaf — reads ranks that exist only after the matrix has been built at every candidate leaf. Fed instead the rank a code can guess from the tolerance alone, one rank per two decades, it names the best leaf on twenty-three cells of thirty, and on the rank-one kernel it cannot see it stores up to seventy-two per cent too much. Doubling the guess for an oscillation, as earlier measurements suggested, makes it worse: eighteen of thirty. Building once, at a single leaf, and holding that build's mean rank fixed names the best leaf on twenty-nine — one more than the rule that builds at all five — and never stores three per cent more than the least.
An offset that bends twice
A hierarchical matrix's cheapest leaf can be named by one build at a leaf of 8, and a rank guessed from the tolerance alone names it on smooth kernels and misses on oscillatory ones. The repair proposed was a term in the frequency: the oscillatory kernels sat two thirds of a rank and one and a half ranks above 1/r at frequencies 40 and 120, and the prediction was a fixed step each time the frequency triples. On five frequencies from 13⅓ to 1,080 the step is a third of a rank, then one, then one and a half, then a third again — a curve that bends twice. The last bend is the smallest blocks filling up: at the tightest tolerance every 8-wide block is at full rank from 360 on. No fixed term reproduces it, and the one build that reads it directly still names the cheapest leaf on thirteen cells of fifteen, never storing two per cent too much, where the uncorrected guess misses seven by up to nine.
A 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.
Named alongside it
The objects these essays reach for when they reach for this one.
Numerical rankLow-rank approximationHierarchical matrixAdmissibilityBackward errorOff-diagonal rankCluster treeStorageTruncationCondition numberOptimal-complexityPreconditioning