Tridiagonal matrix algorithm - TDMA (Thomas algorithm)
From CFD-Wiki
Contents |
Introduction
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
where 
and 
. 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].](/W/images/math/5/b/7/5b73418f4d5bd7154e369a6d6f4ae2fd.png)
For such systems, the solution can be obtained in 
operations instead of 
required by Gaussian Elimination. A first sweep eliminates the 
'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 Poisson problem).
Algorithm
The following algorithm performs the TDMA, overwriting the original arrays. In some situations this is not desirable, so some prefer to copy the original arrays beforehand.
Forward elimination phase
- for k = 2 step until n do
-
- end loop (k)
Backward substitution phase
-
- for k = n-1 stepdown until 1 do
-
- end loop (k)
Assessments
Variants
In some situations, particularly those involving periodic boundary conditions, a slightly perturbed form of the tridiagonal system may need to be solved:
In matrix form, this is
![\left[
\begin{matrix}
{b_1} & {c_1} & { } & { } & {a_1} \\
{a_2} & {b_2} & {c_2} & { } & { } \\
{ } & {a_3} & {b_3} & \cdot & { } \\
{ } & { } & \cdot & \cdot & {c_{n-1}}\\
{c_n} & { } & { } & {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].](/W/images/math/2/3/8/2385d1237cd9b6cb03c950b105dd6c5a.png)
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. We will now solve
where
![u^T = [b_1\ 0\ 0\ ...\ 0\ c_n],\ v^T = [1\ 0\ 0\ ...\ 0\ a_1/b_1].](/W/images/math/7/7/f/77f8df970b65c81b0e706c3a5f6e7a8a.png)
is a slightly different tridiagonal system than above, and the solution to the perturbed system is obtained by solving
and compute 
as
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
- Conte, S.D., and deBoor, C. (1972), Elementary Numerical Analysis, McGraw-Hill, New York..
Still TODO: Add more references, more on the variants, make things nicer looking, and maybe more performance type info --Jasond 22:59, 7 April 2006 (MDT)
