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

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.  So if you . . . if you look at Naive Gaussian method, so let's look at Naive Gauss elimination method. Let's go ahead and see that how much time Naive Gaussian method would take if I was going to find the inverse of an A matrix, inverse of an n-by-n A matrix.  So in that case I'll have forward elimination, okay?  Forward elimination takes . . . the amount of time forward elimination takes is approximately equal to C times n cubed divided by 3. She amount of time forward elimination takes, in order to . . . the computational time is C times n cubed divided by 3, approximately equal to, where C is simply the time to conduct a FLOP, okay?  Multiply/divide FLOP . . . multiply/divide FLOP.  What do I mean by that? C is the amount of time which it conducts . . . which it takes to conduct a multiplication/ division floating point operation, so it is proportional to n cubed by 3. So if n is the number of equations . . . n is the . . . n-by-n is the order of the A matrix, then the amount of time which it's going to take to do forward elimination in the Naive Gaussian method will be proportional to C n cubed divided by 3. 

There are certain assumptions which are involved in this is that we are assuming that multiply and divide floating point operations are taking the same amount of time, which is not actually true. We also . . . we're not also . . . we're also neglecting how much . . . how many floating point operations we have to do of addition and subtraction, although they take a little bit less time. So having . . . having taken these assumptions, that's why I put the word approximately here, because this is not exactly the number of floating point operations you are doing in Gaussian . . . in the forward elimination part of the Gauss elimination method. This is only the multiply/divide floating point operations you are doing, also you are then assuming that multiply and divide takes the same amount of time, and you're also neglecting the addition and subtraction, but this is not a bad assumption to make here that how much time forward elimination takes. In a similar spirit, back substitution . . . back substitution takes approximately C n squared divided by 2 amount of time. 

So if somebody was going to say that, hey, for doing one sets of . . . one set of equations, it will take C times n cubed by 3, for back substitution it takes C n squared divided by 2 amount of time, where C is the time it takes to conduct a single multiply/divide floating point operation, then I can see that the total time it's going to take, so total time it is going to take to find the inverse of A matrix will be C n cubed divided by 3, plus C n squared divided by 2. So this is going to be the amount of time it's going to take to do a single forward elimination and back substitution, so I'll have n times that.  n times C n cubed divided by 3, plus C n squared by 2 will be the amount of time it's going to take for me to do the n . . . to find out the inverse of A, because I have to do these forward substitution and back substitution n times.  Now what about LU decomposition method?  So let's do it on a separate place here. 

In the LU decomposition method, what's going to happen is that the amount of time I have to do forward elimination, so forward elimination is going to take the same amount of time as it takes for Naive Gaussian method, because I'm using the same steps of forward elimination to do the LU decomposition, so it'll be C n cubed divided by 3. Then also, of course, I have to do forward substitution, and that's going to take approximately C n squared by 2, because forward substitution will be same as back substitution, we just talked about that back substitution take C n squared by 2 time, so then back substitution will take approximately C n squared by 2 time also. So you can see that LU decomposition is going to take more time, because we have forward elimination steps, forward substitution steps, and back substitution steps, if we were just doing this once, because the total time will be C n cubed divided by 3, plus C n squared by 2, plus C n squared by 2, because this is the times, which is this part here, is the additional which you have to take in terms of . . . in LU decomposition method.  But the thing is that what you are not seeing is that this . . . this is the time which it's going to take to do the LU decomposition method . . . or the LU decomposition of the A matrix, so this has to be done only once, however this part here will have to be done n times, because I'll have to do the forward substitution and back substitution n times, because the LU decomposition only has to be done once.  So if I . . . this is the total time it's going to take to do LU decomposition.  So this one becomes C n cubed divided by 3, plus C n cubed, and that becomes 4 C n cubed divided by 3. So you can already see that the . . . if I try to write down what is the time taken by Gaussian elimination, so if I look at Gaussian elimination time, and then divided by the . . .  divided by the LU decomposition time. What is that equal to?  The Gauss elimination time is n times C n cubed divided by 3, plus C n squared divided by 2, and the LU decomposition times is 4 n cubed . . . 4 C n cubed divided by 3.  And this is approximately equal to, if n is large, then this quantity here becomes small as compared to this quantity here, so I can always write this as approximately equal to c n cubed divided by 3, so I'm going to neglect this term here, and divided by 4 C n cubed divided by 3. So what I'm going to get is this and this cancels, C and C cancels, and that's n divided by 4.  So what it is basically telling you that the amount of time Gauss elimination is going to take to find the inverse of a matrix will be n by 4 times what LU decomposition is going to take in order to be able to do the finding the inverse of a matrix. So you can very well see if n is equal to . . . if n is equal to 1000, let's suppose, your Gauss elimination . . . your Gauss elimination time divided by the LU decomposition time is going to be 250, because n divided by 4, 1000 divided by 4 is 250.  So Gauss elimination will take 250 times more what LU decomposition will take to do . . . find the inverse of a matrix.  So this is the reason why LU decomposition is favored over Gauss elimination when you have multiple right-hand sides, as will be the case when you are trying to find the inverse of a matrix.  And that's the end of this segment.