tridiagonal

Tridiagonal refers to a type of matrix in linear algebra that has nonzero entries only on three diagonals: the main diagonal, the diagonal immediately above it (the superdiagonal), and the diagonal immediately below it (the subdiagonal). All other entries are zero. For an n-by-n matrix A, the main diagonal entries are often denoted a_i = A[i,i] (i = 1,...,n), the superdiagonal entries b_i = A[i,i+1] (i = 1,...,n-1), and the subdiagonal entries c_i = A[i,i-1] (i = 2,...,n). The matrix is tridiagonal if a_i, b_i, and c_i are the only possibly nonzero elements.

If b_i = c_i for all i, the matrix is symmetric; symmetric tridiagonal matrices arise frequently in numerical problems and have real eigenvalues with orthogonal eigenvectors. A matrix is Toeplitz-tridiagonal if the diagonals are constant (the same a on the main diagonal and the same b on both off-diagonals).

Applications include the finite difference discretization of one-dimensional second-order differential operators, such as the 1D Poisson equation, where the discrete operator yields a symmetric tridiagonal system. Tridiagonal systems can be solved efficiently with the Thomas algorithm in linear time, O(n), much faster than general dense solvers. General dense LU methods also work but with higher cost.

In linear algebra, tridiagonal matrices frequently appear as the result of matrix factorizations or as the form preserved under Krylov subspace methods such as the Lanczos process, which produces a tridiagonal representation of a matrix.