Game Development Reference
In-Depth Information
Figure 10.6. Minimizing the number of nonzero elements. The first plot shows S without
ordering. The second plot shows L without ordering. The third plot shows S after ordering.
And the last plot shows L after ordering S .
Equation (10.22) as
x = S 1 b.
Unfortunately, that leads to no improvement. The main drawback is that although
S is symmetric, S 1 is not, and S 1 b would have an O ( n 2 ) complexity.
Instead, it is better to precompute the Cholesky factorization of S :
S = LL T ,
where L is a lower triangular matrix. Then, solve Equation (10.22) using the
Gauss elimination method.
The Cholesky factorization is performed in a precomputation stage. Much
literature exists on this subject, which we are not going to describe here. We do
know that the number of zero elements in L must be maximized. A good way
of maximizing the number of zeroes is ordering the system matrix S beforehand.
We recommend the use of the minimum degree algorithm . Figure 10.6 shows the
nonzero elements in S and L for a particular model. The dots show the nonzero
elements. It can be appreciated that the minimum degree algorithm drastically re-
duces the number of nonzero elements in the Cholesky factorization. We suggest