Tridiagonal matrix algorithm - TDMA (Thomas algorithm)
From CFD-Wiki
m (→Introduction) |
(Added more material) |
||
Line 1: | Line 1: | ||
== Introduction == | == Introduction == | ||
- | The Thomas | + | 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 |
- | systems of equations. | + | |
- | + | ||
- | |||
:<math> | :<math> | ||
- | a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i | + | a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i, |
</math> <br> | </math> <br> | ||
- | + | ||
+ | where <math> a_1 = 0 </math> and <math> c_n = 0 </math>. In matrix form, this system is written as | ||
+ | |||
+ | :<math> | ||
+ | \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} | ||
+ | {b_1 } \\ | ||
+ | {b_2 } \\ | ||
+ | \cdot \\ | ||
+ | \cdot \\ | ||
+ | {b_n } \\ | ||
+ | \end{matrix} | ||
+ | \right]. | ||
+ | </math> | ||
+ | |||
+ | For such systems, the solution can be obtained in <math>O(n)</math> operations instead of <math>O(n^3)</math> required by Gaussian Elimination. A first sweep eliminates the <math>a_i</math>'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 == | == Algorithm == | ||
- | : for k | + | Forward elimination phase |
+ | : for k = 2 step until n do <br> | ||
:: <math>m = {{a_k } \over {b_{k - 1} }} </math> <br> | :: <math>m = {{a_k } \over {b_{k - 1} }} </math> <br> | ||
:: <math> b_k^' = b_k - mc_{k - 1} </math> <br> | :: <math> b_k^' = b_k - mc_{k - 1} </math> <br> | ||
:: <math> d_k^' = d_k - md_{k - 1} </math> <br> | :: <math> d_k^' = d_k - md_{k - 1} </math> <br> | ||
: end loop (k) | : end loop (k) | ||
- | + | Backward substitution phase | |
- | + | : <math> x_n = {{d_n^' } \over {b_n }} </math> <br> | |
- | : for k | + | : for k = n-1 stepdown until 1 do <br> |
- | :: <math> | + | :: <math> x_k = {{d_k^' - c_k x_{k + 1} } \over {b_k }} </math> <br> |
: end loop (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: | ||
+ | |||
+ | :<math> | ||
+ | a_1 x_{n} + b_1 x_1 + c_1 x_2 = d_1, | ||
+ | </math> <br> | ||
+ | :<math> | ||
+ | a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i,\, i = 2,\ldots,n-1 | ||
+ | </math> <br> | ||
+ | :<math> | ||
+ | a_n x_{n-1} + b_n x_n + c_n x_1 = d_n. | ||
+ | </math> <br> | ||
+ | |||
+ | 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 == | == References == | ||
Line 28: | Line 76: | ||
- | -- | + | ''TODO: Add more references, more on the variants, and maybe more performance type info'' |
- | + | --[[User:Jasond|Jasond]] 16:50, 18 December 2005 (MST) |
Revision as of 23:50, 18 December 2005
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
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 Possion problem).
Algorithm
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)
Variants
In some situations, particularly those involving periodic boundary conditions, a slightly perturbed form of the tridiagonal system may need to be solved:
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
- Conte, S.D., and deBoor, C. (1972), Elementary Numerical Analysis, McGraw-Hill, New York..
TODO: Add more references, more on the variants, and maybe more performance type info
--Jasond 16:50, 18 December 2005 (MST)