Advanced Review A very useful representation of the first stage of GE is from 1 to 0.Hence 1 ows that for thi A一1 1 a as an unstable algorithm. I C-baTlan that arreh thr The matrix C-baT is the Schur complement 1=k+1 of au in A. ore generally,it can be Partial pivoting.At the start of the kth stage,the hown tha the matrix A in Eq.(1)can expres kth and rth rows are interchanged,where 122 A21A 12,where A=A;this is the example symmetric positive definiteness and diagonal Thus an element of maximal magnitude in the pivot dominance abou the incding column is s cted as pivo interesting result som the sectoral fo for the where elements of Land U(see,e.g.,Ref 8,p.1): la: in other words.a det(A) ivot of maximal magnitude is der((1) det(A;1) isi Although elegant,these are of limited practical use PIVOTING AND NUMERICAL STABILITY ohot is choscn that is thearestn The asor partial pivoti In practical computation,it is not just zero pivots that lookine down a column and across a row for the small pivots.The problem largest element in modulus(Figure 1). sm pivot ey ca le to large artia pivoting requires O( possible loss of significance in the subtraction comp as arithmetic and so is a significant cost.The cost of rook pivoting is intermediate between the two and lepe on ne matr n of the and <.GE produces on the be captured in p nutation matrices Pand Q:it can be [-[e][6-+小-w hown that PAQ=LU with a unit lower triangula and upper with Q= r partia In floating point arithmetic the factors are approxi- would be obtai d if all the mated by were done at the start of the elimination and GE m-[oh 9- In ord to asses the succes of these pivoting a=[6]= the effects of all the roundingerrors committed during 232 e2011 John Wiley Sons,Inc Volume 3.Mayllune 2011 Advanced Review wires.wiley.com/compstats A very useful representation of the first stage of GE is 1 n − 1 A = 1 a11 aT n − 1 b C =  1 0 b/a11 In−1   a11 aT 0 C − baT/a11  . The matrix C − baT/a11 is the Schur complement of a11 in A. More generally, it can be shown that the matrix A(k) 22 in Eq. (1) can expressed as A(k) 22 = A22 − A21A−1 11 A12, where Aij ≡ A(1) ij ; this is the Schur complement of A11 in A. Various structures of A can be shown to be inherited by the Schur complement (for example symmetric positive definiteness and diagonal dominance), and this enables the proof of several interesting results about the LU factors (including some of those in the section ‘Structured Matrices’). Explicit determinantal formulae exist for the elements of L and U (see, e.g., Ref 8, p. 11): ij = det A([1: j − 1, i], 1: j)  det(Aj) , i ≥ j, uij = det A(1: i, [1: i − 1, j]) det(Ai−1) , i ≤ j. Although elegant, these are of limited practical use. PIVOTING AND NUMERICAL STABILITY In practical computation, it is not just zero pivots that are unwelcome but also small pivots. The problem with small pivots is that they can lead to large multipliers mik. Indeed if mik is large then there is a possible loss of significance in the subtraction a (k) ij − mika (k) kj , with low-order digits of a (k) ij being lost. Losing these digits could correspond to making a relatively large change to the original matrix A. The simplest example of this phenomenon is for the matrix A =  1 1 1  , where we assume 0 << u. GE produces  1 1 1  =  1 0 1/ 1   1 0 −1/ + 1  = LU. In floating point arithmetic the factors are approxi￾mated by fl(L) =  1 0 1/ 1  =: L, fl(U) =  1 0 −1/  =: U, which would be the exact answer if we changed a22 from 1 to 0. Hence LU = A + A with A∞/A∞ = 1/2 u. This shows that for this matrix GE does not compute the LU factorization of a matrix close to A, which means that GE is behaving as an unstable algorithm. Three different pivoting strategies are available that attempt to avoid instability. All three strategies ensure that the multipliers are nicely bounded: |mik| ≤ 1, i = k + 1: n. Partial pivoting. At the start of the kth stage, the kth and rth rows are interchanged, where |a (k) rk | := max k≤i≤n |a (k) ik |. Thus an element of maximal magnitude in the pivot column is selected as pivot. Complete pivoting. At the start of the kth stage rows k and r and columns k and s are interchanged where |a(k) rs | := max k≤i,j≤n |a (k) ij |; in other words, a pivot of maximal magnitude is chosen over the whole remaining submatrix. Rook pivoting. At the start of the kth stage, rows k and r and columns k and s are interchanged, where |a(k) rs | = max k≤i≤n |a (k) is | = max k≤j≤n |a (k) rj |; in other words, a pivot is chosen that is the largest in magnitude in both its column (as for partial pivoting) and its row. The pivot search is done by repeatedly looking down a column and across a row for the largest element in modulus (Figure 1). Partial pivoting requires O(n2) comparisons in total. Complete pivoting requires O(n3) comparisons, which is of the same order of magnitude as the arithmetic and so is a significant cost. The cost of rook pivoting is intermediate between the two and depends on the matrix. The effect on the LU factorization of the row and column interchanges in these pivoting strategies can be captured in permutation matrices P and Q; it can be shown that PAQ = LU with a unit lower triangular L and upper triangular U (with Q = I for partial pivoting). In other words, the triangular factors are those that would be obtained if all the interchanges were done at the start of the elimination and GE without pivoting were used. In order to assess the success of these pivoting strategies in improving numerical stability we need a backward error analysis result. Such a result expresses the effects of all the rounding errors committed during 232  2011 John Wiley & Son s, In c. Volume 3, May/June 2011