Created
November 6, 2021 07:37
-
-
Save vuddameri/75212bfab7d98a9c75861243a9f8f272 to your computer and use it in GitHub Desktop.
Thomas Algorithm.ipynb
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 5, | |
| "metadata": { | |
| "kernelspec": { | |
| "display_name": "Python 3 (ipykernel)", | |
| "language": "python", | |
| "name": "python3" | |
| }, | |
| "language_info": { | |
| "codemirror_mode": { | |
| "name": "ipython", | |
| "version": 3 | |
| }, | |
| "file_extension": ".py", | |
| "mimetype": "text/x-python", | |
| "name": "python", | |
| "nbconvert_exporter": "python", | |
| "pygments_lexer": "ipython3", | |
| "version": "3.8.10" | |
| }, | |
| "colab": { | |
| "name": "Thomas Algorithm.ipynb", | |
| "provenance": [], | |
| "include_colab_link": true | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/vuddameri/75212bfab7d98a9c75861243a9f8f272/thomas-algorithm.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "e1314e17" | |
| }, | |
| "source": [ | |
| "<h1><font color = 'blue'><center>Tridiagonal Matrix Algorithm (Thomas Algorithm)</center></font></h1>" | |
| ], | |
| "id": "e1314e17" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "d50d8c69" | |
| }, | |
| "source": [ | |
| "<p > Sparse matrices are commonly encountered when finite difference and finite element methods are used to solve differential equations. <font color='red'>A sparse matrix is a matrix where a majority of elements have zero values.</font> The presence of a large number of zeros creates both challenges and opportunities when solving matrices. The primary challenge arises when inverting a matrix using traditional methods. However, for sparsity also helps reduce the data storage requirements and lead to simpler approaches to solve systems of equations involving sparse matrices.</p> " | |
| ], | |
| "id": "d50d8c69" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "1022efea" | |
| }, | |
| "source": [ | |
| "<p> <font color='red'>A tridiagonal matrix only contains non-zero elements along the principal diagonal as well as along the left and right columns immediately adjecent to the diagonal. </font> If the coefficient matrix is a tridiagonal matrix, then Gaussian elimination can be readily applied in an efficient way. <font color= 'blue'> The tridiagonal matrix algorithm (TMDA) or the Thomas Algorithm </font> is an efficient application of Gaussian-elimination to solving system of equations whose diagonal terms are sparse. " | |
| ], | |
| "id": "1022efea" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "ea0eec40" | |
| }, | |
| "source": [ | |
| "Consider a system of linear equations represented using the matrix form below:\n", | |
| "\n", | |
| "$\\begin{equation}\n", | |
| "[A] [x] = [d]\n", | |
| "\\end{equation}$\n", | |
| "\n", | |
| "If A is a tridiagonal matrix then it will be of the following form:" | |
| ], | |
| "id": "ea0eec40" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "da0d2a40" | |
| }, | |
| "source": [ | |
| "\n" | |
| ], | |
| "id": "da0d2a40" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "a981f017" | |
| }, | |
| "source": [ | |
| "Just like Gaussian Elimination, the TMDA proceeds with the <font color='blue'> forward sweep </font> which results in a last equation having just one unknown leading to a solution of $x_n$. This is followed by a <font color='red'> reverse sweep (backward substituion) </font> where the estimated $x_{i+1}$ value is used to compute the unknown $x_i$. " | |
| ], | |
| "id": "a981f017" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "c39fcbfa" | |
| }, | |
| "source": [ | |
| "<h3> <font color='blue'> Forward Sweep </font> </h3>" | |
| ], | |
| "id": "c39fcbfa" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "2a8a5f12" | |
| }, | |
| "source": [ | |
| "The forward sweep perform row operations wherein the pivoting row is modified and subtracted from other equations to eliminate all but one unknown $x_n$. These operations can be succinctly summarized as follows:" | |
| ], | |
| "id": "2a8a5f12" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "a832d3b5" | |
| }, | |
| "source": [ | |
| "" | |
| ], | |
| "id": "a832d3b5" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "acbd761b" | |
| }, | |
| "source": [ | |
| "Where $c'_i$ and $d'_i$ are modified coefficients for c and d in the original matrix. Notice that b and a coefficients are not modified in this process (as they are eliminated)." | |
| ], | |
| "id": "acbd761b" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "633537c9" | |
| }, | |
| "source": [ | |
| "<h3> <font color='blue'> Reverse Sweep (Back-substitution) </font> </h3>" | |
| ], | |
| "id": "633537c9" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "09da384c" | |
| }, | |
| "source": [ | |
| "The completion of the forward sweep results in a value of $x_n$. This value can be used to compute the value of $x_{n-1}$ which in turn can be used to obtain $x_{n-2}$ and so on using the transformed coefficients as follows: " | |
| ], | |
| "id": "09da384c" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "27678e23" | |
| }, | |
| "source": [ | |
| "" | |
| ], | |
| "id": "27678e23" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "85b402c5" | |
| }, | |
| "source": [ | |
| "<h3> <font color='blue'> Python Implementation </font> </h3>" | |
| ], | |
| "id": "85b402c5" | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "5e7017e7" | |
| }, | |
| "source": [ | |
| "# Python Function to Implement Thomas Algorithm\n", | |
| "# Venki Uddameri\n", | |
| "\n", | |
| "# Step 1: Import Libraries\n", | |
| "import numpy as np\n", | |
| "\n", | |
| "# Function for TMDA Algorithm\n", | |
| "def thomas(a,b,c,d):\n", | |
| " \"\"\" A is the tridiagnonal coefficient matrix and d is the RHS matrix\"\"\"\n", | |
| " N = len(a)\n", | |
| " cp = np.zeros(N,dtype='float64') # store tranformed c or c'\n", | |
| " dp = np.zeros(N,dtype='float64') # store transformed d or d'\n", | |
| " X = np.zeros(N,dtype='float64') # store unknown coefficients\n", | |
| " \n", | |
| " # Perform Forward Sweep\n", | |
| " # Equation 1 indexed as 0 in python\n", | |
| " cp[0] = c[0]/b[0] \n", | |
| " dp[0] = d[0]/b[0]\n", | |
| " # Equation 2, ..., N (indexed 1 - N-1 in Python)\n", | |
| " for i in np.arange(1,(N),1):\n", | |
| " dnum = b[i] - a[i]*cp[i-1]\n", | |
| " cp[i] = c[i]/dnum\n", | |
| " dp[i] = (d[i]-a[i]*dp[i-1])/dnum\n", | |
| " \n", | |
| " # Perform Back Substitution\n", | |
| " X[(N-1)] = dp[N-1] # Obtain last xn \n", | |
| "\n", | |
| " for i in np.arange((N-2),-1,-1): # use x[i+1] to obtain x[i]\n", | |
| " X[i] = (dp[i]) - (cp[i])*(X[i+1])\n", | |
| " \n", | |
| " return(X)" | |
| ], | |
| "id": "5e7017e7", | |
| "execution_count": 1, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "ccc366f2" | |
| }, | |
| "source": [ | |
| "<h3> <font color='blue'> Illustrative Example </font> </h3>" | |
| ], | |
| "id": "ccc366f2" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "46422ba0" | |
| }, | |
| "source": [ | |
| "Use the thomas function to solve the system of equations shown in the matrix form below:" | |
| ], | |
| "id": "46422ba0" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "b3caecd8" | |
| }, | |
| "source": [ | |
| "" | |
| ], | |
| "id": "b3caecd8" | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "3ebaa2dc" | |
| }, | |
| "source": [ | |
| "# Main Program\n", | |
| "#step 1: Create Coefficient and LHS matrices store (a,b,c,d) seperately\n", | |
| "a = [0,-1,-1,-1]\n", | |
| "b = [2,2,2,1]\n", | |
| "c = [-1,-1,-1,0]\n", | |
| "d = [0,0,1,0]\n", | |
| "\n", | |
| "# Call thomas function\n", | |
| "x = thomas(a,b,c,d)\n" | |
| ], | |
| "id": "3ebaa2dc", | |
| "execution_count": 2, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "4e06a951", | |
| "outputId": "784b1f12-4062-49ba-8319-e23c24821203" | |
| }, | |
| "source": [ | |
| "# Print x\n", | |
| "print('The values of x are: ',x)" | |
| ], | |
| "id": "4e06a951", | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "The values of x are: [1. 2. 3. 3.]\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "c65d59bf" | |
| }, | |
| "source": [ | |
| "<h3> <font color='blue'> Closing Remarks </font> </h3>" | |
| ], | |
| "id": "c65d59bf" | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "b8333d71" | |
| }, | |
| "source": [ | |
| "Tridiagnonal matrix algorithm (TMDA) or the Thomas Algorithm is an efficient way to solve systems of equations whose coefficient matrix is tridiagonal. This approach comes in handy when solving $2^{nd}$ Order ODEs (Boundary Value Problems) as well as 1D parabolic partial differential equations such those depicting the flow of heat, mass and momentum in natural and engineered systems. Understanding this algorithm is therefore beneficial to engineers. " | |
| ], | |
| "id": "b8333d71" | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment