Tridiagonal Matrices

Tridiagonal matrices have nonzero element only in a narrow band around the diagonal \[A = \begin{bmatrix} b_1 & c_1 & 0 & ... & 0\\ a_2 & b_2 & c_2 & ... & 0 \\ 0 & & \ddots & & 0 \\ 0 & ... & a_{n-1} & b_{n-1} & c_{n-1} \\ 0 & & ... & a_n & b_n\\ \end{bmatrix}.\] Solving a system of linear equations \(Ax=b\) can be done very efficiently by the so called Thomas algorithm, named after the physicist and computational scientist Llewellyn Thomas.

Since the algorithm is very well documented on wikipedia, I won't repeat it here. It is essentially a specialization of the standard Gauss elimination method to the special structure of tridiagonal matrices.

It is an order \(\mathcal{O}(n)\) algorithm, which means it is very efficient compared to \(\mathcal{O}(n^3)\) for a general matrix.

The attribution to Llewellyn Thomas is somewhat interesting. Cleve Moler writes:

Llewellyn H. Thomas is a distinquished physicist who in the 50's held positions at Columbia University and at IBM's Watson Research Laboratory when it was located adjacent to the Columbia campus. He is probably best known in connection with the Thomas-Fermi electron gas model. 

The so-called Thomas Algorithm is indeed just a form of elimination for solving tridiagonal systems of linear equations. But it usually associated with the systems that arise from finite difference approximations to partial differential equations. The attribution to Thomas seems to be more common in some engineering disciplines than it is in numerical analysis. 

W.F. Ames writes in his book [1]: "The method we describe was discovered independently by many and has been called the Thomas algorithm (see [2]) by (David) Young. Its general description first appeared in widely distributed published form in an article by Bruce et al. [3]."