Thomas algorithm

Solves a tridiagonal linear system in $O(N)$ operations (Gaussian elimination: $O(N^3)$):

$$a_i{x}_{i-1}+b_i{x}_i+c_i{x}_{i+1}=d_i,i=1\dots N$$

where:

• $x_i$: unknowns,
• $a_i$, $b_i$, $c_i$: lower, main and upper diagonal coefficients ($a_1=c_N=0$),
• $d_i$: right-hand side.

Forward sweep, starting from $c_1^{\prime }=c_1/b_1$ and $d_1^{\prime }=d_1/b_1$:

$$c_i^{\prime }=\frac{c_i}{b_i-a_i{c}_{i-1}^{\prime }},d_i^{\prime }=\frac{d_i-a_i{d}_{i-1}^{\prime }}{b_i-a_i{c}_{i-1}^{\prime }}$$

Back substitution, starting from $x_N=d_N^{\prime }$:

$$x_i=d_i^{\prime }-c_i^{\prime }{x}_{i+1}$$

No pivoting, so it is only safe when the matrix is diagonally dominant ($|b_i|>|a_i|+|c_i|$), as in discretised diffusion. Used in implicit diffusion schemes such as Crank-Nicolson, and for cubic splines.