Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Admissibility — where it appears

The test deciding whether a pair of index clusters may have the matrix block between them stored as two thin factors. It compares the sum of the clusters' radii to the distance between their centres, so it is four numbers per pair and reads no entry of the matrix at all.

Named by 21 essays across 3 fields — each of them below, with the objects they name alongside it.

0369121501122334455digits asked for, −log₁₀ εcolumns keptwhat the geometry promiseswhat the matrix costsa rank is a number of digitscolumns a decade0.55bound, a decade3.3rank at 10⁻⁸5bound at 10⁻⁸28q0.5the shape is rightand the constant is not

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.

hierarchy · Off-diagonal rank 45678903691215log₂ of the points a sidecolumns above 10⁻⁸two intervals that touchtwo that do notthe measurement that is a null resultadmissible, n = 325admissible, n = 2565touching, n = 329touching, n = 25613stored ⁄ dense at largest0.039the rank belongs to the geometryand not to the sampling

The size the rank does not notice

Sample a kernel block at 32, 64, 128 and 256 points a side and it needs five columns, five, five and five. Sample the touching block next to it at the same four sizes and it needs nine, eleven, twelve and thirteen. Same kernel, same accuracy, one number and a logarithm.

hierarchy · Off-diagonal rank -1012301020304050log₂ of the segment lengthcolumns above 10⁻⁸cos(κr) ⁄ r at κ = 401 ⁄ r, same pointsthe case with no answerq, held fixed0.51/r at L = 0.561/r at L = 86cos(κr)/r at L = 0.512cos(κr)/r at L = 853the geometry did not moveand the rank did

The kernel with nothing to compress

Hold the geometry fixed at q = ½, fix the wavelength, and scale the picture up by sixteen. A smooth kernel needs six columns at every scale. An oscillatory one needs twelve, sixteen, twenty-two, thirty-three, fifty-three, and there is no scale at which it stops.

hierarchy · Off-diagonal rank 545545545455554545545545545454555555454545545545545455554545545545rows and columns, in the order the points arrivedark: kept dense · light: two thin factors, rank printedthe strong partitionblocks112kept dense46largest rank5numbers stored2.7·10⁴relative compression error3.4·10⁻¹⁰the picture is decidedbefore a number is read

Which pairs are allowed to be small

A hierarchical representation is a partition of the matrix into blocks, and the rule that produces it reads four numbers per pair of index clusters and not one entry of the matrix. On a 256-square it yields 112 blocks, 66 of them stored as two thin factors, none of rank above five.

hierarchy · Admissibility 567891003691215log₂ nlargest rank in the partitionweak: touching pairs compressedstrong: touching pairs refusedthe test bounds a rank and costs storagestrong, blocks250weak, blocks94strong, numbers6.8·10⁴weak, numbers6.1·10⁴strong ⁄ weak1.1the better partitionis the more expensive one

The test that costs what it saves

The partition that refuses to compress a touching pair keeps every rank at five while the other lets them climb from nine to thirteen. It also stores more numbers at every size measured — 67,968 against 61,440 at n = 512 — and which of those two facts matters is a question about how large the problem is going to get.

hierarchy · Admissibility numbers stored, 256 × 256clustered, strong27,008clustered, weak24,064the dense matrix65,536shuffled, strong65,536shuffled, weak118,208the same matrix, twiceκ, clustered24κ, shuffled24Frobenius norm, clustered6140Frobenius norm, shuffled6140shuffled weak ⁄ dense1.8the compressibility is in the numberingand the numbering is not in the matrix

The same matrix, numbered twice

One symmetric permutation. The condition number is 24.3948 either way to eight digits and the Frobenius norm is 6.13996414·10³ either way to twelve. The partition that stored 27,008 numbers now finds no admissible pair anywhere and stores all 65,536, and the format that compresses regardless stores 118,208.

hierarchy · Admissibility 567891010¹10²10³10⁴10⁵10⁶log₂ nnumbers the construction touchedentries, n²products with the operatoran operator, applied a few hundred timesproducts at n = 512256entries at n = 5122.6·10⁵per doubling48relative compression error4·10⁻⁷excess over the compression7.3no entry of the matrixwas ever read

Built from products alone

A 512-square hierarchical representation, at a relative error of 4·10⁻⁷, from 256 applications of an operator that is never assembled. The compression route reads 262,144 entries; this one reads none, and pays for it with a factor of seven against the representation the entries would have given.

randomised · Sketching 10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²ε the blocks were compressed at‖A − LLᵀ‖ ⁄ ‖A‖the factorisationthe knob, on a factorisationtruncations34residual at 10⁻⁴2.2·10⁻⁵residual at 10⁻¹⁰9.9·10⁻¹²slope1worst ratio to the representation1.8ten decadesand a slope of one

A knob calibrated in residuals

A formatted Cholesky has two numbers in it and only one of them is an accuracy. Across twelve trees — three sizes by four leaf sizes — the leaf moves the truncation count from 0 to 258 and moves the ranks of the blocks not at all, while the residual follows the tolerance at slopes between 1.022 and 1.046 and sits at about a tenth of it throughout.

hierarchy · Recompression 02040608010010⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸truncations performed by the factorisationrelative errorthe representation's own error‖A − LLᵀ‖ ⁄ ‖A‖no decomposition without its residualresidual, 0 truncations2.1·10⁻¹⁰residual, 98 truncations1.1·10⁻⁹representation, deepest1.4·10⁻⁹residual ⁄ representation0.81levels, deepest5a hundred approximate stepsand an exact-looking factorisation

The count that is not the budget

A Cholesky performed inside a low-rank format truncates 0, 2, 10, 34 and 98 times as the leaf falls from 128 to 8, and those five integers are the same at every accuracy from 10⁻¹² to 10⁻². Across all ten decades the factorisation's residual stays below the representation's own error at a ratio between 0.81 and 1.00 — with two entries that read 1.83 and 1.78, and neither of them is accumulation.

hierarchy · Recompression 10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³relative compression error, the representation‖b − Ax‖ ⁄ ‖A‖‖x‖, the solveequala backward error, chosenslope0.99representation at 10⁻⁸1.2·10⁻⁹backward error there1.3·10⁻¹⁰representation at 10⁻¹²1.2·10⁻¹³backward error there2.5·10⁻¹⁴the compression is not an approximationit is a perturbation of the problem

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.

error · Backward error 10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹relative compression error, chosen‖x − x*‖ ⁄ ‖x*‖κ × the chosen backward errorthe error in the answerboth factors known firstκ21chosen at 10⁻⁸1.4·10⁻⁹predicted forward2.9·10⁻⁸measured forward1.6·10⁻⁹bound ⁄ measured26the amplifier, used forwardsfor once

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.

hierarchy · Hierarchical solve 56789100108216324432log₂ nstored per unknowndenseweak: every off-diagonal blockstrong: only the admissible onesa constant per doublingstrong, n = 5126.8·10⁴weak, n = 5126.1·10⁴dense, n = 5122.6·10⁵per doubling26relative compression error3.8·10⁻¹⁰the dense line doublesand the other two add a constant

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.

hierarchy · Storage growth six tolerancesblocks, every tolerance250slope per unit of rank5.1worst residual3.6·10⁻¹⁵234567010203040mean rank of the low-rank blocksnumbers per doubling2 digits4 digits6 digits8 digits10 digits12 digitsthe partition is the same at every toleranceand the rank rises one per two decades

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.

hierarchy · Storage growth n = 512, ε = 10⁻⁸least storage, at leaf16numbers per unknown there133at the largest leaf211050100150200leaf sizestored per unknown48163264stored per unknownshare in the dense blockslarge dot: the least storage availableand the dashed curve is why there is one

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.

hierarchy · Storage growth n = 512, leaf 16blocks, tightest to loosest592and at the loosest94mean rank, tightest3.3and at the loosest8.9052104156208260the separation constantstored per unknown0.20.30.40.50.951.4stored per unknownmean rank, compressed blocksboth curves move togetherwhich is what the other two knobs never do

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.

hierarchy · Storage growth n = 512, ε = 10⁻⁸1/r, least at leaf16log r, least at leaf8cos(40r)/r, least at leaf16cos(120r)/r, least at leaf1604794141188235leaf sizestored per unknown481632641/rlog rcos(40r)/rcos(120r)/rthe rank doubles and the optimum does not movewhich the next figure explains

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.

hierarchy · Storage growth k < s/4cells agreeing28cells3010⁻³10⁻²10⁻¹11distance from the threshold, relativepredicted leaf ÷ bestred: the rule's two missesboth within three per cent of the break-even

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.

hierarchy · Storage growth source segment length btarget length a⅛¼½124⅛¼½1247889888991011108912131313910131618188111318222681013182633columns at 10⁻⁸square block, side 433⅛ against 48square block, side ⅛7κ = 40, separation ratio ½ throughoutthe smaller side sets the rank

The smaller cluster sets the rank

An oscillatory kernel block between two equal clusters needs a rank that grows without limit as they grow. Make the clusters unequal at the same separation ratio and the rank stops following the larger one: a target an eighth long against a source of four needs 8 columns where the square block of side four needs 33, and a target a third long against a source 130 wavelengths long needs 11. What decides the rank is the product of the two lengths over their distance — the Fresnel number, the count optics gives for the waves two apertures can exchange.

hierarchy · Off-diagonal rank cells named right, of thirtyone rank per two decades23the same, doubled for an oscillation18one build at a leaf of 829the rule, every leaf built28thumbdoubledprobefull rule1/r, 1e−4 · best 81/r, 1e−6 · best 81/r, 1e−8 · best 161/r, 1e−10 · best 161/r, 1e−12 · best 16log r, 1e−4 · best 8log r, 1e−6 · best 8log r, 1e−8 · best 8log r, 1e−10 · best 16log r, 1e−12 · best 16cos(40r)/r, 1e−4 · best 816cos(40r)/r, 1e−6 · best 8cos(40r)/r, 1e−8 · best 1632cos(40r)/r, 1e−10 · best 1632cos(40r)/r, 1e−12 · best 1632cos(120r)/r, 1e−4 · best 8161616cos(120r)/r, 1e−6 · best 168cos(120r)/r, 1e−8 · best 1632cos(120r)/r, 1e−10 · best 163232cos(120r)/r, 1e−12 · best 3216√r, 1e−4 · best 8√r, 1e−6 · best 8√r, 1e−8 · best 8√r, 1e−10 · best 16√r, 1e−12 · best 16e^(−5r), 1e−4 · best 488e^(−5r), 1e−6 · best 488e^(−5r), 1e−8 · best 41616e^(−5r), 1e−10 · best 41616e^(−5r), 1e−12 · best 41616dot: the best leaf named · number: the leaf named insteadone build reads what the kernel hides

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.

hierarchy · Storage growth 00.511.52ranks added by one triplingκ from 13⅓ to 400.28κ from 40 to 1200.95κ from 120 to 3601.39κ from 360 to 10800.38dot: mean over tolerances · bar: rangeno fixed step

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.

hierarchy · Storage growth of 5 cellscheapest 32, 16-wide ≥ 85cheapest 32, 8-wide ≥ 82234567891011121323456789mean rank of the 16-wide blocksmean rank of the 8-wide blockshalving 32 → 16 does not paythe most an 8-wide block holdscheapest leaf 32cheapest 8 or 16the decision is a column, not a rowthe 16-wide blocks carry it

Each halving reads its own width

A hierarchical matrix's cheapest leaf is found by halving it while the blocks the halving creates have rank below a quarter of the leaf. The proposal was to probe only the near blocks of one compression at a leaf of 8, predicted to do at least as well as the whole compression. It does worse: twelve cells of fifteen against thirteen, every miss naming 16 where 32 is cheapest, because the decision between 32 and 16 turns on whether a block reaches rank 8 and an 8-wide block cannot exceed it. Read each halving off the blocks of its own width instead and the probe names the cheapest leaf on all fifteen oscillatory cells and all thirty cells of six kernels, beating even the rule with every leaf compressed, from eighteen small blocks at under one per cent of the work of the compression it replaces.

hierarchy · Storage growth

Named alongside it

The objects these essays reach for when they reach for this one.

Hierarchical matrixOff-diagonal rankNumerical rankLow-rank approximationToleranceCluster treeKernel matrixStorageAsymptotic analysisTruncationBackward errorWeak admissibility

All concepts