# pivoting in LU decomposition

I tried to find some reference on the net but couldn't find a good one. What is the advantage of pivoting in LU decomposition over regular LU decomposition? Is it something to do with matrix singular or not?

-
To summarize, LU decomposition with pivoting does not require matrix to have positive principal minors, it only requires matrix to be non-singular. So it is more stable. The answers below explain what stability means in greater detail. Thanks everyone. –  user957 Sep 13 '10 at 4:33

To further generalize Rahul's answer, any matrix that has a singular leading block cannot have an LU decomposition. By allowing pivoting (or in matrix factorization terms, allowing the multiplication of your original matrix by an appropriate permutation matrix), all matrices admit an LU decomposition. This is the explanation for pivoting in exact arithmetic.

In inexact arithmetic, the condition "singular" in the explanation above is replaced by the term "ill-conditioned". Every matrix has an associated condition number, which is defined as the product of the norm of the matrix and the norm of its inverse. In attempting to proceed with the LU decomposition of a matrix with an ill-conditioned leading block, you will hit a point where you have to divide by a small number (resulting in a number that may be much larger in magnitude than the matrix's original entries), which causes all sorts of trouble in the succeeding additions/subtractions that have to be done to finish the LU decomposition.

By pivoting, we avoid (or at the very least delay) the onset of encountering numbers much larger than the entries of the original matrix, which is one way precision is lost in the operations.

Of course, one could make the objection that the coefficients are badly scaled: for instance, if you have two equations in two unknowns, and you multiply both sides of any of the two equations by a number much smaller or much larger than the original coefficients, the solution to the system is still the same, but attempting to perform LU decomposition on the transformed system can be disastrous. This is where concepts like "scaled pivoting" comes in, where relative instead of absolute magnitudes are taken into account in the selection of pivots.

Then there are applications where "partial pivoting" (swapping of rows) is not enough; rank determination of a matrix, for instance, requires "complete pivoting" (swapping of both rows and columns).

In short, LU decomposition behaves much better with pivoting.

(I have been intentionally vague in some parts; you would do well to read Golub and Van Loan, as already recommended by jmoy, or the books "Matrix Decompositions" by Stewart or "Applied Numerical Linear Algebra" by Demmel for more rigorous versions of my explanation.)

-

The matrix $\begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}$ is as far from singular as you can get, yet it cannot be factorized into an LU decomposition without pivoting.

-

Pivoting is necessary to reduce the effect of rounding errors. In a world with exact arithmetic you wouldn't need pivoting. With a singular matrix it would just happen that you would not be able to proceed with computing the LU decomposition beyond a point.

But since finite computers must approximate reals with finite numbers of bits, every computation introduces a rounding error, and pivoting helps us control the accumulation of these errors.

I don't know of an online reference but most books on numerical analysis discuss this. An advanced source is Golub and van Loan's Matrix Computations.

-
It is not true that «in a world with exact arithmetic you wouldn't need pivoting»: see Rahul's answer. –  Mariano Suárez-Alvarez Aug 31 '10 at 15:10

Most of the invertible square matrices admit an $LU$ decomposition with $L$ a lower triangular matrix with 1’s onthe diagonal and $U$ is an upper triangular matrix (with arbitrary nonzero diagonal entries). Such an expression is easily seen to be unique. The set of invertible matrices admitting decomposition is open and dense in the group of n by n invertible matrices $GL(n)$. A matrix belongs to this set if and only if all its leading principal minors are nonzero as mentioned in the Wikipedia page) If the matrix does not belong to this set it still admits an $LU$ decomposition with pivoting $A = wLU$, with $L$ and $U$ as before and $w$ is a permutaion matrix.

The geometric origin of these constructions is given by means of the Bruhat cell decomposition of $GL(n)$

$GL(n) = \coprod_{w \in W} BwB$

where $B$ is the subgroup of invertibe upper triangular matrices, $W$ is the symmetric group, and $w$ is a permutation matrix.

When $w=w_0$ is the longest element of the symmetric group, given by an antidiagonal matrix with a unit antidiagonal, then: $B w_0 = w_0 w_0^{-1} B w_0 = w_0 N$, where $N$ is the group of upper triangular matrices. Thus the set of matrices admitting the regular LU decomposition is identified with the cell corresponding to the longest element. This cell which is dense in $GL(n)$ is called the big (Schubert) cell.

When, the matrix belongs to the big cell , but some of the leading principal minors are very small with respect to others, then the $LU$ decomposition will result big matrix elements, because the determinants of the principal minors appear in the denominators of the matrix elements of the $LU$ decomposition. In this case, it is customary to perform pivoting to move this matrix to another cell, to reduce the scale difference among the leading principal minors and gain numerical stability.

-