Introduction

TDMA, also know as Thomaz Algorithm, stands for Tri-Diagonal Matrix Algorithm. It’s a simple, but yet effective algorithm used to solve tri-diagonal systems of equations. This algorithm is a direct method when solving a one dimensional problem, but also can be applied successfully to solve bi or tri-dimensional problems. In this case, the strategy is solve the problem interactively, line by line, until reach the convergence.

Problem

Consider the following system of equations:

Tri diagonal system of equations

Observe that the above system has an organization, on which the elements at the right hand side are displaced in bands, occupying the main diagonal, the first diagonal above this and the diagonal below the main diagonal. This organization eases the solution of the system of equations.

Solution

This system of equations leads to a Tri-Diagonal Matrix:

Tri diagonal matrix

Let’s start the Gaussian Elimination method, in a step by step fashion, by dividing the first row by $latex a_{1}$.

solution_step1

Let $latex P_{1}=b_{1}/a_{1}$ and $latex Q_{1}=d_{1}/a_{1}$. Now, the system allow us to eliminate $latex -c_{2}$ by multiplying the first row by $latex c_{2}$ and adding the result to the second row.

solution_step2

Now, dividing the second row by $latex a_{2}-c_{2}P_{1}$

solution_step3

The elimination continues by letting $latex P_{2}=frac{b_{2}}{a_{2}-c_{2}P_{1}}$ and $latex Q_{2}=frac{d_{2}+c_{2}Q_{1}}{a_{2}-c_{2}P_{1}}$ and also by eliminating $latex -c_{3}$.

solution_step4

Dividing the third row by $latex a_{3}-c_{3}P_{2}$

solution_step5

The elimination phase has one more step until the end by letting $latex P_{3}=frac{b_{3}}{a_{3}-c_{3}P_{2}}$ and $latex Q_{3}=frac{d_{3}+c_{3}Q_{2}}{a_{3}-c_{3}P_{2}}$ and also by eliminating $latex -c_{4}$.
solution_step6

Finally, let’s divide the fourth row by $latex a_{4}-c_{4}P_{3}$ and we reach to the end of the elimination phase

solution_step7

where $latex Q_{4}=frac{d_{4}+c_{4}Q_{3}}{a_{4}-c_{4}P_{3}}$. By inspecting the final system of equations, we conclude that $latex T_{4}=Q_{4}$.

Now, proceeding with the retro substitution phase

tdma_T3

If we move on, we also find $latex T_{2}$ and $latex T_{1}$

tdma_T2

tdma_T1

The table below summarizes what we done so far

tdma_table_1

Putting in general terms:

  • Forward elimination phase:

tdma_eq_Pn

tdma_eq_Qn

  • Backward substitution phase:

tdma_eq_Tn

Numerical Example

Consider the system of equations:

sys_eq_num_example

which gives origin to the following table

tdma_table_2

The last column of this table is the solution for the given system of equations after applying the equations showed in the Table 1.

Algorithm

A possible algorithm able to solve this problem is shown below.

tdma_flowchart

Code

Below is a simplistic Python implementation of the exposed algorithm.

import numpy as np

def SolveTdma(A, D):
  n = len(D)

  # The result
  T = np.zeros(n)

  # Auxiliary vectors
  P = np.zeros(n)
  Q = np.zeros(n)

  # Forward elimination phase:

  # First point
  b_0 = -A[0][1]
  P[0] = b_0 / A[0][0]
  Q[0] = D[0] / A[0][0]

  # Remaining points
  for j in range(1,n):
    a = A[j][j]
    c = -A[j - 1][j]

  # last point calculation
  if (j == n - 1):
    P[j] = 0

  # middle points
  else:
    b_n = -A[j][j + 1]
    P[j] = b_n / (a - c * P[j - 1])

    Q[j] = (D[j] + c * Q[j - 1]) / (a - c * P[j - 1])

  # Back-substitution phase:
  # Last point
  T[n - 1] = Q[n - 1]

  # Remaining points
  for i in range(n-2, -1, -1):
      T[i] = P[i] * T[i + 1] + Q[i]

  # The final result
  return T

if __name__ == "__main__":
  A = np.array([
      [20.0, -5.0, 0.0, 0.0],
      [-5.0, 15.0, -5.0, 0.0],
      [0.0, -5.0, 15.0, -5.0],
      [0.0, 0.0, -5.0, 10.0]
    ])

    D = np.array([1100.0, 100.0, 100.0, 100.0])
    print "TDMA"
    print "A:", A
    print "D:", D
    print "Result:", SolveTdma(A, D)

 

Conclusion

Due its simplicity, TDMA is very often used as a first method to be learnt by a numerical analyst aspirant. But such simplicity also has its price. This method is only applicable on very well “behaved systems”, i.e, systems that satisfies the condition: $latex a_{n}>0 ; : forall , n $. In other words, all elements in the main diagonal must be non-zero.

Also, the method has interesting variations that improve its computational performance and memory consumption. These variations will be posted here soon.

References

  • See Wikipedia, Tridiagonal matrix algorithm, (as of Nov. 02, 2009, 12:50 GMT);
  • Versteeg, H. K. & Malalasekera, W. (1995) – An Introduction to Computational Fluid Dynamics – The Finite Volume Method, Prentice Hall, London, UK;
  • Patankar, S. V.  (1980) – Numerical Heat Transfer and Fluid Flow, Hemisphere Publishing Corporation, Taylor & Francis Group, New York.
1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading...