**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 *n*x*n* 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 *n*x*n *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

**Back substitution**: Proportional to

**Forward substitution**: Proportional to

So for LU decomposition method used to find the inverse of a matrix, the computational time is proportional to . 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 . 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 , while for Gaussian Elimination, the computational time is proportional to . So for large *n*, the ratio of the computational time for Gaussian elimination to computational for LU Decomposition is .

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

Pingback: So what does this mean that the computational time is proportional to some power of n in Gaussian Elimination method? « Autarkaw’s Weblog

Samuel L.

said:I noticed that this is not the first time you mention this topic. Why have you chosen it again?

LikeLike

Autar Kaw

said:I do not understand. If I have chosen it again, it must be in a different context.

LikeLike

click

said:Just to let you know your web site looks a little bit strange in Firefox on my notebook using Linux .

LikeLike

Juan Ramirez

said: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??

LikeLike

Autar Kaw

said:No, because the A=LU needs to be done only once. You are not going to get a different LU as A does not change. Read this chapter fully at http://mathforcollege.com/nm/mws/gen/04sle/mws_gen_sle_txt_ludecomp.pdf

LikeLike