LU Decomposition takes more computational time than Gaussian Elimination! What gives?

If you are solving a set of simultaneous linear equations, LU Decomposition method (involving forward elimination, forward substitution and back substitution) would use more computational time than Gaussian elimination (involving forward elimination and back substitution, but NO forward substitution).

So why use and waste time talking about LU Decomposition?

Because, LU Decomposition is computationally more efficient than Gaussian elimination when we are solving several sets of equations with the same coefficient matrix but different right hand sides. Case in point is when you are finding the inverse of a matrix [A]. If one is trying to find the inverse of nxn matrix, then it implies that one needs to solve n sets of simultaneous linear equations of [A][X]=[C] form with the n right hand sides [C] being the n columns of the nxn identity matrix, while the coefficient matrix [A] stays the same.

The computational time taken for solving a single set of n simultaneous linear equations is as follows:

  • Forward elimination: Proportional to \frac{n^3}{3}
  • Back substitution: Proportional to \frac{n^2}{2}
  • Forward substitution: Proportional to \frac{n^2}{2}
  • So for LU decomposition method used to find the inverse of a matrix, the computational time is proportional to \frac{n^3}{3}+n( \frac{n^2}{2}+\frac{n^2}{2})=\frac{4n^3}{3}. Remember that the forward elimination only needs to be done only once on [A] to generate the L and U matrices for the LU decomposition method. However the forward and back substitution need to be done n times.

    Now for Gaussian Elimination used to find the inverse of a matrix, the computational time is proportional to n \frac{n^3}{3} +n \frac{n^2}{2}=\frac{n^4}{3}+\frac{n^3}{2}. Remember that both the forward elimination and back substitution need to be done n times.

    Hence for large n, for LU Decomposition, the computational time is proportional to \frac{4n^3}{3}, while for Gaussian Elimination, the computational time is proportional to \frac{n^4}{3} . So for large n, the ratio of the computational time for Gaussian elimination to computational for LU Decomposition is  {\frac{n^4}{3}}/{\frac{4n^3}{3}}=\frac{n}{4}.

    As an example, to find the inverse of a 2000×2000 coefficient matrix by Gaussian Elimination would take n/4=2000/4=500 times the time it would take to find the inverse by LU Decomposition.

    So are you convinced now why we use LU Decomposition in certain cases? For textbook notes on this issue, examples of LU Decomposition to solve a set of equations, and finding inverse of a matrix using LU Decomposition, click here.

    Reference: Numerical Methods for the STEM Undergraduate, http://numericalmethods.eng.usf.edu/topics/lu_decomposition.html

    This post brought to you by Holistic Numerical Methods: Numerical Methods for the STEM undergraduate at http://numericalmethods.eng.usf.edu

    Advertisements

    Undergraduate Numerical Methods for Engineering

    I am starting this blog to help UNDERGRADUATES with their queries on Numerical Methods for Engineers. I have been teaching Numerical Methods for the last 20 years and I get interesting queries and questions while I am teaching, when students come to see me during my office hours, or the email sent at midnight before the assignment is due.

    I am keeping a log of what students ask me and will note the answers to their queries here. I am sure that students elsewhere have similar questions when they take a course in Numerical Methods.

    The diversity of the course is quite evident –

    1. The course is taught to different engineering majors – mechanical, civil, chemical, industrial and electrical.
    2. Some teachers emphasize the numerical methods while others spend more time on solving physical problems, and a few may include numerical analysis.
    3. The programming tools are diverse including FORTRAN (yes the language is alive and well), Basic, C, Java, or computational packages such as MATLAB, MATHEMATICA, MathCAD, and Maple.

    With funding from NSF since 2002, we have developed web-based resources for a course in Numerical Methods. The inclusion of the blog is not part of the funded proposals but we think that this mode of Web 2.0 dissemination is critical in keeping the conversation going on. Although what I am doing here can be offered via a static website, the widgets offered by blogging softwares are indispensable. The widgets I like are categorizing, tagging and RSS Feeds.

    We want to reach as many people as possible and build a community which may be temporary to students who are taking a course in Numerical Methods, permanent to instructors and people who use numerical methods in their work. But one thing is certain, temporary or permanent, visitors will leave their imprint on this resource.

    This post brought to you by Holistic Numerical Methods: Numerical Methods for the STEM undergraduate at http://numericalmethods.eng.usf.edu