CFD Online Discussion Forums (http://www.cfd-online.com/Forums/)
-   Main CFD Forum (http://www.cfd-online.com/Forums/main/)
-   -   comparision between TDMAand gauss elimination (http://www.cfd-online.com/Forums/main/13261-comparision-between-tdmaand-gauss-elimination.html)

comparision between TDMAand gauss elimination

friends, I would like to know how many transformations or calculations we are saving by using Thomas algorithm instead of Gauss elimination approch if any one know mathematial derivation of this plz directly mail t o aditya_jayanthi1986@yhaoo.com

 pc April 6, 2007 08:36

Re: comparision between TDMAand gauss elimination

Basically you have far less work and less storage with TDMA. You only need to store 3 vectors for the diagonal and off-diagonal terms, not the full matrix.

You can find details on TDMA in any introductory CFD text.

 opaque April 6, 2007 13:00

Re: comparision between TDMAand gauss elimination

Mostly you are saving storage since you require only 3 vectors for diagonal, and a RHS vector.

The number of operations saved is dependent of what you mean by Gaussian elimination. For Gaussian elimination w/o partial/total pivoting, you are only saving the logical decisions of not processing the 0's on the even lower triangular part of the full matrix when doing the forward elimination. Similar when doing the back susbtitution.

Thomas' algorithm is just a minimal storage version of Gaussian elimination. However, they are only identical if pivoting is not used.

I do not recall exactly, but if your equations are not diagonally dominant you may find a round off propagation/truncation error that Gaussian elimination with pivoting does not have.

Opaque.

 Trinity April 6, 2007 18:52

Re: comparision between TDMAand gauss elimination

TDMA involves O(n) operations, while Gauss elimination involves O(n3) operations, if n is the size of the matrix to be inverted.

 Opaque April 7, 2007 11:19

Re: comparision between TDMAand gauss elimination

Dear Trinity,

For a full nxn matrix, you are correct.. Just run through the Gauss algorithm for the 3 diagonals, and count the operations..Recall that when doing the forward elimination (for most implementations) there is no cost when eliminating a row with leading zero coefficient since they are skipped.

The problem might be in the back substitution.. Most implementations run from column j--> n w/o checking for zero coefficients.

My point was (at least I intended to) that Thomas algorithm is just Gauss Elimination reduced to 3 diagonals. It is not a "different" method..

 Trinity April 7, 2007 11:54

Re: comparision between TDMAand gauss elimination

You are right absolutely right Opaque, I had never thought about the possibility of zero coefficients. I guess partly because I have only dealt with 'nice' matrices, that are diagonally dominant. The type you get when discretizing the laplacian.

So TDMA just 'honors' the fact that the matrix is tridiagonal (and diagonally dominant) and applies GE with that understanding. But in certain non-linear problems i suppose, the matrix may not be as nicely behaved (and thanks for pointing that out to me! :) )

But in most 'beginner' problems, if there is a choice between TDMA and GE, TDMA is the way to go. Even when used iteratively, for example in solving poisson equation in 2d, TDMA is orders of magnitude faster. It is a pain to implement the boundary conditions sometimes, but nothing as compared to the pain of seeing the simulation run for half the day as with GE.

 All times are GMT -4. The time now is 16:31.