Two condition numbers of one matrix

The essay that introduced the componentwise condition number did so as a repair for an embarrassment: κ₂ can be changed by a factor of 10⁶ by measuring one variable in millimetres instead of kilometres, which means it is partly a statement about somebody’s units. The componentwise number is invariant to that rescaling, so it is the honest version of the same quantity.

That reading makes it sound like a refinement — usually a bit smaller, occasionally worth computing. On one matrix in this collection the two numbers are 3.04·10¹³ and 13.25, and only one of them says anything about the error.

The two definitions, side by side #

The normwise condition number of a solve is

κ(A) = ‖A‖ · ‖A⁻¹‖

and the bound it supports is: if the matrix is perturbed to A + ΔA with ‖ΔA‖ ≤ ε‖A‖, the solution moves by at most κ(A)·ε relatively. The hypothesis is a bound on the norm of the perturbation and says nothing about where it is.

Skeel’s componentwise number is

cond(A, x) = ‖ |A⁻¹| |A| |x| ‖ / ‖x‖

and the bound it supports is: if each entry is perturbed by at most ε times its own magnitude — |ΔAᵢⱼ| ≤ ε|Aᵢⱼ| — the solution moves by at most cond(A, x)·ε relatively. The hypothesis is a bound on each entry relative to that entry.

The second is always at most the first times a scaling factor, and it can be very much smaller. When it is, the difference is a fact about the matrix’s scales, and the ratio is a measure of how much of κ₂ is a statement about a perturbation nobody would ever make.

The matrix #

The constraint field’s fifth essay supplies it. A Newton step of an interior-point method, written in its unreduced form

[ H Cᵀ ] [ C −D⁻¹ ]

where D = Z/S is a diagonal whose entries run to 1/μ on the active constraints and to μ on the inactive ones, so −D⁻¹ has entries spanning 1/μ². As μ falls the diagonal separates by twenty-four orders, which is what makes the matrix ill conditioned in the normwise sense.

The entries are not uniform in scale and they are not uniform by construction: the matrix has a block of ordinary numbers, a block of enormous ones and a block of tiny ones, and which is which is known. That is exactly the situation the two definitions disagree about.

The measurement #

Both numbers, at four barrier parameters, on the augmented form and on the condensed form:

μ κ₂ augmented componentwise componentwise, condensed 10⁰ 2.90·10¹ 22.54 1.35·10² 10⁻⁴ 3.02·10⁵ 13.18 1.31·10⁶ 10⁻⁸ 3.04·10⁹ 13.25 1.32·10¹⁰ 10⁻¹² 3.04·10¹³ 13.25 1.32·10¹⁴

For the augmented matrix the componentwise number is 13.25 and does not move while κ₂ climbs thirteen decades. For the condensed matrix the two agree to within a factor of two at every μ.

And the measured error follows the componentwise number: 9.4·10⁻¹⁶ for the augmented form at μ = 10⁻¹², which is 13.25 · u to within four orders, against a κ₂·u of 3.4·10⁻³.

So the two numbers are not a refinement of one another. On this matrix they are different answers to different questions, and one of the questions is the one being asked.

What “13.25” is a number about #

A flat line at 13.25 across thirteen decades invites the question of where 13.25 comes from, and the answer is that it is about the size of the problem rather than about the barrier.

cond(A, x) = ‖ |A⁻¹||A||x| ‖ / ‖x‖ is at least one for any matrix, and the tempting reading of 13.25 on a 14 × 14 matrix is that it is counting terms — what a fourteen-term sum of same-signed contributions produces — which would predict about seventeen at 18 × 18 and less at smaller sizes.

The same measurement across shapes, all at μ = 10⁻¹²:

It is not the dimension. cond ÷ N runs from 0.76 to 4.78 with no trend; the 18 × 18 gives 13.75 where seventeen was predicted; and the smallest matrix in the table gives 20.3 where the prediction says the number should fall. Two matrices of the same size, 14 × 14, differ by a factor of five on the active-constraint count alone.

And the finding survives all of it. The number is between 13 and 66 at every shape while κ₂ is 10¹³ to 10¹⁴ — so the thirteen-order gap is a property of the form rather than of the one problem it was measured on, which is a stronger claim than the term-counting story was making and does not depend on it. It is flat in μ on every shape too, constant to four digits from μ = 10⁻⁴ downwards.

What the height is a function of is not settled by this measurement, and saying so is better than supplying the wrong answer. It moves with the active-constraint count, it moves with n and p separately, and it does not move with N. Whatever it is, it is bounded within a couple of orders across every shape tried, which is all the argument needs.

The one place the number is not flat is at μ = 1, where the 14 × 14 reads 22.5 rather than 13.2 — and the reading that the separation helps the componentwise number does not survive the other shapes either. It helps on three and hurts on three: 22.54 → 13.25, 23.66 → 20.31 and 16.31 → 13.75 against 15.49 → 57.42, 22.38 → 65.78 and 34.03 → 38.23. The separation does something small and shape-dependent to a number that stays under a hundred, and thirteen orders to one that does not.

Why that correction leaves the essay stronger #

It is worth being explicit about which way the repair runs, because a section that removes an explanation usually weakens the thing explained and here it does the opposite.

The term-counting story made the good behaviour contingent. If 13.25 were the count of terms in a fourteen-term sum, then a reader would be right to ask what happens on a matrix where the terms do cancel, or where there are a great many more of them — and the answer would have to be that the componentwise number rises with the problem and the gap eventually closes. The essay’s own conclusion would then be a statement about small problems.

The measurement says the height does not track the size at all. Doubling the dimension from 18 to 36 moves it from 13.75 to 38.2 while quadrupling the number of terms in every sum, and halving it from 14 to 6 moves it up from 13.25 to 20.3. Whatever the height is, it is not accumulating with the work, and every shape tried lands in a range of five where κ₂ spans none at all — 10¹³ to 10¹⁴ at every one of them.

So the claim that can be made is the one the essay wants and could not previously support: on this form, at any shape, the componentwise number is a small number and κ₂ is not, and the thirteen orders between them are not an artefact of the fourteen-by-fourteen the figure happens to draw. The explanation that was offered would have been a reason to doubt that; its absence is not.

The size behaves the same way, which took measuring rather than assuming — the obvious guess is that a componentwise number counts terms and so grows with the dimension.

The reading at ten is higher than at four by a factor of four, which looks like the trend the guess predicted — until the next stop, where it falls again.

Neither parameter produces a trend, and that is the result rather than a failure to find one. Across every combination drawn the componentwise number stays between 11 and 48 while κ₂ stays near 10¹³ — eleven or twelve orders apart at every stop, on the same matrices. The generator asserts the band directly rather than by inspection: max(...sk) < 100, “and it is a two-figure number at every μ”, which is a claim that would fail on the first frame if the number tracked either knob.

So the sentence to carry is not that the componentwise number is smaller. It is that it is not a function of the things κ₂ is a function of. κ₂ moves by an order of magnitude across these draws — 5.4·10¹² at four unknowns to 9.8·10¹³ at ten — and the componentwise number moves within a factor of four with no relationship to it. Two numbers computed from one matrix, and only one of them is answering a question about the matrix’s shape.

Why the perturbation a factorisation makes is componentwise #

The reason the smaller number is the relevant one is a fact about backward stability rather than about condition numbers, and it is worth stating precisely because the usual statement is normwise and hides it.

A backward-stable factorisation returns the exact factors of A + ΔA with ‖ΔA‖ ≤ cn·u·‖A‖. That is the normwise statement, and it is what the backward error essays quote. The finer statement, which holds for Gaussian elimination and for symmetric indefinite factorisation with a bounded growth factor, is componentwise: |ΔAᵢⱼ| ≤ cn·u·(|L||U|)ᵢⱼ, and in the absence of growth that is |ΔAᵢⱼ| ≲ cn·u·|Aᵢⱼ|.

Each entry is perturbed by an amount relative to itself. The enormous entries of −D⁻¹ are perturbed by enormous absolute amounts that are tiny relative to themselves; the ordinary entries of H and C are perturbed by ordinary tiny amounts. That is a componentwise perturbation, and the number that bounds its effect is the componentwise one.

A normwise perturbation of the same norm is permitted to put its entire budget on the smallest entry — a change of 10⁻² to an entry of size 10⁻² — which no factorisation would ever make and which is what κ₂ = 3·10¹³ is a worst case over.

And why the elimination destroys it #

The condensed form is H + CᵀDC, and its two condition numbers agree. The structure that protected the augmented form is gone, and the reason is arithmetic rather than algebraic.

An entry of CᵀDC is a sum over the constraints: Σₖ Cₖᵢ Dₖ Cₖⱼ. Some terms in that sum are of size 1/μ and some are of size μ, and the result is dominated by the first. So an entry of the condensed matrix is a huge number that has a small number hidden inside it, and perturbing the entry by ε times itself perturbs the hidden contribution by ε times the huge number — which is enormous relative to the hidden part.

The information about scale was in the separateness of the entries, and the elimination summed them. What is lost is not accuracy at the moment of summing — the sum is computed to full relative precision — but the ability of any later perturbation to respect the two scales, because after the sum they are no longer distinguishable.

That is a general lesson about eliminations and it is not confined to this family: an elimination is a change of variables, and a change of variables can destroy structure that the original variables had. The tensor field found the same shape when an all-orthogonality measurement was scaled by the wrong thing, and the structured backward error essays found it when a nearby problem turned out not to be a problem of the right kind.

What each number is good for #

Neither is the right number in general, and saying which question each answers is more useful than picking a winner.

κ₂ is right for an error in the data. A measured H, a C assembled from noisy geometry, a right-hand side from an instrument: those errors are not proportional to the entries they land on, and against them the matrix really is as sensitive as κ₂ says. A page that concluded “κ₂ is misleading” would be wrong about the case it was invented for.

The componentwise number is right for an error the arithmetic makes, which is the case this site is about. It is also right for an error in data that is known relatively — a measurement quoted to three significant figures perturbs each entry proportionally.

And there is a third case neither covers: a structured perturbation that has to preserve a pattern. The structured backward error of a Toeplitz solve is a different number again, because the perturbation is required to stay Toeplitz. Each of the three is a worst case over a different set, and the sets are nested.

The third quantity in the identity #

The site’s spine is forward ⪅ condition × backward, and this page has been about replacing one factor. The other factor changes too, and the two changes are the same change seen twice.

The normwise backward error of a computed x is ‖Ax − b‖ / (‖A‖‖x‖ + ‖b‖), and its componentwise cousin divides each component of the residual by (|A||x| + |b|)ᵢ instead. For the augmented matrix the second is at the rounding level while the first is too, because both are measuring an algorithm that behaved well — the backward error is the easy half here.

What the pairing means is that the identity has to be used consistently: a componentwise condition number multiplies a componentwise backward error, and a normwise one multiplies a normwise one. Mixing them gives a bound that is not a bound in either sense. The reason the normwise product is so far above the measured error on this matrix is not that the bound is weak — it is a perfectly good bound on the wrong quantity — but that the pair being multiplied does not describe what happened.

That is the same failure this field has recorded once before, from the other direction, when a backward error turned out to promise a nearby problem of the wrong kind. The identity is exact; what it is about depends entirely on which set of perturbations both halves are worst cases over.

What it costs to compute #

cond(A, x) needs |A⁻¹|, and forming an inverse is the operation this collection has an essay against. So the definition is not directly usable, which is one reason libraries print κ₂ instead.

What is usable is an estimate. The quantity ‖ |A⁻¹||A||x| ‖ is the norm of A⁻¹ applied to a known nonnegative vector, so it is one solve with the already-computed factors per estimate, and the standard condition estimator that this field has already priced applies unchanged. That makes it about as expensive as the normwise estimate every library already computes.

The measurement on this page forms the inverse, because the matrices are fourteen by fourteen and the point is the exact value rather than the practicality. On a real problem the estimate is what would be used, and it inherits the estimator’s own failure mode — a matrix on which it under-reports by an arbitrary factor.

Which of the two a reader should print #

The practical conclusion is not “use the componentwise number”, because on most matrices the two agree and the extra solve is wasted. It is a rule about when they can disagree, and the rule has a shape that is easy to check.

They can disagree only when the entries of the matrix span many orders of magnitude and the spread is structural rather than accidental — when the matrix has blocks or rows or columns of different scale, and those scales came from the problem’s construction rather than from noise. A matrix whose entries are all within a few orders has cond(A, x) within a small factor of κ∞(A) and nothing to learn.

That test is cheap: the ratio of the largest entry to the smallest nonzero one, which any code already knows. If it is under 10⁶ the two numbers agree; if it is 10²⁴, as it is here, they may not, and the componentwise estimate is worth the solve.

The same test says where else on this site the question would have been worth asking. A graded matrix in the relative-accuracy essays has exactly this shape, and its eigenvalues turn out to have relative accuracy nobody expected for exactly this reason; so does a scaled system in the units essay. Three places, one diagnostic.

The refusal #

The reading to close is the one this essay’s own predecessor invites: the componentwise condition number is a refinement of the normwise one — usually a bit smaller, occasionally worth computing, and never a different answer. Every word of that is a reasonable summary of the earlier essay, and it is what makes the case here worth measuring.

The assertion is fed both numbers for the augmented matrix at μ = 10⁻¹² and required to reject the claim that they agree within six orders. They are 3.04·10¹³ and 13.25, a ratio of 2.3·10¹².

Two further refusals guard the other direction. One is fed the claim that eliminating a block keeps the componentwise conditioning, and required to refuse — the whole second half of the page rests on the elimination being what destroys it. The other is fed the claim that a condition number of 10¹³ costs thirteen digits, and required to refuse: the standard bound is an upper bound and this matrix is twelve orders under it.

A note on which norm #

Both definitions above were written with a norm left unspecified, and the choice is not free.

The componentwise bound is naturally an infinity-norm statement, because it comes from bounding each component of the error separately and then taking the largest. Mixing it with a two-norm condition number — which is what a code that prints κ₂ and then quotes a componentwise bound would be doing — introduces a factor of √n that is harmless at n = 14 and is not at n = 10⁶.

The measurements on this page use the infinity norm throughout for the componentwise number and the two-norm for κ₂, which is the convention each is usually quoted in, and the ratio between them for a matrix of this size is under four. That is well inside the thirteen orders being reported, so nothing here turns on it — but a reader carrying the numbers elsewhere should carry the norms with them.