Sparse, banded matrix and memory optimization

Sparse matrix: a matrix in which most entries are zero. Stiffness matrices of FEM are sparse because a node is connected only to the nodes of neighbouring elements.

Banded matrix: a matrix whose non-zero entries lie in a narrow band about the main diagonal, i.e. $a_{ij}=0$ for $|i-j|>b$. The half-bandwidth is

$$b=(\text{max difference of node numbers in an element}+1)\times \text{dof per node}$$

A symmetric matrix of order $n$ and half-bandwidth $b$ is stored with only $n\times b$ numbers instead of $n^2$.

 x x . . .
 x x x . .      band along the
 . x x x .      diagonal, zeros
 . . x x x      outside
 . . . x x

Memory optimisation: reducing the memory needed to store and solve $[K]\{U\}=\{F\}$. Techniques are:

• store only the upper triangle (symmetry);
• store only the band (banded storage) or the skyline profile;
• store only non-zero terms with index arrays (sparse storage);
• renumber nodes to minimise bandwidth. Less memory also gives fewer operations: the cost of banded elimination is about $n b^2$ instead of $n^3$.