The scale that only moved a pivot

A multiplier is a force put a third equality constraint into a least-squares fit, a near repeat of the first at distance ε, and gave its datum a strain δ — an amount it asks for beyond what the other two imply. The Lagrange multipliers grew as $0.0133\,\delta/\varepsilon^2$, a force on a lever of length ε, and the two routes to the answer parted company. The null-space route, which factors the constraint block $B$ and solves the fit in the directions $B$ leaves free, stayed at about a tenth of κ(B)·u whatever the strain. The saddle-point route, which solves one indefinite system for the answer $x$ and the multipliers λ together, rose with the strain: at ε = 10⁻⁸ from 6.3·10⁻⁹ with no strain to 4.6·10⁻⁴ at δ = 10⁻⁵, where the null-space route was at 1.8·10⁻⁸.

The same gap shows against the conditioning. When the third constraint asks for a new condition at every ε, the saddle-point route as given sits above κ(B)·u from the middle of the sweep and ends at 8.2·10⁻³, while the null-space route stays under the dashed line throughout; when it asks for nothing, the two routes run together.

The essay argued a reason without isolating it. A backward-stable elimination of the system

$$\begin{pmatrix} A^{\mathsf T}A & B^{\mathsf T} \\ B & 0 \end{pmatrix}\begin{pmatrix} x \\ \lambda \end{pmatrix} = \begin{pmatrix} A^{\mathsf T}b \\ d \end{pmatrix}$$

commits an error proportional to the norm of the whole unknown, and when λ is 10¹² that norm is λ’s; a part in $10^{16}$ of 10¹² is not small next to an answer of size one. It proposed the test in its last section. Multiply the constraint rows $B$ and their data $d$ by a scale $s$: the feasible set does not change, $x$ does not change, and the multipliers are divided by $s$. Choose $s$ so they come out the size of $x$, and if the argument is right the extra loss goes with them — “at the price of making $B$ itself badly scaled”, which the units the matrix is measured in had priced for a single linear system.

The prediction holds, and the argument fails it.

Multipliers the size of the answer #

Every error here is measured against an exact answer: the optimality conditions solved in rational arithmetic from the stored doubles of $A$, $b$, $B$ and $d$, as in the essays before, so the reference has nothing rounded in it and a scaled problem’s reference is the same answer to the last bit.

The figure is the strain sweep at ε = 10⁻⁸, where κ(B) is 4.64·10⁸ at every point, with three versions of the saddle-point route beside the null-space route. As given, the route is the red line from the earlier essay, rising five decades with the strain. Rescaled so the exact multipliers are the size of $x$, it is the purple line: 2.5·10⁻⁸ at the smallest strain, 1.4·10⁻⁸ at δ = 10⁻⁸ and 3.3·10⁻⁸ at the largest, against the null-space route’s 7.8·10⁻⁹ to 1.8·10⁻⁸. Where the saddle-point route had been 25,000 times worse, at the large strains it is within about a factor of two.

A code does not have the exact multipliers, so the third version reads the scale from a first, unscaled solve — the ratio of its λ to its $x$, an inaccurate λ but a usable ratio, which agrees with the exact one to under a per cent wherever the multipliers are large because of a genuine demand — and never scales by less than one. That line is the green one, and it does the same: 1.8·10⁻⁸ at the largest strain. The scales involved are large. At δ = 10⁻⁵ the exact ratio is 5.9·10⁵, and the constraint rows are being multiplied by more than half a million.

None of this touches κ(B). A uniform scale multiplies every singular value of $B$ by the same factor, so the scaled block’s condition number equals the unscaled one to within a per cent, which is as finely as the singular value decomposition resolves the smallest singular value at these sizes. The price the earlier essay expected was a badly scaled $B$, and a uniform scale cannot produce one.

Two families of constraint, one remedy #

The strain sweep holds ε fixed. The other sweep in the earlier essay held the construction fixed and let ε fall, on two families: one in which the third constraint asks for a new condition at every ε, so that the multipliers rise in proportion to κ(B), and one in which its datum is set to what the other two constraints imply, so it asks for nothing but its own rounding.

On the first family the saddle-point route as given was the worst of the three at every ε below 10⁻⁴, by a factor of 290 at ε = 10⁻⁶ and of nearly fifty thousand at 10⁻⁸, where it was wrong by 1.2·10⁻³ against the null-space route’s 2.5·10⁻⁸. Rescaled, it is 1.4·10⁻¹⁰ at ε = 10⁻⁶ and 4.9·10⁻⁹ at 10⁻⁸ — on the second, five times better than the null-space route. At ε = 10⁻¹², where κ(B)·u is 5.2·10⁻⁴, the rescaled route is at 1.3·10⁻⁴ and the null-space route at 1.2·10⁻⁴: the two have met at the floor the conditioning sets, which is where the earlier essays found every honest route ends up.

Turn the dial to the second family. The multipliers there are 0.0040 down to ε = 10⁻⁶; from 10⁻⁸ the rounding of the third datum, amplified by the lever, lifts them, to 0.040, then 440, then 2.0·10⁶. The exact scale is therefore below one for most of the sweep — 5.6·10⁻⁴ — and scaling to it means raising the multipliers to the size of $x$ by making $B$ nearly two thousand times smaller. The essay that proposed balancing did not say which way. On this family it makes no difference either way, to within the scatter of rounding: the scaled route’s errors are between 0.2 and 12 times the unscaled ones, with no trend in ε, and the capped scale — which never shrinks $B$ — leaves the problem as it was. That was the first sign that the size of the multipliers was not what the error read, and the next figure is what it was reading instead.

A scale of ten does what half a million does #

The test so far uses one scale per problem, the one the argument chose. Sweep the scale instead, on one problem — the first family at ε = 10⁻⁸, whose multipliers are 1.6·10⁶ times the size of its answer — from $s = 10^{-4}$ to $10^{8}$.

The large dots are the route as a solver runs it, with partial pivoting. At $s = 1$ the error is 1.2·10⁻³. At $s = 10$ it is 5.6·10⁻⁸. From there to $s = 10^{8}$ it wanders between 4.7·10⁻⁹ and 5.6·10⁻⁸ with no slope at all, through the vertical line at 1.6·10⁶ where the argument said the remedy should be centred. The multipliers at $s = 10$ are still 1.6·10⁵ times the answer, and the route has already recovered everything it is going to.

If the error were proportional to the size of the combined vector, it would fall steadily as $s$ rose, by a decade per decade until λ/s reached the size of $x$, and then level off. It does neither. It falls by more than four decades between two adjacent scales and then does not move for seven more. That is the shape of a discrete event, and in an elimination with partial pivoting there is one obvious discrete event: which row is chosen as the pivot.

Partial pivoting compares the entries of a column and takes the largest. Multiplying the constraint rows by $s$ multiplies their entries in the columns of $x$ by $s$, and somewhere between a scale of three and of five the comparison at the second step changes its answer. At a scale of one the elimination takes, for its first six pivots, the second constraint, then a row of $A^{\mathsf T}A$, then the third constraint, then three more rows of $A^{\mathsf T}A$. From a scale of five onwards it begins with the second constraint and then the third, before any row of $A^{\mathsf T}A$. Nothing else about the run changes.

Hold the order and the scale does nothing #

That is a hypothesis about the dots, and it can be tested directly by taking the choice away from partial pivoting: permute the rows of the saddle-point matrix into a fixed order and eliminate with no interchanges, at every scale. The three lines in the same figure are three such orders.

The red line keeps the order partial pivoting takes at a scale of one. Its error is between 4.1·10⁻⁵ and 5.7·10⁻³ at every scale from 10⁻⁴ to 10⁸ — twelve decades of scale, ten decades of multiplier size, and no trend; with the multipliers a million times smaller than at $s = 1$, at $s = 10^6$, it is 4.3·10⁻³, a little worse. The purple line keeps the order partial pivoting takes at $s = 10^4$, and its error is between 2.1·10⁻⁹ and 5.6·10⁻⁸ at every scale, including $s = 1$, where the multipliers are as large as they ever are: 5.0·10⁻⁹. The green line puts every constraint row before any row of $A^{\mathsf T}A$, and lies with the purple, 1.5·10⁻⁹ to 3.9·10⁻⁸.

So the scale was never the variable. Under a fixed order, multiplying the constraint rows by $s$ is a diagonal scaling of the rows and columns of the saddle-point matrix, and an elimination without interchanges is indifferent to that up to the rounding of the scaled entries — which is the result the units the matrix is measured in and a condition number scaling cannot move both rest on. What the scale can change is the decision partial pivoting makes, because that decision compares numbers whose units differ. The pivot that reads the units built a row scaling that made partial pivoting repeat the catastrophic elimination it exists to prevent, on the standard two-by-two; this is the same mechanism run the other way, a scaling that steered it out of a bad order and into a good one.

The left half of the figure is the converse, and the warning that goes with it. Scale the constraint rows down and partial pivoting takes rows of $A^{\mathsf T}A$ first for longer: at $s = 10^{-4}$ none of the first six pivots is a constraint row, and the route returns an answer with no correct digit, an error of 2.5. The earlier essay’s caution about badly scaled constraints was right about this direction and only this one.

What the order does with a demand #

The earlier essay’s observation still has to be accounted for: the saddle-point route as given did get worse as the multipliers grew, over twelve decades of strain. The order explains that too, once it is held fixed and the strain is moved instead. With no strain the order partial pivoting takes unscaled is harmless — 6.1·10⁻⁹, the same as the other two orders and the null-space route. At δ = 10⁻¹¹ it is 1.5·10⁻⁷, at δ = 10⁻⁸ it is 1.1·10⁻⁴, and from δ = 10⁻⁵ it sits at 4.6·10⁻⁴. The other two orders stay between 2.5·10⁻⁹ and 1.0·10⁻⁸ across the whole sweep.

So the multipliers and the error did rise together, and for a common cause rather than one causing the other. The strain is a demand the near-repeated pair of constraints makes through a row of size ε. The multipliers are the force that holds that demand, and they grow with it as $\delta/\varepsilon^2$. The bad order is one that resolves the demand late — after a row of $A^{\mathsf T}A$, with entries of order one, has been eliminated between the two halves of the near-repeated pair — and so resolves it against rounding committed at the scale of that row rather than at the scale of the demand. With no demand there is nothing to resolve and the order costs nothing, which is why the second family above showed no effect at any scale.

The sweep on that family is the control. Partial pivoting changes order at the same scales as on the first family — the matrix is the same up to one datum, and the datum does not enter the pivot comparison — and the three fixed orders behave as before in the sense that none of them responds to the scale. What is missing is the gap between them: every order and every scale lands between 8·10⁻¹⁰ and 5.1·10⁻⁸, the scatter of rounding on a problem whose κ(B) is 4.6·10⁸. The bad order is bad only in the presence of a demand. The plausible reading of that mechanism is stated here and not isolated; what is measured is that the order turns a demand into error and the other two orders do not.

The multipliers were therefore an honest symptom and a wrong diagnosis. A large multiplier means the constraints are holding a large demand, and in the unscaled order a large demand means a large error. But the remedy the diagnosis suggested — shrink the multipliers — works only because, on this matrix, the way to shrink them is also a way to change the pivot order.

Constraints first, and no scale to estimate #

That changes what the remedy is. The rescaling needed an estimate of the multipliers, from a first solve that costs as much as the real one, and it worked for a reason that has nothing to do with the estimate: a scale of five or more makes partial pivoting take the constraint rows early, and any number from five to a hundred million did. Where the threshold sits depends on how the entries of $B$ compare with those of $A^{\mathsf T}A$ in each column, which is a property of the data’s units rather than of the problem, and a code cannot know in advance that five is enough.

Ordering the constraint rows first needs nothing. It is a fixed permutation of a matrix the solver has just assembled, it is independent of every scale, and it is the order the null-space route follows by construction — factor $B$, then solve the fit on what remains. The saddle-point route with that order is not the null-space route: it still forms $A^{\mathsf T}A$, and the reference was a method found that forming it is where that route loses most of what it loses when $A$ is ill-conditioned. But it removes the part of the loss the multipliers were blamed for, at no cost on every problem here, and on the first family at ε = 10⁻⁸ it is within a factor of two of the null-space route at every scale.

It is also a reminder of why a saddle-point matrix cannot simply be handed to a symmetric factorisation in any order. The zero that is not a missing entry showed the zero block is a theorem — no order makes the matrix definite — and the regularisation that legalises every order showed that perturbing both blocks makes every symmetric order legal, with growth that varies by six orders across them. Legal is not accurate. On these problems two orders, each of which completes without a zero pivot and returns an answer that satisfies every constraint to $10^{-15}$, differ in accuracy by five decades — the same silence feasible and wrong found in the residual, met here in the pivot sequence.

Where the conditioning still wins #

The order removes the saddle-point route’s extra loss; it does not remove the loss the problem carries. At ε = 10⁻¹² on the first family the constraints-first order is between 3.7·10⁻⁵ and 4.0·10⁻⁴ across the scales and the null-space route is at 1.2·10⁻⁴, both under κ(B)·u = 5.2·10⁻⁴: what is left is the rounding of the data amplified by the lever, which the condition number that does not know and the multipliers essay both traced to the problem a machine holds, before any route is chosen. The unscaled order at the same ε is worse than that floor by a factor of 16 on its good scales and returns no correct digit on its bad ones, at an error of 2.6 — the same order, the same matrix up to a diagonal scaling, and an answer that depends on the scale only through the rounding of its entries, which at κ(B) of 10¹² is enough to flip a nearly cancelled pivot between harmless and fatal.

That last observation is worth stating for what it says about testing. On the first family at ε = 10⁻⁸ the bad order’s error at the thirteen scales ranges over two decades, 4.1·10⁻⁵ to 5.7·10⁻³, for one fixed sequence of row operations. A single run of the saddle-point route as given, at one scale, is one draw from that spread. The earlier essays read single runs and found the route to be about κ(B)·u, or a few times worse, and both readings were draws.

What these problems do not show #

One construction: twelve observations, six unknowns, three constraints of which two are nearly parallel, one seed. The pivot order partial pivoting takes depends on the magnitudes in every column, and on a different $A$ the switch from a bad order to a good one would happen at a different scale, or not at all — a matrix on which partial pivoting already takes the constraint rows first unscaled would show no loss to remove, and no gain from scaling. The claim that survives a change of construction is the narrower one: at a fixed order, scale does not move the error, and an order that eliminates the constraint rows before the fit’s normal equations does not turn a demand into error. Both are measured here on one matrix, at thirteen scales and on twenty problems.

Still open: where the switch sits, and the multiplier as a rank decision #

The threshold scale. Partial pivoting changes order between a scale of three and of five on this problem. The comparison it makes at the second step is between the third constraint’s entry in the column being eliminated, after the first step has updated it, and the largest entry of $A^{\mathsf T}A$ in the same column — both computable before anything is solved. The prediction with a sign is that the switching scale is that ratio’s reciprocal, to within the change the first step makes to it, and that a code can therefore compute a sufficient scale cheaply rather than estimate the multipliers. Whether a scale read that way is ever worse than the constraints-first order is the measurement.

A multiplier as a rank decision. The question the earlier essay left beside this one still stands. Deleting a redundant constraint is a rank decision on $B$ made with the data in view, the kind the rank depends on the ring showed is never a property of the numbers alone. On the second family the third constraint’s multiplier is made of the rounding of its datum, and a rule that deletes a constraint whose dropped residual is at the rounding level of its datum would make the decision without a threshold on κ(B). How small a genuine demand such a rule can tell from none is the sweep that would turn it into a method — and, after this essay, it should be run in the constraints-first order, since the order is what decides whether a small demand survives elimination at all.