Game Development Reference

In-Depth Information

for
(int k = 0; k < n; k++)

m[k * n + i] -= m[k * n + j] * factor;

}

}

// Perform backward substitution.

for
(
int
i = n - 1; i >= 0; i--)

{

float
sum = r[i];

for
(
int
k = i + 1; k < n; k++) sum -= m[k * n + i] * r[k];

r[i] = sum / m[i * n + i];

}

result =
true
;

exit:

delete
[] rowNormalizer;

return
(result);

}

16.2.3 LU Decomposition

Suppose again that we have a linear system of
n
equations that can be written as

=

Mxr
. If we can find two matrices
L
and
U
, where
L
is a lower triangular ma-

trix and
U
is an upper triangular matrix, such that

LUM
, then the linear system

=

Mxr
can be written as

=

(

)
=

L Ux

r
.

(16.12)

Mxr
into the problems of

=

This transforms the problem of solving the system

Ux y
. The solutions to

both of these systems is easily calculated using forward substitution (for

Lyr
and then solving the system

=

=

solving the system

Lyr
)

=

Ux y
).

The pair of triangular matrices
L
and
U
whose product yields
M
is called the

LU decomposition
of
M
. Once determined, the LU decomposition of a matrix can

be repeatedly used to solve linear systems having the same coefficient matrix
M

and different constant vectors
r
. In particular, we can calculate the
j
-th column of

1

=

and backward substitution (for

−

M

by setting
i

r δ

=

, where
δ
is the Kronecker delta symbol.

ij

We need an algorithm that determines the matrices
L
and
U
such that

Search Nedrilad ::

Custom Search