Background Information and Techniques - Computer Animation: Algorithms and Techniques - page 410

For the third column of A
U 13 ¼ A 13
L 21 U 13 þ U 23 ¼ A 23
L 31 U 13 þ L 32 U 23 þ U 33 ¼ A 33
L 41 U 13 þ L 42 U 23 þ L 43 U 33 ¼ A 43

(B.14)

For the fourth column of A
U 14 ¼ A 14
L 21 U 14 þ U 24 ¼ A 24
L 31 U 14 þ L 32 U 24 þ U 34 ¼ A 34
L 41 U 14 þ L 42 U 24 þ L 43 U 34 þ U 44 ¼ A 44

Notice a two-phase pattern in each column in which terms from the U matrix from the first row to
the diagonal are determined first, followed by terms from the L matrix below the diagonal. This pattern
can be generalized easily to matrices of arbitrary size [ 16 ], as shown in Equation B.15 . The compu-
tations for each column j must be completed before proceeding to the next column.

X
K¼ 1 L ik U kj

U ij ¼ A ij for i ¼ 1 ; ...; j

!

(B.15)

j 1
k¼ 1 L ik U kj

1
U ij

L ij ¼ Aij i ¼ j þ ; ...; n

for 1

So far this is fairly simple and easy to follow. Now comes the complication— partial pivoting .
Notice that some of the equations require a division to compute the value for the unknown. For this
computation to be numerically stable (i.e., the numerical error less sensitive to particular input values),
this division should be by a relatively large number. By reordering the rows, one can exert some control
over what divisor is used. Reordering rows does not affect the computation if the matrices are viewed as
a system of linear equations; reordering obviously matters if the inverse of a matrix is being computed.
However, as long as the reordering is recorded, it can easily be undone when the inverse matrix is
formed from the L and U matrices.
Consider the first column of the 4 4 matrix. The divisor used in the last three equations is U 11 ,

which is equal to A 11 . However, if the rows are reordered, then a different value might end up as A 11 .So
the objective is to swap rows so that the largest value (in the absolute value sense) of A 11 , A 21 , A 31 , A 41
ends up at A 11 , which makes the computation more stable. Similarly, in the second column, the divisor
is U 22 , which is equal to A 22

( L 21 U 12 ). As in the case of the first column, the rows below this are
checked to see if a row swap might make this value larger. The row above is not checked because that
row was needed to calculate U 12 , which is needed in the computations of the rows below it. For each
successive column, there are fewer choices because the only rows that are checked are the ones below
the topmost row that requires the divisor.
There is one other modification to partial pivoting. Because any linear equation has the same solution
under a scale factor, an arbitrary scale factor applied to a linear equation could bias the comparisons made
in the partial pivoting. To factor out the effect of an arbitrary scale factor when comparing values for the
partial pivoting, one scales the coefficients for that row, just for the purposes of the comparison, so that
the largest coefficient of a particular row is equal to one. This is referred to as implicit pivoting .