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

    Author: Autar Kaw

    Autar Kaw (http://autarkaw.com) is a Professor of Mechanical Engineering at the University of South Florida. He has been at USF since 1987, the same year in which he received his Ph. D. in Engineering Mechanics from Clemson University. He is a recipient of the 2012 U.S. Professor of the Year Award. With major funding from NSF, he is the principal and managing contributor in developing the multiple award-winning online open courseware for an undergraduate course in Numerical Methods. The OpenCourseWare (nm.MathForCollege.com) annually receives 1,000,000+ page views, 1,000,000+ views of the YouTube audiovisual lectures, and 150,000+ page views at the NumericalMethodsGuy blog. His current research interests include engineering education research methods, adaptive learning, open courseware, massive open online courses, flipped classrooms, and learning strategies. He has written four textbooks and 80 refereed technical papers, and his opinion editorials have appeared in the St. Petersburg Times and Tampa Tribune.

    10 thoughts on “LU Decomposition takes more computational time than Gaussian Elimination! What gives?”

    1. I don’t understand how come Forward elimination is done just once on LU decomposition but but n times on Gaussian elimination?
      When I see the example in both cases it is necessary to get the upper matrices (Forward elimination in both cases) the same procedure in both methods, then should not be n*(n^3/3) in both cases??

      Like

    2. This post is wrong by one order of magnitude. The inverse of a matrix can be computed with gaussian elimination in $O(N^3)$ steps.

      Like

    3. “For inverting a matrix, Gauss-Jordan elimination is about as efficient as any
      other direct method. We know of no reason not to use it in this application if you are
      sure that the matrix inverse is what you really want.” Press, Teukolsky, et al,
      Numerical Recipes: The Art of Scientific Computing 2007.

      Liked by 1 person

      1. I am only showing how using the Gaussian elimination method takes more time than LU decomposition method to find the inverse of a square matrix. I am not saying that LU decomposition method is the best method for finding an inverse of a matrix. Now about using the Gauss-Jordan method, maybe you can find the computational time formula – I believe that it would be proportional to n^3 if that is what you are alluding to, but that is not Gaussian elimination though. To make a direct comparison with the formulas I have derived, you can use 4 clock cycle times for each addition, multiplication or subtraction, while 16 clock cycle times for each division.

        Liked by 1 person

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out /  Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out /  Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out /  Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out /  Change )

    Connecting to %s