The switch is read before the solve

The scale that only moved a pivot took the saddle-point route to an equality-constrained least-squares fit apart. The route forms the optimality conditions — $A^{\mathsf T}A$ beside the constraint matrix $B$, the multipliers alongside the solution — and solves them by Gaussian elimination with partial pivoting. On a problem whose third constraint nearly repeats its first it lost digits in proportion to the multipliers, and rescaling the constraint rows so that the multipliers came out the size of the solution removed the loss. But not for the reason given. Held in a fixed row order, nine decades of scale moved the error by less than a factor of five; what the scale changed was which row partial pivoting took at the second step, and eliminating every constraint row first, with no scale at all, did best of every order tried.

It closed on the question of where the switch sits. “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.”

The switching scale can be read exactly. Whether it is sufficient depends on what sufficient is measured against.

Why one elimination is enough #

The saddle-point matrix has the normal matrix $A^{\mathsf T}A$ in its top left, $B^{\mathsf T}$ beside it, $B$ below, and zeros in the corner. Scaling the constraints by s multiplies the rows and columns that belong to $B$ by s. Partial pivoting looks, at each step, down the column being eliminated, at rows of two kinds: rows of the normal matrix and constraint rows.

The structure of the scaling decides the competition. In the first n columns, where the solution’s unknowns sit, a constraint row’s entries are s times what they would be unscaled, and a normal-matrix row’s are independent of s. That stays true after any elimination step. If the pivot is a normal-matrix row, a constraint row loses a multiple of it whose size is proportional to s and keeps its proportionality; if the pivot is a constraint row, a normal-matrix row loses $a/(sc)$ times a row that is s times something, and the s cancels. So at every step the comparison is between a number that does not move and s times a number that does not move, and the unscaled elimination contains both.

The prediction is then exact rather than approximate. Run the unscaled elimination with partial pivoting once; at each step record the largest candidate among the normal-matrix rows, a, and among the constraint rows, c. The unscaled order survives scaling by s for as long as s stays below $a/c$ at every step a normal-matrix row won and above it at every step a constraint row won. The upward switch is the smallest $a/c$ among the steps a normal-matrix row won.

Forty-nine problems, one ratio each #

The figure above is every problem’s switch, read off one unscaled elimination and found by bisection. The problems are the earlier essays’: a fit of six unknowns to twelve observations with two constraints — the setting of a constraint is a weight at infinity, which reached the same answer as a limit of heavy weighting — and a third constraint equal to the first plus a coupling ε times a random direction, at seven couplings from one to $10^{-12}$; the third constraint’s datum either repeats the first’s, asks for nothing the first two do not already imply, or asks for that plus a strain δ at five sizes. On every one the scale read off the unscaled elimination agrees with the scale bisection finds — searching for the first scale at which partial pivoting’s row order differs — to within $4.4 \cdot 10^{-16}$ relatively. The switch is 1.820 at a coupling of one, 3.067 at $10^{-2}$, and 3.197 or 3.198 at every smaller coupling, the same for all seven problems at a coupling, because the datum does not enter the matrix.

The step that decides it is the second on every problem except those at a coupling of one, where it is the third. The figure shows why the first step does not: there a constraint row wins outright, 1.76 against 0.135, and a constraint row that wins at s = 1 only wins harder at larger s. At the second step a normal-matrix row wins, 0.174 against 0.054, and that is the comparison a scale of 3.198 reverses. The earlier essay’s guess — the ratio between the third constraint’s entry and the normal matrix’s, after the first step’s update — is right in substance and wrong in one detail: the constraint row that competes at the second step is whichever is largest after the update, not necessarily the third.

The change the first step makes is not small. In the unreduced first column the ratio of the largest normal-matrix entry to the largest constraint entry is 0.076; the switch is at 3.198, forty times larger. Reading the switch “before anything is solved” means reading it after one elimination step, which is the first $n^2$ of the solve’s work, not before it.

A scale just past the switch removes the catastrophe #

The figure is partial pivoting’s error against the scale on the repeated constraint at a coupling of $10^{-8}$. Below the switch the error is $1.2 \cdot 10^{-3}$; at 1.01 times the switch it is $2.4 \cdot 10^{-8}$, and over the next five decades of scale it wanders between $10^{-9}$ and $10^{-7}$ around the constraints-first order’s $1.7 \cdot 10^{-8}$. One decade of scale is worth four decades of accuracy, and the decade is computable.

The dial runs the coupling. The step stays at the same scale — the comparison that decides it involves the normal matrix and the first two constraints, not the third constraint’s small difference from the first — and its height grows as the coupling shrinks: at $10^{-6}$ the unscaled order costs $1.7 \cdot 10^{-8}$ against $2.5 \cdot 10^{-10}$ just past the switch; at $10^{-12}$, $8.2 \cdot 10^{-3}$ against $2.8 \cdot 10^{-4}$. On every problem where the unscaled order loses more than a thousand times the constraints-first error — the repeated and strained problems at small couplings — a scale 1.01 times the switch brings the error within fifteen times it.

And does not make the route as good as constraints first #

The best of five scales — 1.01, 2, 10, a thousand and a hundred thousand times the switch — is within three times the constraints-first error on forty-five of the forty-nine problems. On the other four it is thirty to thirty-nine times worse: the consistent problem and the three smallest strains at a coupling of $10^{-6}$, where every scale gives about $1.1 \cdot 10^{-10}$ and the constraints-first order gives $3.5 \cdot 10^{-12}$. On those four the unscaled route was fifty-four to sixty-eight times worse than constraints first as well. The condition number that does not know found two constrained fits with the same size and the same conditioning of A returning errors twelve orders apart, separated by a conditioning no solver reports; here the same problem at the same conditioning returns errors thirty times apart depending on a pivot sequence no condition number sees. The switch repairs the step partial pivoting gets wrong because of the scale; it does nothing about the later steps, where partial pivoting’s choices among rows of one kind are made on sizes the scale does not touch, and on these problems those later choices are the ones that cost.

That answers the earlier essay’s question in the direction it feared. A scale read off the elimination is cheap and sufficient against the catastrophe — the loss the multipliers were first blamed for — and it is not sufficient against the order. The constraints-first order is thirty times better on four problems; where it is worse than the best of five scales, by up to thirteen times, both errors are within a few units of rounding or of the squared conditioning’s floor, and it needs no scale, no ratio and no first elimination to compute one.

The window has two edges #

The same elimination gives the other edge. At every step a constraint row won, the unscaled order survives only while s stays above the ratio $a/c$ there, and the largest of those ratios is the scale below which the order changes the other way: a constraint row that won at s = 1 loses to a normal-matrix row once the constraints are shrunk enough. On the problems at couplings of $10^{-4}$ and smaller that edge is at 0.158, so the unscaled order holds for every scale from 0.158 to 3.198 — a window a factor of twenty wide, with s = 1 inside it.

The lower edge is not harmless either. On the repeated constraint at a coupling of $10^{-8}$, halving the scale to below the lower edge takes the error from $1.2 \cdot 10^{-3}$ to $0.16$; at a hundredth of the edge it is 9.7, an answer with no correct digit. Shrinking the constraints is what a code would do if it read the multipliers’ smallness on a consistent problem as a reason to scale them down — on the consistent problem at the same coupling the error moves only from $6 \cdot 10^{-9}$ to $4 \cdot 10^{-8}$, because there the constraints ask for nothing the order could turn into error. The window, not either of its edges, is the object the elimination describes: inside it, partial pivoting does what it does at s = 1; outside it on either side, it does something else, and which side is safe depends on what the third constraint demands.

The multipliers measure the wrong thing #

The earlier essays scaled the constraints by the ratio of the multipliers’ norm to the solution’s, because it was the multipliers’ size the route was blamed for. That ratio runs from $5.6 \cdot 10^{-4}$ on the consistent problems to $1.6 \cdot 10^{10}$ on the repeated one at the smallest coupling, while the switch sits at about three everywhere. Where the multipliers are large the ratio overshoots the scale partial pivoting needs by up to ten orders of magnitude, harmlessly, since any scale past the switch does the same; where they are small it is far below one and scaling by it would move the order the wrong way or not at all. A multiplier is a force found the multipliers growing in proportion to the constraint matrix’s conditioning; the switch does not grow with anything. The two quantities answer different questions — how hard the constraints push, and when a pivot rule changes its mind — and the second is the one the route’s accuracy depended on.

What the scale was doing all along #

The measurement completes the earlier essay’s correction. It found that the scale’s effect was a change of pivot; this one finds that the change happens at a scale set by two numbers in one column at one step, that those numbers are available from the elimination itself, and that crossing that scale buys exactly what changing that one pivot buys. Feasible and wrong found the saddle-point route returning an answer that satisfies every constraint and is wrong by $10^{-4}$; on these problems that answer is the unscaled order’s second pivot, and the cheapest repair is to take a constraint row there — or everywhere, first.

The reference was a method warned that the saddle-point conditions contain $A^{\mathsf T}A$ and so solve a squared problem in block form; nothing here changes that, and the constraints-first order’s errors at the smallest couplings, $10^{-6}$ to $10^{-4}$, are the squared conditioning’s price, not the order’s. The null-space route of the earlier essays, which never forms $A^{\mathsf T}A$, remains the more accurate one; the question here was only how to stop the saddle-point route losing more than it must.

What a code would do with it #

Put as a procedure, the measurement says this. A code that solves the saddle-point system with partial pivoting can record, during the elimination it is doing anyway, the largest candidate of each kind at each step; at the end it knows the window of constraint scales over which its pivot sequence would have been the same. If the window contains the scale it used, nothing about the order was decided by an accident of units. If a demanding constraint is present — a strain, or a near-repetition with its own datum — a solver can rescale to just past the upper edge and solve again, at the price of a second elimination, and expect the catastrophic loss to be gone. And on problems where the constraints ask for nothing new, the second solve buys nothing, which the window also cannot tell it.

Or a solver can eliminate the constraint rows first and skip all of it. On these forty-nine problems that order was at worst thirteen times worse than the best of five scaled orders — on problems where both errors are a few units of rounding and the best of five draws is partly luck — and thirty times better on four where the difference is real. It is the order the road that squares the problem would suggest for other reasons too: the constraint rows carry the problem’s hard structure and the normal-matrix rows its squared conditioning, and taking the hard structure out first keeps the squaring away from the steps where the constraints are decided. The window is a diagnostic; the order is a method.

What forty-nine problems do not show #

One least-squares matrix, two constraints, a third that nearly repeats the first, and one random direction for the near-repetition. A problem with many constraints has many constraint rows competing at many steps, and the interval of scales that keeps the unscaled order is bounded by the tightest of all of them; the prediction from one elimination still gives it exactly, by the argument above, but the switch might come at a scale where some later competition goes the other way, and a scale just past one switch could sit just short of the next. Partial pivoting is the only pivot rule measured; rook or complete pivoting compares rows and columns, and scaling columns as well would change the argument. The error is measured in the solution, not in the multipliers.

Still open: the multiplier as a rank decision, and many constraints #

A multiplier made of rounding. The question the earlier essays 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 repeated family the third constraint’s multiplier, in the constraints-first order, is made of the rounding of its datum. The prediction with a sign is that a rule deleting a constraint whose computed multiplier is below the datum’s rounding times the multiplier’s condition number separates a genuine demand from none down to strains of $10^{-11}$ at coupling $10^{-8}$, and fails below that, where the strain is smaller than the rounding it is compared with.

Many constraints. With m constraints the competition has m constraint rows at each step. The prediction is that the switch read off one elimination still agrees with bisection exactly, that it is decided at the step where the first normal-matrix row wins against a still-unreduced constraint row, and that a scale past it leaves the error within three times the constraints-first order’s on a larger share of problems than here, because with more constraints the constraint rows win more of the early steps anyway.