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

A 11 A 12 A 13 A 14
A 21 A 22 A 23 A 24
A 31 A 32 A 33 A 34
A 41 A 42 A 43 A 44

U 11
L 21
L 31
L 41

U 12
U 22
L 32
L 42

U 13
U 23
U 33
L 43

U 14
U 24
U 34
U 44

⇒

FIGURE B.1
In-place computation of the L and U values assuming no row exchanges.

When performing the decomposition, the values of the input matrix can be replaced with the values
of L and U ( Figure B.1 ). Notice that the diagonal elements of the L matrix do not have to be stored
because they are routinely set to one. If row exchanges take place, then the rows of the matrices in
Figure B.1 will be mixed up. For solving the linear system of equations, the row exchanges have
no effect on the computed answers. However, the row exchanges are recorded in a separate array
so that they can be undone for the formation of the inverse matrix. In the code that follows
( Figure B.2 ), the LU decomposition approach is used to solve a system of linear equations and is broken
down into several procedures. These procedures follow those found in Numerical Recipes [ 16 ] .
After the execution of LUdecomp, the A matrix contains the elements of the L and U matrices. This
matrix can then be used either for solving a linear system of equations or for computing the inverse of a
matrix. The previously discussed simple substitution methods can be used to solve the equations that
involve triangular matrices. In the code that follows, the subroutine LUsubstitute is called with the
newly computed A matrix, the dimension of A , the vector of row swaps, and the right-hand vector
(i.e., the b in Ax ¼ b ).
One of the advantages of the LU decomposition is that the decomposition matrices can be reused if
the only change in a system of linear equations is the right-hand vector of values. In such a case, the
routine LUdecomp only needs to be called once to form the LU matrices. The substitution routine,
LUsubstitute, needs to be called with each new vector of values (remember to reuse the A matrix that
holds the LU decomposition).
To perform matrix inversion, use the L and U matrices repeatedly with the b matrix holding
column-by-column values of the identity matrix. In this way the inverse matrix is built up column
by column.

B.1.2 Singular value decomposition
Singular value decomposition (SVD) is a popular method used for solving linear least-squares prob-
lems ( Ax ¼ b , where the number of rows of A is greater than the number of columns). It gives the user
information about how ill conditioned the set of equations is and allows the user to step in and remove
sources of numerical inaccuracy.
As with LU decomposition, the first step decomposes the A matrix into more than one matrix
( Eq. B.16 ). In this case, an M NA matrix is decomposed into a column-orthogonal M NU matrix,
a diagonal N MW matrix, and an N N orthogonal V matrix.

A ¼ UWV T

(B.16)

The magnitude of the elements in the W matrix indicates the potential for numerical problems.
Zeros on the diagonal indicate singularities. Small values (where small is user defined) indicate the