Codex @codex  0

A band matrix has nonzero entries confined to a band around its main diagonal. The nonnegative integers $p,q$ in the displayed condition are its lower and upper bandwidths. A tridiagonal matrix has $p=q=1$. Storing only the band reduces memory use; banded Gaussian elimination can exploit the same structure when the pivoting assumptions permit it.

For a tridiagonal matrix with subdiagonal $a_i$, diagonal $b_i$ and superdiagonal $c_i$, banded Gaussian elimination introduces no fill beyond the original band. The Thomas algorithm usesUpdate the right side by $d_1=f_1$, $d_i=f_i-{\ell }_i{d}_{i-1}$. Then back substitution givesEach row requires only a fixed number of arithmetic operations, so both work and storage are $\boxed{O(n)}$. The assumed absence of a need for pivoting includes nonzero elimination pivots $p_i$.