CHAPTER 04.07: LU DECOMPOSITION: Why LU Decomposition:  Part 1

In this segment, we're going to talk about why we do LU decomposition.  What is the advantage of doing LU decomposition method? and you'll be able to see that why we want to do LU decomposition, because it might seem to be, in the beginning, that, hey, we are spending more time doing LU decomposition method than other methods. 

So for example, when you have A times X equal to C given to you.  So if you are doing, let's suppose, Naive Gauss elimination. So in this case, what you will be doing is you'll be doing forward elimination, there will be two steps which you'll be conducting in order to do Naive Gaussian method, you can do . . . you will do forward elimination and then you will do back substitution.  So that's where the computation time will be spent in order to solve this set of equations by Naive Gaussian method, you will do forward elimination steps and you will do back substitution steps.  Now, if you are doing LU decomposition method, then what is the time spent?  The first one, you will do forward elimination steps to find L times U, and that's something which we will be talking about in a different segment, that you'll be, in order to do LU decomposition, you have to first decompose your A matrix into L times U, and for that you'll be doing the same kind of steps which you are doing for the forward elimination steps for Naive Gaussian method.  And then you have to solve L times Z equal to C, and that's forward substitution. And then third one is that you have  U times X equal to Z, so once you have found out what Z, is you're going to put it in here, in U X equal to Z equation, and you're going to do back substitution. So what you are finding out here is that in Naive Gaussian method you are using forward elimination and back substitution, in LU decomposition method you are using the forward elimination steps to find the decomposition of the coefficient matrix into L times U, then you have to do the forward substitution, and then you have to do the back substitution.  So it seems that this is more work . . . not seems, but it is more work to do this than to do the Naive Gaussian method, because you have an extra step of this forward substitution, which you are seeing there.

So the question arises that why is then LU decomposition method even used if first you're going to use the forward elimination steps to find the decomposition itself, then you have to do forward substitution, and then you have to do back substitution?  So let's go ahead and see that what the reason for that is.  The reason for that is that because if you have multiple right-hand sides, and coefficient matrix is not changing, then your L times U, your LU decomposition method, may be better in terms of computational effort which you're . . . or the computational time it's going to take, so if you have multiple right-hand sides.  A good example of that can be, let's suppose if you're trying to find the inverse of A. Let's suppose you're trying to find inverse of A.  In order to find the inverse of A, you will have to solve n such sets of equations.  You will have to solve . . . you will have to solve n sets of equations with n different right-hand sides. So if you are trying to find the inverse of A, you will have to solve n sets of equations with n different right-hand sides.  So that means that only the right-hand side will be changing when you are trying to find the inverse of A, and you will have n different right-hand sides, your coefficient matrix is not going to change. So how does that make LU decomposition method a better method to use than using Gauss elimination?  So let's go ahead and see how that works out.