Pivoted LU and growth factors

In the convention PA=LU, P records the final row permutation, L is unit lower triangular, and U is upper triangular. Solving Ax=b means first solving Ly=Pb and then Ux=y. Other software conventions write A=PLU using a different permutation meaning, so the displayed equation is more informative than a variable name. When a later elimination step exchanges rows, the previously formed multiplier columns must be exchanged consistently as well; otherwise the claimed factors no longer multiply back to the permuted original matrix.

Partial pivoting selects an entry of largest magnitude in the active column and moves its row into the pivot position. In exact arithmetic, every multiplier below that pivot then has magnitude at most one. A zero active column signals singularity in the remaining square block rather than a pivoting choice that can repair rank. Pivoting by columns as well may improve other properties, but requires tracking unknown permutations. In sparse systems, pivot selection also affects fill, so numerical robustness and storage cost interact.

Define the growth factor as the largest entry magnitude encountered at the starts of elimination stages divided by the largest original entry magnitude. It is at least one under this convention. Large growth matters because rounding error bounds scale with intermediate magnitudes, not merely the original data. Partial pivoting bounds multipliers but repeated subtraction can still accumulate large trailing entries. In exact arithmetic, its worst-case growth is bounded by two to the power n−1, and carefully structured examples attain that exponential bound.

In many computations growth is much smaller, which helps explain why partial pivoting is effective in practice. This empirical tendency is not a universal small-growth theorem. Backward error analysis typically contains dimension factors, unit roundoff, and growth or products involving the computed factors. It should not be reduced to an unconditional claim of tiny error for every matrix. Conversely, a large worst-case bound does not prove that a particular computation is inaccurate; evaluate the actual residual and relevant diagnostics.

A well-conditioned matrix can suffer substantial elimination growth, and an ill-conditioned triangular matrix can need no elimination at all. Growth is an algorithm-path property; conditioning is a property of the chosen problem and perturbation model. Their distinction is practical: changing the pivot strategy can alter growth without changing the original matrix's condition number. Scaling can also change pivot comparisons and intermediate magnitudes. It should be chosen with an explicit relationship to the original variables and uncertainties.

After factorization, reuse L, U, and the permutation for multiple right-hand sides instead of recomputing an inverse. Check factorization or solve residuals using the same permutation convention. A determinant formed from pivot products may underflow or overflow and is a poor standalone rank diagnostic. A tiny pivot relative to an appropriate scale deserves a condition estimate, while a zero pivot requires a rank-aware strategy. For a symmetric positive definite matrix, Cholesky uses its structure more directly than generic LU, but that choice requires positive definiteness rather than just symmetry.