Tridiagonal matrix algorithm  TDMA (Thomas algorithm)
From CFDWiki
(Difference between revisions)
m (Thomas algorithm moved to Tridiagonal matrix algorithm  TDMA (Thomas algorithm)) 
(towards a uniform notation for linear systems : A*Phi = B) 

Line 2:  Line 2:  
The Thomas Algorithm is a special form of Gauss elimination that can be used to solve tridiagonal  The Thomas Algorithm is a special form of Gauss elimination that can be used to solve tridiagonal  
systems of equations. When the matrix is tridiagonal, the solution can be obtained in O(n) operations,  systems of equations. When the matrix is tridiagonal, the solution can be obtained in O(n) operations,  
  instead of O(n3/3). Example of such matrices are matrices arising from  +  instead of O(n3/3). Example of such matrices are matrices arising from discretization of 1D problems. 
We can write the tridiagonal system in the form: <br>  We can write the tridiagonal system in the form: <br>  
:<math>  :<math>  
  a_i  +  a_i \phi_{i  1} + b_i \phi_i + c_i \phi_{i + 1} = d_i 
</math> <br>  </math> <br>  
Where <math> a_1 = 0 </math> and <math> c_n = 0 </math> <br>  Where <math> a_1 = 0 </math> and <math> c_n = 0 </math> <br>  
Line 17:  Line 17:  
: end loop (k)  : end loop (k)  
: then <br>  : then <br>  
  :: <math>  +  :: <math> \phi_n = {{d_n^' } \over {b_n }} </math> <br> 
: for k := n1 stepdown until 1 do <br>  : for k := n1 stepdown until 1 do <br>  
  :: <math>  +  :: <math> \phi_k = {{d_k^'  c_k \phi_{k + 1} } \over {b_k }} </math> <br> 
: end loop (k)  : end loop (k)  
   
Revision as of 20:43, 15 December 2005
Introduction
The Thomas Algorithm is a special form of Gauss elimination that can be used to solve tridiagonal systems of equations. When the matrix is tridiagonal, the solution can be obtained in O(n) operations, instead of O(n3/3). Example of such matrices are matrices arising from discretization of 1D problems.
We can write the tridiagonal system in the form:
Where and
Algorithm
 for k:= 2 step until n do

 end loop (k)
 then

 for k := n1 stepdown until 1 do

 end loop (k)
References
 Conte, S.D., and deBoor, C. (1972), Elementary Numerical Analysis, McGrawHill, New York..
Return to Numerical Methods