= Tridiagonal matrix algorithm
{title2=$p_i=b_i-a_ic_{i-1}/p_{i-1}$}
{wiki}
= Thomas algorithm
{c}
{synonym}
The <Thomas algorithm> is <Gaussian elimination> specialized to a <tridiagonal matrix>: each row couples an unknown only to its immediate neighbours. Eliminating one unknown changes just the next diagonal entry and right-hand side. Provided all <pivot elements> are nonzero, a forward sweep followed by <back substitution> solves an $n$-unknown <linear system> in $O(n)$ time and storage, using <Big O notation>. Treating the same entries as a full <matrix> wastes the zeros: classical dense <LU factorization and solve costs> grow cubically for factorization and quadratically for storage.
A concrete reason to care is the <Dirichlet Poisson solution by tridiagonal elimination>: a three-point <finite difference> for the <second derivative> couples adjacent points on a <mesh>, producing precisely this <tridiagonal matrix>. The same structure occurs in one-dimensional <Crank-Nicolson method> calculations. NPTEL's archived Lecture 13 introduces the <Thomas algorithm> from that time-stepping problem and labels the procedure “Thomas algorithm (1949)”.<Thomas algorithm (NPTEL Lecture 13)>[Lecture 13, Thomas algorithm: opening historical attribution and Crank Nicolson motivation]{ref}
Back to article page
