Tridiagonal matrix algorithm

The tridiagonal matrix algorithm (TDMA), also known as the Thomas algorithm, is a simplified form of Gaussian elimination that can be used to solve tridiagonal systems of equations. A tridiagonal system may be written as

$a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}=d_{i},$

where $a_{1}=0$ and $c_{n}=0$. In matrix form, this system is written as

$\left[{\begin{matrix}{b_{1}}&{c_{1}}&{}&{}&{0}\\{a_{2}}&{b_{2}}&{c_{2}}&{}&{}\\{}&{a_{3}}&{b_{3}}&\cdot &{}\\{}&{}&\cdot &\cdot &{c_{n-1}}\\{0}&{}&{}&{a_{n}}&{b_{n}}\\\end{matrix}}\right]\left[{\begin{matrix}{x_{1}}\\{x_{2}}\\\cdot \\\cdot \\{x_{n}}\\\end{matrix}}\right]=\left[{\begin{matrix}{d_{1}}\\{d_{2}}\\\cdot \\\cdot \\{d_{n}}\\\end{matrix}}\right].$

For such systems, the solution can be obtained in $O(n)$ operations instead of $O(n^{3})$ required by Gaussian Elimination. A first sweep eliminates the $a_{i}$'s, and then an (abbreviated) backward substitution produces the solution. Example of such matrices commonly arise from the discretization of 1D problems (e.g. the 1D Possion problem).

Algorithm

Forward elimination phase

for k = 2 step until n do

$m={{a_{k}} \over {b_{k-1}}}$

$b_{k}^{'}=b_{k}-mc_{k-1}$

$d_{k}^{'}=d_{k}-md_{k-1}$

end loop (k)

Backward substitution phase

$x_{n}={{d_{n}^{'}} \over {b_{n}}}$

for k = n-1 stepdown until 1 do

$x_{k}={{d_{k}^{'}-c_{k}x_{k+1}} \over {b_{k}}}$

end loop (k)

Variants

In some situations, particularly those involving periodic boundary conditions, a slightly perturbed form of the tridiagonal system may need to be solved:

$a_{1}x_{n}+b_{1}x_{1}+c_{1}x_{2}=d_{1},$

$a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}=d_{i},\,i=2,\ldots ,n-1$

$a_{n}x_{n-1}+b_{n}x_{n}+c_{n}x_{1}=d_{n}.$

In this case, we can make use of the Sherman-Morrison formula to avoid the additional operations of Gaussian elimination and still use the Thomas algorithm.

In other situation, the system of equation may be block tridiagonal, with smaller submatrices arranged as the individual elements in the above matrix system. Simplified forms of Gaussian elimination have been developed for these situations.

References

• Template:Reference-book
• This article incorporates text from the article {{{name}}} on CFD-Wiki that is under the GFDL license.