A Sampler of Useful Computational Tools for Applied Geometry, Computer Graphics, and Image Processing

86 Solution of Linear Systems

20 40 60 80 100

10

20

30

40

50

60

70

80

90

100

−1

−0.5

0

0.5

1

1.5

2

2.5

3

3.5

4

Figure 6.1: Sparsity pattern of a 100 × 100 discrete two-dimensional

Laplacian on a uniform mesh.

We end this part of the discussion with a note of caution. In-

verses of matrices are almost always entirely dense. For example,

for the Laplacian matrix, we have that the Cholesky factors are

narrow-banded, but the inverse is dense; see Figure 6.2. For this

reason, there is a fundamental difference between solving a lin-

ear system using factorizations, and solving it by computing the

inverse of the matrix explicitly.

Iterative methods

Direct methods are extremely