Optimal-complexity — where it appears
Named by 6 essays across 3 fields — each of them below, with the objects they name alongside it.
Where the format starts paying
A hierarchical solve costs 1.48 times a dense factorisation at 64 unknowns and 0.16 times it at 512. The crossover is between 64 and 128, it walks right when the accuracy is tightened, and the exponent between consecutive sizes is 2.13, 1.93, 1.74 — falling towards one and never arriving.
A rate that does not notice the size
The V-cycle reduces the residual by a factor of ten a cycle at fifteen points and at a hundred and twenty-seven. Jacobi on the same four problems goes from 0.981 to 0.9978, climbing towards one. One of those is a constant and the other is an exponent, and that is the whole distinction the field turns on.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Hierarchical matrixAsymptotic analysisCluster treeLow-rank approximationNumerical rankToleranceAdmissibilityOff-diagonal rankTruncationBackward errorFlop countStorage