Tridiagonal matrix algorithm

The tridiagonal matrix algorithm, also known as the Thomas algorithm after Llewellyn Thomas, is a simplified form of Gaussian elimination used to solve tridiagonal systems of linear equations, in which each equation involves only one unknown and its two neighbours. A forward sweep computes modified coefficients and a back substitution then recovers the solution. Such a system can be solved in a number of operations proportional to n instead of the order of n cubed required by general Gaussian elimination, so the cost grows linearly with the size of the system. The same idea is applied to block tridiagonal systems, in which smaller submatrices are arranged along the diagonals.