Contents

# 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:

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:

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

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.

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

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}$.

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

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}$.

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

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

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

The table below summarizes what we done so far

Putting in general terms:

- Forward elimination phase:

- Backward substitution phase:

# Numerical Example

Consider the system of equations:

which gives origin to the following table

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.

# 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.