A second objective that is the first one doubled

Two knobs on one number swept the leaf size of a cluster tree against the storage of the hierarchical matrix built on it, found a least at 16 for eight digits, and closed by naming three things the sweep had not priced. The first of them was time. Storage is what the measurement counted and it is not what anybody optimises; the operations one hierarchical matrix–vector product does are a different sum over the same blocks, and a different sum over the same blocks was expected to have a different least.

The sum is easy to write. A dense block of m rows and k columns costs 2mk — one multiply and one add per entry — and a compressed block of rank r costs 2rk to apply the thin factor on the right and 2rm to apply the one on the left, so 2r(m + k) in all. Add those over the partition and the leaf that minimises the total is the leaf a code that cares about seconds should choose.

Counted at n = 512 and eight digits, the five leaves do 160,128, 139,904, 135,936, 155,136 and 216,064 operations. The same five representations store 80,064, 69,952, 67,968, 77,568 and 108,032 numbers.

Every one of those pairs is a factor of two apart, to the number.

Every number a block holds is read exactly once #

The coincidence is not one, and seeing why takes one line per kind of block.

A dense block stores mk numbers and the product reads each of them once, multiplying it by an entry of the vector and adding the result into an accumulator. Two operations per stored number, mk numbers, 2mk operations.

A compressed block stores the two thin factors, which between them hold r(m + k) numbers. The product reads the right-hand factor once, forming a short vector of length r; then it reads the left-hand factor once, expanding that short vector into the output. Every entry of both factors is touched exactly once, and each time it is touched it is multiplied and added. Two operations per stored number again.

So the identity is not about hierarchical matrices at all. It is about any representation whose product is a single pass over the stored numbers, and a hierarchical matrix–vector product is exactly that: it never forms a block, never revisits one, and never reads a number it did not store. The operation count and the storage are the same measurement in different units, and a unit change cannot move a minimum.

That is worth stating as a general fact rather than as a result of this sweep, because it says which questions about this data structure are answerable by counting and which are not. Anything of the form how much work does the product do is the storage curve. Anything that distinguishes two representations holding the same number of numbers has to be about something other than how many operations they generate — which is the same place a blocked and an unblocked elimination arrived at from the other end of this field, with 72,568 operations apiece and a factor of several in the time they take.

The three questions the identity closes #

It closes them together, and they are worth separating because two of them were live and one of them was not.

The first was the one the sweep asked: is there a leaf that trades storage for time. There is not, and there cannot be, at any tolerance and on any kernel — the identity holds block by block and so holds however the blocks are arranged. The measurement is unnecessary and the sweep of it is a check on the arithmetic rather than a finding.

The second is subtler and was the reason to expect a difference. A compressed block of side s and rank r stores 2rs where a dense one stores $s^2$, so compression pays only while r is under half of s — which the storage sweep used to explain why a tighter tolerance wants a larger leaf. It would have been reasonable to think the arithmetic weighs the two kinds of block differently, because a dense block’s work is a square and a compressed block’s is a product of a small number and a sum. It does not. The rank that appears in it is the one a block nobody can call sparse measured and the size the rank does not notice found invariant to the block’s size, and neither of those facts enters here at all. Both are two operations per number, and the break-even side is the same number for both quantities, for the same reason.

The third is the one the identity does not close, and it is where the rest of this goes. The two counts agree on how many operations there are. They say nothing about how fast those operations run, and the whole reason anybody asks about time rather than storage is that they do not all run at the same speed.

What a machine charges that a count cannot see #

A count of operations treats reaching a block and doing arithmetic inside it as the same thing, and on a machine with a memory hierarchy they are not.

A hierarchical product at leaf 4 visits 1,102 blocks. At leaf 64 it visits 46. Each visit is an index computation, a pair of bounds, a pointer followed into an array that was probably not in cache, and — in most implementations — a function call. None of that is arithmetic and none of it appears in the sum. Whatever it costs, it is charged 1,102 times in one case and 46 times in the other, which is a factor of twenty-four on a quantity the count reports as zero.

That is the only thing in this whole measurement that is a property of the machine rather than of the matrix, so it is worth putting exactly one number on it and not more. A block size is a property of the machine makes the same move for a blocked elimination and finds the counted optimum and the measured one a whole term apart, which is the closest thing to a warning about what follows. Let the charge for reaching a block be some number of operations’ worth of time, and call it what it is: an overhead per block, paid before any entry is read. The cost of a product is then the operations plus the overhead times the block count, and the leaf that minimises it depends on what the overhead is.

That is a one-parameter family of answers rather than an answer, which is the honest shape. What the sweep can do is say where the answer changes.

The charge at which the answer starts to move #

Between two leaves the difference in cost is a straight line in the overhead — the operations differ by a fixed amount and the block counts differ by a fixed amount — so each pair of leaves crosses exactly once, and finding the crossing is a division rather than a search.

Leaf 32 overtakes leaf 16 at an overhead of 139 operations a block. Leaf 64 overtakes leaf 32 at 923.

Below 139, a code that wants speed and a code that wants memory want the same tree and there is nothing to decide. Between 139 and 923, they differ by one step of the leaf. Above 923, by two. That is the whole of the answer, and it is three numbers rather than a curve because there are only five leaves to choose between and the crossings come in order. A code that has to run well on more than one machine is in the position the recursion that was never told the memory describes, where a width tuned to one fast memory costs up to 2.9 times the best at another — and the reading here is that below the first crossing there is no tuning to get wrong.

The ordering is not automatic and is worth checking rather than assuming. It holds because the block count falls monotonically with the leaf while the arithmetic has an interior minimum, so past that minimum each successive leaf is dearer in arithmetic and cheaper in visits, and the trade goes one way. A representation whose block count did not fall monotonically could have its cheapest leaf jump two steps at one value of the overhead, and this one cannot.

Two leaves that never win, whatever the overhead #

The crossings below the storage optimum are the interesting ones, because they are negative.

Leaf 8 overtakes leaf 4 at an overhead of −35.5, and leaf 16 overtakes leaf 8 at −14.1. A negative crossing means the comparison never changes sign for any overhead a machine could have: leaf 8 does less arithmetic than leaf 4 and visits fewer blocks, so it wins on both counts at once and there is no charge that could rescue the smaller tree.

That is a stronger statement than the storage sweep made. It found leaf 4 storing 17 per cent more than leaf 16 and called it worse; the overhead reading says the two smallest leaves are not on the frontier at all — not merely beaten, but beaten in a way no property of any machine can reverse. A code choosing a leaf may restrict itself to 16 and above without knowing anything about the hardware it will run on.

The reason is the same break-even inequality, read from the other side, and the rank in it is the one which pairs are allowed to be small shows the admissibility test bounding before any entry is read. At rank 5 a compressed block is dearer than a dense one below side 10, so a leaf of 4 creates a whole bottom level of blocks that are stored — and therefore multiplied — larger than they need to be, and it creates a great many of them: 974 compressed blocks against leaf 16’s 156. More arithmetic in more blocks is not a trade.

The three numbers barely move with the size, and move a great deal with the accuracy #

A threshold is only useful if it is stable in the things a code does not control, so both were swept.

The size it is nearly indifferent to. At a fourfold change in n the overhead at which leaf 32 overtakes leaf 16 is 128, 136 and 139, and the one at which leaf 64 overtakes leaf 32 is 725, 870 and 923. Both are climbing and both are climbing slowly, toward what looks like a limit — which is what a threshold set by the shape of the partition rather than by its extent should do. The block counts at a given leaf quadruple with n and the arithmetic slightly more than quadruples, and the ratio of the two differences is what the crossing is, so the limit is the ratio the two growth rates approach.

That matters practically because it means the three numbers can be quoted without a size attached. A code choosing a leaf for a problem larger than anything measured here is choosing against the same thresholds.

The accuracy it is not indifferent to at all. Holding n at 512 and sweeping the tolerance, the overhead at which the optimum first moves is 264 at two digits, 223 at four, 139 at eight and 56 at twelve.

The direction is the useful part and it is the opposite of comfortable. A tighter tolerance makes the storage optimum less robust: the more accuracy a computation demands, the smaller the machine-dependent charge has to be before the leaf should be chosen for the machine rather than for the memory. At two digits a code would need an overhead of 264 operations a block before the two answers part; at twelve, 56 will do it, and 56 operations is within the range a single cache miss occupies.

The mechanism is the same break-even inequality once more. A higher rank flattens the arithmetic curve near its minimum — the leaves on either side of the optimum are storing more nearly the same amount — so a smaller nudge tips the total. The curve is not merely shifted upward by the accuracy; it is shifted upward and flattened, and the flattening is what the threshold is reading.

So of the two parameters a caller sets, one leaves the thresholds alone and the other moves them by a factor of five. The tolerance comes from the application — the knob that moved two things is where choosing it from the accuracy the answer needs is priced — and the size comes from the problem. It is the one that comes from the application that decides whether any of this needs thinking about.

What the overhead is not #

Two things the charge deliberately does not model, because including them would make the number unmeasurable rather than more accurate.

It does not model the rate at which a block’s own arithmetic runs. A dense 64 by 64 block is a matrix–vector product with good locality; a dense 4 by 4 block is not, and a compressed block’s two thin factors are two skinny products rather than one square one. Those differ in operations per second, not in operations, and folding them in would mean a second parameter per kind of block and a model with more knobs than measurements.

It does not model the blocks being visited in any particular order. A real implementation walks the partition in an order that reuses the input vector’s cache lines, and a good order makes the per-block charge smaller at every leaf rather than shifting it between them. The block size a recursion still has is the same observation about a different recursion: the width below which a code stops recursing is never absent, only unstated. Whether it shifts it unevenly — whether the charge is larger at small leaves because the visits are more scattered — is exactly the sort of thing that would move the crossings, and it is not something a count can find.

Both of those point the same way as the charge itself: toward larger leaves. So 139 and 923 are best read as upper bounds on where the answer moves, not as estimates of it. If the arithmetic inside a small block also runs slower per operation, the leaf that minimises seconds is at or above the leaf this says it is.

What must fail for any of this to be wrong #

Five claims and a refusal. That the operation count is exactly twice the stored total at every leaf, which is an equality between integers rather than an agreement to some tolerance. That the two counts therefore choose the same leaf. That no positive overhead makes either of the two smallest leaves the cheapest, which is the negative-crossing reading. That the crossings above the optimum are positive and come in increasing order, so the choice walks up one step at a time. And that just past the first crossing the cheapest leaf is no longer the storage optimum, which is what makes the number mean anything.

The refusal is fed the claim that the operation count prefers a different leaf from the storage, and required to fail.

The equality is required as an equality and not as a closeness, which is the right form here: both quantities are sums of products of integers, computed in exact arithmetic, and a tolerance on them would be a tolerance hiding a mistake rather than hiding rounding.

What this does not settle #

One matrix, one kernel, one size, five leaves at powers of two. The crossings are located between those five and not inside them, so 139 is the overhead at which leaf 32 becomes better than leaf 16 and not the overhead at which some leaf between them does.

The overhead is a single number standing for several different costs, and it is not measured here — nothing in this collection can measure it, because it is a property of a machine and everything here is a count. What the sweep supplies is the sensitivity: how large it would have to be before it mattered, which is the part a measurement on a real machine could then be compared against.

And the whole reading is about one product. A code that applies the same representation many times amortises some of the per-block cost — the index computations can be done once and kept — which lowers the effective overhead and pushes the answer back toward the storage optimum. A code that applies it once, inside a larger recursive algorithm that walks the tree for other reasons, pays it every time.

What the identity is worth outside this sweep #

The negative result is small and the reason for it is not, so it is worth saying what else it covers.

Any representation whose apply is one pass over its stored numbers has this property, and most of the ones this field is built on are: a sparse matrix in compressed rows, a low-rank factorisation, a sum of Kronecker products, a hierarchical matrix under either partition rule. For all of them, operations and numbers stored are one quantity, and any question about the trade between memory and time is a question about the machine and not about the representation.

The representations where the two genuinely differ are the ones that read a number more than once or generate numbers they do not store — a factorisation applied by forward and back substitution, an iteration that rebuilds entries on the fly, a matrix-free operator. Those are the places where a second sweep would find a second optimum, and this field’s own matrix-free line is where the distinction lives.

So the sweep asked for here was worth running once, and its result is that the question belongs to a different family of objects than the one it was asked about.

Still open: the charge itself, and the leaf inside a solve #

The overhead as a measurement rather than a parameter. Everything above prices the answer’s sensitivity to a number nobody has measured. Timing one hierarchical product at each leaf on one machine and fitting the two coefficients — a cost per operation and a cost per block — would give it, and the fit’s residual would say whether a two-term model is the right shape at all or whether the rate inside a block has to be modelled too. That is a measurement on hardware rather than on a matrix, which is why it is not made here, and it is the only thing standing between these three numbers and an answer.

Whether the charge is the same at every leaf. The model charges one overhead per block visit regardless of the block’s size, which is what makes the crossings a division. If reaching a small block costs more than reaching a large one — because the visits are more scattered in memory — then the charge is itself a function of the leaf, the cost curves are no longer straight lines in it, and the crossings could move or disappear. Measuring the charge at two leaves rather than fitting one number across all five would say which.

The leaf inside a hierarchical solve. A product is one pass. A hierarchical solve is a recursion that visits the tree repeatedly, forms intermediate low-rank blocks, and truncates them — so it reads numbers it did not store and stores numbers it then discards, which is exactly the shape the identity above does not cover. Whether the leaf that minimises a solve’s arithmetic is the one that minimises its storage is therefore an open question of the kind this one turned out not to be, and it is the one worth asking next. Where the format starts paying prices that solve against a dense factorisation and finds the crossover walking with the accuracy, which is the curve a leaf sweep would sit inside.

And what a shallower tree buys the recursion. A larger leaf means fewer levels, and every recursive algorithm on this structure walks them. The block count is one measure of that and the tree height is another, and they do not move together: from leaf 4 to leaf 64 the block count falls by a factor of twenty-four and the height by three levels. Which of the two the overhead is really charging for is a question the sweep cannot separate, because on a balanced tree they are locked to one another.