A sparse matrix has few nonzero matrix elements in each row or column compared with its dimension. Algorithms normally require an efficient oracle that lists the positions and values of those entries.
A band matrix has nonzero entries confined to a band around its main diagonal. The nonnegative integers in the displayed condition are its lower and upper bandwidths. A tridiagonal matrix has . Storing only the band reduces memory use; banded Gaussian elimination can exploit the same structure when the pivoting assumptions permit it.
Compressed sparse storage keeps a sparse matrix as numerical nonzero values, their row or column indices, and pointers to the start of each compressed column or row. It avoids allocating all entries. A sparse direct solver must additionally allocate possible fill-in predicted by symbolic factorization, because elimination can create entries absent from the input.
The bandwidth in this convention is the largest distance from the main diagonal of a nonzero matrix entry. A symmetric positive-definite matrix of bandwidth can be factored using operations and storage; its Cholesky decomposition does not introduce entries outside that band. A variable permutation changes bandwidth, so it is a property of both the sparsity pattern and its ordering.
