Sparse matrices vs. small matrices

In the previous two chapters we have introduced methods based on completely different principles: finite differences rest upon the replacement of derivatives by linear combinations of function values but the idea behind finite elements is to approximate an infinite-dimensional expansion of the solution in a finite-dimensional space. Yet the implementation of either approach ultimately leads to the solution of a system of algebraic equations. The bad news about such a system is that it tends to be very large indeed; the good news is that it is highly structured, usually very sparse, hence lending itself to effective algorithms for the solution of sparse linear algebraic systems, the theme of Chapters 11–15.

In other words, both finite differences and finite elements converge fairly slowly (hence the matrices are large) but the weak coupling between the variables results in sparsity and in practice algebraic systems can be computed notwithstanding their size. Once we formulate the organizing principle of both kinds of method in this manner, it immediately suggests an enticing alternative: methods that produce small matrices in the first place. Although we are giving up sparsity, the much smaller size of the matrices renders their solution affordable.

How do we construct such ‘small matrix’ methods? The large size of the matrices in Chapters 8 and 9 was caused by slow convergence of the underlying approximations, which resulted in a large number of parameters (grid points or finite element functions).