Storage growth — the series
-
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.
-
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 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.
-
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.
-
A class is no longer one matrix
On a uniform grid every off-diagonal block of one width and one offset is the same matrix, so a probe that compresses one block of each class reads the whole partition's ranks and names a hierarchical matrix's cheapest leaf. On scattered points that stops being true, and the prediction was that the ranks inside a class would spread by at most one, that three blocks a class would still name the leaf everywhere, and that the probe would fail first at the highest frequency. The ranks spread by up to four. Three blocks a class still name the cheapest leaf on all thirty cells of two draws — so does one — and nothing fails at the highest frequency. The decision survives because no mean the rule compares sits close to its threshold, and scattering moved no cheapest leaf at all.