The question begins when I read the following paper.
- Carlotta Giannelli, Bert Jüttler, Hendrik Speleers, THB-splines: the truncated basis for hierarchical splines, Computer Aided Geometric Design, Volume 29, Issue 7, October 2012.
In one section, they apply the Cholesky decomposition of matrices and get the following two figures.
The black dot in the figures shows non-zero number. The paper said that the second figure is better than the first figure. I am not sure why they get this result. Forgive me for my ignorance, is there any benefit just because the second figure shows more sparsity. Thank you very much.
The short answer is that the computation could be faster with sparse matrix data structures and the ordering that results in the Cholesky factor shown on the right side of the figure. This is about performance rather than accuracy.
The rows and columns of a sparse positive definite matrix can be reordered in various ways to reduce the number of nonzero entries created in the Cholesky factor. Since many of the entries in the Cholesky factor will be 0, we can save storage by storing only the nonzero entries and the information needed to know where those entries are located.
Since it takes more work (both floating-point operations and writes to memory) to compute a larger number of nonzero entries in the Cholesky factor, the factorization process is faster when an ordering is used that reduces "fill-in" in the Cholesky factor.
Also, in using the Cholesky factor to solve a system of equations, there is less work with a sparse Cholesky factor. The work (floating-point operations and memory reads/writes) is linear in the number of nonzero entries in the Cholesky factor.
It is also true that in some cases you may only have enough memory for an optimized sparse Cholesky factor. Thus you may be able to solve larger problems with a sparse Cholesky factor.
Note: The two Cholesky factors shown in this figure are actually not very good examples. The sparser factor is still about 50% dense, so it's unlikely that using Cholesky factorization would actually be faster than using BLAS/LAPACK dense linear algebra computations. In practice, sparse Cholesky factorization is used on matrices that are much more sparse than this (e.g. less than 1% dense.)