The order a batch arrives in

The problem that arrives again classifies what changes between the members of a sequence and prices four kinds of it. It treats the sequence as given: a list of problems arriving in an order nobody chose, to be solved one at a time as they come.

That is exactly right for a continuation, a time-stepping code and a Newton iteration, where member s + 1 is built from the answer to member s and there is no order but the one. It is wrong for the fourth case the field names and passes over quickly — a design sweep solving the same structure under two hundred load cases, a parameter study, a batch of related fits — where every member is known at the start, none depends on any other, and the loop’s order is whatever the enumeration produced.

The median shuffling costs 1.54 times what the sorted order costs. The worst costs 1.84. The answers are identical, the problems are identical, and the arithmetic differs by that much because of the sequence a for loop happened to produce.

Why the order is a cost at all #

The mechanism is the whole of the field’s third case, stated backwards.

A factorisation of member s is an approximation to the matrix of member s + 1, and how good an approximation is decided by how far apart the two members are. A factorisation kept past its date measures the shelf life directly: one Cholesky factor serves five members of a drifting sequence and saves 44 per cent of the work, and kept for twenty it stops converging altogether.

Sort the members and consecutive ones are one drift step apart. Shuffle them and consecutive ones are an arbitrary distance apart — on a sixteen-member batch the average jump is about five steps rather than one. A factorisation that would have served five sorted members serves one shuffled one, and the rule that decides when to rebuild fires far more often.

So the shuffle does not change any problem, it changes the distances between neighbours, and the distances are the only thing the reuse decision depends on.

The arithmetic of that is worth writing out, because it says how the penalty should scale. Sixteen points on a line visited in order travel a total of fifteen steps. Visited in a random order they travel, on average, about a third of the whole interval per hop — the expected distance between two uniform points on an interval is a third of its length — which on fifteen hops over an interval of fifteen steps is about seventy-five steps. So a shuffle travels roughly five times as far, and if a factorisation’s shelf life were simply a distance the penalty would be five.

It is not five, because the rule does not pay in distance. It pays in factorisations, and a factorisation serves a whole member however far that member is; a hop five times too long costs one extra rebuild rather than five. That is why the measured penalty sits between 1.06 and 2.80 rather than near five, and why it rises with the drift: at a small drift even a long hop is inside the shelf life, and at a large one even a short hop is not.

The three pictures share a horizontal axis and a vertical one, so what changes between them is the height of the curve and nothing else. That is the shape of a quantity whose whole content is the drift: at 0.01 the penalty is a few per cent and could be ignored, at 0.04 it is half again the sorted cost, and at 0.16 it is more than double. Nothing about the problems moved and nothing about the rule changed.

Put beside that classification, the measurement above says something the classification cannot. Its four bars are what changes between one member and the next, which is presented as a property of the problem. On a batch it is a property of the order: the same sixteen members are a slowly drifting sequence when they are sorted and a set of nearly independent problems when they are shuffled, and the bar a code lands on is decided after the problems are known.

Where the factorisations go #

The count behind the flops is the clearer number, and it is worth reporting on its own.

At a drift of 0.04 the sorted order needs four factorisations for sixteen members. The shuffles need between five and nine. At a drift of 0.16 the sorted order needs eight and the worst shuffle fourteen, which is nearly one per member — the point at which reuse has stopped happening at all and the run has become the field’s fourth case, sixteen independent problems in a loop.

That is the transition worth seeing: a shuffle does not degrade reuse gradually, it moves the run from one of the field’s four kinds to another. A batch that would have been the matrix drifts slowly becomes everything changes, and the cost model that applies to it changes with it, without anything about the problems having moved.

The inner steps move the other way and partly compensate, which is why the flop penalty is 1.54 rather than the 2.25 the factorisation counts alone would suggest. A fresher factorisation takes fewer chord steps per member, so a run that rebuilds more often does less work per member — and the two effects are what the rule is balancing. The penalty that survives is the part the rule cannot recover.

The penalty rises with the drift, and so does the prize #

Across drifts of 0.01, 0.04 and 0.16 the median penalty reads 1.06, 1.54 and 2.19 and the worst reads 1.21, 1.84 and 2.74.

Both ends of that are worth having. At a small drift the order hardly matters, because one factorisation serves everything however the members are arranged and there is almost nothing for the ordering to save. At a large drift the sorted order itself needs many factorisations — eight of sixteen — and the shuffle needs nearly one per member, so the penalty approaches the ratio between “reuse sometimes” and “reuse never”.

That ratio is the ceiling on what ordering can ever be worth, and it is the same quantity the field’s first essay puts at 100% for a sequence in which nothing carries. So the ordering question has a bound and the bound is the difference between the field’s third case and its fourth.

One shuffle of eight at the smallest drift comes out three per cent cheaper than the sorted order, which is worth not hiding. The rebuild rule reads an observed contraction ratio rather than a distance, so a lucky arrangement can trip it fewer times than the orderly one does. That is noise in a quantity whose median is 1.06, and it disappears entirely by a drift of 0.04.

The reordering is a sort #

The remarkable part of the measurement is not the penalty; it is how completely it is recoverable.

A nearest-neighbour path — start where the batch starts, repeatedly go to the closest unvisited parameter value — matches the sorted order’s arithmetic to every digit, on all eight shufflings, at all five drifts. Not nearly: the flop counts are equal integers.

That is not a coincidence and it is not an achievement of the heuristic. The members here lie along a line in one parameter, and a nearest-neighbour path along a line visits the points in order — the greedy choice is the optimal one because there is nowhere else to go. So the reordering problem in one parameter is a sort, it costs n log n comparisons on numbers the code already has, and it recovers all of a penalty that reaches a factor of 2.8.

A code solving a batch over one parameter should sort it, and that is the whole recommendation. There is no threshold to tune — unlike what a rebuild is worth, where the cheapest period depends on what a rebuild cost and six different answers are all correct — no estimate to make, and nothing to measure first: the sorted order is never worse, it is up to 2.8 times better, and finding it costs nothing beside a single solve.

And in more than one parameter it is not #

The honest limit arrives as soon as the sweep has two knobs.

A batch over two parameters is a set of points in a plane, the cost of visiting them in an order is the total distance travelled, and finding the cheapest order is the travelling salesman problem. Greedy is no longer optimal, it has no constant-factor guarantee, and the question stops being a sort.

That is the same escalation the sparse field and the contraction field both make: a decision about order that is trivial in the smallest case and NP-hard in the general one, with heuristics measured against an exhaustive answer only where an exhaustive answer exists. What is unusual here is that the one-parameter case is not a toy — a great many parameter studies really do vary one thing — so the tractable case is also a common one.

What the two-parameter case would need is a distance. The natural one is not the Euclidean distance between parameter values but the distance between the matrices they produce, since that is what the factorisation’s shelf life depends on, and the two are the same only when the parameters enter the matrix comparably. Nothing here measures that, and it is the first thing a code with two knobs would have to decide.

The refusals #

The claim worth breaking is the one a cost model makes by omission: the cost of a batch is decided by how many problems there are and how far apart they are. Both of those are held fixed here — the same sixteen members, the same drift — and the assertion that the arithmetic is therefore the same is fed the shuffles and required to fail, at a median of 1.54 and a worst of 2.80.

The second refusal is the control that makes the recommendation safe. Fed all eight shufflings at all five drifts, the claim that a nearest-neighbour reordering differs from the sorted order is required to fail — the two flop counts are equal integers in all forty cases, which is what says the reordering is a sort rather than a heuristic that usually works.

And the third refuses the reading that the penalty is unbounded. Fed the smallest drift, the claim that the order always costs a factor has to fail: the median penalty there is 1.06 and one shuffle of eight is cheaper than sorted, because a rule that reads a contraction ratio can be tripped fewer times by a lucky arrangement than by an orderly one.

What this does not change about the field’s other cases #

Three qualifications, because the recommendation above applies to exactly one of the four kinds of sequence.

Not a continuation or a time-stepping code. There the order is the problem: member s + 1 is built from the answer to member s, and reordering is not available at any price. Those are the sequences the field’s other measurements are about and nothing here touches them.

Not a Newton iteration. Same reason, more sharply: the iterates are produced by the method and the notion of solving them in a different order is not defined.

And not a batch whose members are independent problems. The field’s fourth case — everything changes — has no reuse to schedule, so no order is better than any other and a sort buys nothing. The recommendation lives entirely in the case where the matrix drifts and the members are known in advance, which is the intersection of the field’s third case with its fourth.

What a code would have to know #

The sort needs a parameter to sort on, and that is a real requirement rather than a formality.

A batch assembled from a loop over a parameter has one. A batch assembled from a list of load cases, or from a set of configurations read out of a file, may not — the members may be related without any scalar ordering them, and then the distance between two of them is a matrix norm rather than a subtraction. Computing that for every pair is $n^2$ matrix norms, which is affordable for a few hundred members and is not free.

The cheap case is the common one and it is worth naming precisely: a batch parameterised by one number, where the sort is on that number and costs nothing. The expensive case is a batch related by structure rather than by a parameter, and there the ordering question has the same shape as the contraction field’s and the sparse field’s — a distance that has to be computed before it can be minimised, and a minimisation that is hard once it can.

The same sentence, three fields apart #

An ordering that changes no answer and changes the cost by a factor is the single most repeated finding in this collection, and this is the fourth field to produce one. Collecting them says what is particular about each.

The order decides the memory is a sparse elimination, where four orderings of one matrix give factors of 1,739, 1,354, 1,413 and 1,026 entries. The resource is storage, the decision is symbolic, and the optimum is NP-hard.

The order the products are taken in is a tensor contraction, where two evaluation orders of one expression differ by a factor of two million. The resource is arithmetic, the decision is symbolic, and the optimum is computable on the networks that occur.

The same arithmetic at a different price is a blocked elimination, where the same 72,568 operations move 41,332 words or 19,476. The resource is traffic, the decision is a block size, and the optimum is a property of the machine.

This one is the fourth and it is the easy one. The resource is arithmetic, the decision is a permutation of a set of problems, and the optimum is a sort — because the objects being ordered sit on a line and the cost of an ordering is the total distance along it. Three of the four have an optimum nobody can compute and this one has an optimum a library function returns.

What the four share is the shape of the omission. In every case the quantity that varies is not in the problem statement, does not appear in any answer, and is invisible in every check a code performs. A run that solved its batch in a bad order returns exactly the right answers, satisfies every residual test, and is slower — which is the one failure mode this collection keeps finding and the one no gate anywhere reports.

Still open: the rule and the order together #

The measurement holds the rebuild rule fixed and varies the order, which is half of a question.

The rule used here rebuilds when the observed contraction ratio is worse than a threshold, which is the rule a factorisation kept past its date finds beats every fixed period without being told the drift. It reads a quantity produced by the iteration, so it adapts to whatever order it is given — and the penalty measured above is what it costs to adapt to a bad order rather than to be given a good one.

A rule that knew the order in advance could do better still. Sorted members arrive at a known distance, so the number of members a factorisation will serve is predictable before the run, and a code could schedule the rebuilds rather than discovering them. Whether that beats the contraction-ratio rule on a sorted batch — where the rule has an easy job — or merely matches it, is the measurement this page does not make.

The second open question is whether sorting is the right objective. The sort minimises the total distance travelled, which minimises the number of rebuilds; it does not minimise the total work, because a rebuild and an extra inner step are different costs and the trade between them depends on the problem size. A sweep over n would say whether the two objectives ever disagree, and on this family they cannot, because the sorted order minimises both.

One line #

A batch of related problems is a set rather than a list, the order it is solved in is worth up to a factor of 2.8, and along one parameter the reordering that recovers all of it is a sort.