|
CHAPTER 04.07: LU DECOMPOSITION: Why LU
Decomposition Method?
So, to recap, if we have a set of equations
like [A][X] equal to [B], what we first do in Gaussian elimination is use
forward elimination steps to reduce the set of equations where the
coefficient matrix becomes an upper triangular matrix. And the reason why we
do that is because now we can conduct the steps of back substitution and be
able to find out the unknown variables/ the unknown vector [X] is. The same
thing is in LU decomposition method, what we do is we decompose the
coefficient matrix [A] into [L] times [U]. And we already know that in order
to be able to decompose the matrix [A] into [L] times [U], we use the steps
of forward elimination of Gaussian elimination to do it. Once we have done
the decomposition, we set up the problem with [L] times [Z] equals to [B] to
do the forward substitution and find [Z]. Once we have found [Z], we use that
as the right-hand side, and we use back substitution just like in Gaussian
elimination to calculate the unknown vector [X]. So, what you are basically
seeing here is that there's a lot of similarity between LU decomposition
method and Gaussian elimination. One might say: hey, LU decomposition method
has three steps while Gaussian elimination has only two steps? Isn't LU
decomposition method more complicated/ more complex than Gaussian
elimination? So, we want to be able to see that hey whether the complication
is there or not, we want to see that whether LU decomposition method is computationally
efficient than Gaussian elimination or not. If it is not, then, we might be
simply wasting our time. In order to make the argument that how much time
Gaussian elimination and LU decomposition method time it takes, what we need
to do is we need to figure out what the individual components of these
methods take as far as the computational time is concerned. Here is back
substitution which is common between the two methods. This is the end
equation which you are gonna get at the end of the
forward substitution step in LU decomposition method or the end of the
elimination of the Gaussian elimination method. And, this is the algorithm in
order to be able to conduct the back substitution. What I'm giving you here
is the code which is needed to be able to do the back substitution in MATLAB,
I suppose. And the computational time will depend on how fast the machine is,
right? And, will also depend on how many computations you are doing, how many
floating-point operations you are doing. So, let's take care of the first concept,
which is the clocks, clock cycle time. So, if you have a 2 Giga-Hertz machine,
let’s suppose, in that case that means that it is going through 2 billion
cycles per second. So, how much does one cycle take, as far as time is
concerned? Is 1 divided by 2 times 10 to the power of 9 seconds. Which is 0.5
times 10 to the power of minus 9 seconds, and that is about 0.5 nanoseconds.
So, the machine is taking 0.5 nanoseconds to go through one cycle, and the floating-point
operation which are taking place in this algorithm and they are right here,
the division is taking place right here, the subtraction is taking place
division is taking place right here, the multiplication taking place here. It's
taking place in two nested loops as you can see right here. How many of these
floating-point operations are taking place? We won’t be concerned about that
in this particular lecture. It is given in a blog
and link to that blog is given in the YouTube description, so you can definitely go there to satisfy your curiosity. But, what
we find out is that if we go through this algorithm right here, the number of
multiplications, additions, divisions, and subtractions which are taking
place as follows: you have n divisions, you get 0 additions, n times n minus
1 divided by 2 multiplications, and n times n minus one dived by two
subtractions. Those are the number of floating-point operations which are
taking place in the algorithm. Now, what we want to be able to figure out is
that since we now know the number of floating-point operations that are
taking place, how much time is going to take to do back substitution which
are basically we are trying to derive this particular formula right here. So, now to do that, what we are gonna do is we can say hey let's suppose if I know the
architecture of the chip I'm using on this 2 Giga-Hertz
machine I suppose an AMD chip. And typically on an
AMD chip it takes 4 clock cycles to do one addition, it takes four clock
cycle times to do one subtraction, it takes four clock cycles to do one
multiplication, and takes 16 clock cycles to do one division. So, that is the
amount of time it takes to do one floating-point operation of addition,
subtraction, multiplication here is four times T, T is the clock cycle time, and 16T for
division, T being the clock cycle time again. Then the total time our back
substitutions is gonna take is based on that hey we
already know that we have n divisions, right? If n divisions and each
division is taking 16 clock cycle times, that is 16 T, we already know that
no additions are taking place, so 0 times 4T, we also know that there are n
times n minus 1 divided by 2 multiplication taking place, and each
multiplication takes 4 clock cycle times, and then we know that there are n
minus n times n minus 1 divided by 2 subtractions taking place, and each subtraction
taking four clock cycles. So, if we add all those times, we get T times 4n
squared plus 12n and that is how we are able to
obtain the computational time for back substitution. So, we just found out
that hey the amount of time it takes to do in this particular
back substitution is T times 4n squared plus 12n. Similarly, if you
follow the algorithm, you will find this is the amount of time it takes to do
forward elimination, this is the amount of time it takes to decompose
coefficient matrix [A] into the form [L] times [U] and this is the amount of
time it takes to do forward substitution. So, we should be able to use these particular computational times for the various steps to be
able to make the comparison between Gaussian elimination and the LU
decomposition method. As a side note, I want you to think about two
things: one is that look at the forward elimination computation time it is
proportional to n cube, so is the decomposition to the [L] times [U] it is
proportional n cube. However, the proportionality for the back substitution
and the forward substitution is only proportionally to n squared. So, keep
that in mind to figure out that hey which part of the algorithm is going to
be computationally intensive. The other thing which I want to point out here
is that look at the time it takes to back substitution and the time it takes
to forward substitution. It…a person would think that hey these two times
should be exactly the same because what is forward
substitution? Is more… it is the inverse of back substitution and the back substitution start with the last equation and go to
the first equation, and the forward substitution you start from the first
equation and go to the last equation. But, the times
are different. So, think about it why are the times different? Second, look
at the forward elimination… decomposition into [L] [U]. We use forward
elimination to decompose of matrix into [A] times [L][U]. However, the time
for decomposition is less than the time it takes for forward elimination. So,
answer this question: why is the time it takes to decompose the [A] matrix to
L times U less than what it takes to do forward elimination? So, answer those
questions and I think you know better understanding of what we mean by
computational times. So, is a LU decomposition more efficient than
Gaussian elimination? Let's go and see! So, T is the clock cycle time. And
then if we have this as the size of the matrix n equations n unknowns, so the
coefficient matrix will be n by n. So, in this particular
case, what you'll find out is here is that you have forward
elimination this is the amount of time it takes to forwards elimination this
is the amount it takes to back substitution. So, for Gaussian elimination the
time will be how much time does it take forward elimination, how much time
does it take to do back substitution. So, as far as the LU decomposition is
concerned, I have to add the time it takes to
decompose the matrix, the time it takes to do forward substitution, and the
time it takes to do back substitution. So, this is the amount of time it
takes to do Gaussian elimination, this is the amount of time it takes to do LU
decomposition. So, if we add those times, this is what we get for Gaussian
elimination, and this is what we get for LU decomposition. And you can
clearly see both these particular times, computational
times, are exactly. the same. So, both methods LU decomposition method and
Gaussian elimination are equally efficient So, one should surely ask the
question that hey so what is the advantage of LU decomposition method when
it's so similar to Gaussian elimination and since we…it is three steps rather
than two steps and Gaussian elimination we conduct forward elimination, back
substitution. In LU decomposition method we do decomposition of the [A] matrix,
we do the forward substitution, do the back substitution. So, what what is what gives? That's what we want to answer. So,
let's figure out when is the LU decomposition method better than Gaussian
elimination. LU decomposition is better than Gaussian elimination when you
have multiple right-hand side vectors. What does that mean? What that means
is that let's suppose somebody gives me a set of questions [A][X] equal to [B],
and then says okay you solve for X. So, I solve for X. Then they give me
another vector for B and keep the [A] to the same then say solve for X. I can
do that by either of the methods and I can continue to do this depending on
how many different right-hand side vectors are given to me. So, let's suppose
if I'm even given M right-hand sides, so I'm giving M right-hand side vectors.
How much time is gonna take me to do forward
elimination? Would be given by that hey it will be I'll have to do the
forward elimination, I'll have to do M times, and I'll have to do the back substitution M times. That's the amount of time it’s gonna take me to do it by using, back subs… using Gaussian
elimination. How much time is gonna take me to do
it by using LU decomposition method will be… I will
do the decomposition, but then I'll have to do the forward substitution M
times, because my right-hand side vector is changing, and also
I’ll do the back substitution M times. Now, you might say hey why didn't I
multiply this by M? This is because the decomposition of the [A] matrix will
stay the same no matter how many times different right-hand sides are given
to you because the [A] is not changing so it is decomposition of [L] times [U]
is not changing. You can decompose M times but you're going to get the same
answer again and again. So, now to save time we just do it only once. So, now
I'm hoping that you are able to see that why the LU
decomposition method is a better method than Gaussian elimination under these
circumstances that multiple right-hand sides are given to you. In order to exemplify this advantage, let’s
take an example of finding the inverse of a square matrix to show that how
much time we are really saving by using LU decomposition method over Gaussian
elimination. If you recall your definition of the inverse of a matrix, what
is it? If I want to find the inverse of [A] if I multiply it by its inverse
it should come out with an identity matrix. So, what does that mean? What
that means is that if somebody is saying that hey go ahead and solve for the
inverse of a matrix, it simply means that you are setting up n sets of
equations. You are setting up n sets of equations. That's what you said you
know what… why is that? Why is that it shows that if you are trying to find [A]
times [B], [B] has n columns in it. And as you know that when you are solving
a set of equation you can only solve one column at a time, right? So, the [A]
matrix multiplied by the first column of the inverse matrix will be the first
equal to the first column of the identity matrix. The [A] matrix multiplied
by the second column of the inverse matrix will be equal to the second column
of the identity matrix. And, if we continue to do this, if you go to the last
column, the [A] matrix multiplied by the last column of the inverse matrix it
would be equal to the last column of the identity matrix. And what you are
finding out here is a good example that whenever you are trying to find the inverse
of a matrix it boils down to finding the solution to a set of equations where
the right-hand side vector is the only thing which is changing. The [A]
matrix, in all of these sets of equations, is always
staying the same. Hence, what that means is that when I decompose my [A]
matrix I will only have to do it once. Let's see what that means. What that means
that if I was going to do the problem by Gaussian elimination then since I
have N different right-hand sides I'll have to do
the forward elimination N times I'll have to the back substitution N times. And
if I do the calculation, this is the total amount of time to take we need to
find the inverse of a square matrix by using Gaussian elimination. And look
at the computational time, it is proportional to the quantity of N to the
power of 4. However, when I am doing LU decomposition method I only decomposed,
had to decompose the matrix only once. However, the forward substitution will
have to be done N times and the backs substitution N times. Why? Because I
got N different right-hand sides. And once I do the addition of these three
quantities this is what I get. And look at this: the computational time taken
by LU decomposition method is proportional to N cube as opposed to N to the
power of 4 for Gaussian elimination method. And I'm hoping that by looking at
these expressions here, for the time taken by Gaussian time taken by LU decomposition
method, that you are able to see that hey there is a there's a distinction in
the amount of time it takes to find the inverse by these two different
methods. To illustrate it, this is what you can see right here this is the total time taken by Gaussian elimination, which we just found out, this is the total time it takes by using LU composition method, that we just found out, and now if I had to find the ratio between the computational time it takes to find the inverse of matrix by using Gaussian elimination to the computational time to find inverse by LU decomposition method, all I'm doing is I'm dividing this quantity by this quantity. That's all I'm doing. And I did for different values of N. And you can see that suppose if I trying to find the inverse for 10,000 by 10,000 matrix, the computational time to take me to find the inverse by Gaussian elimination there will be about 2,500 times what it will take me to find by LU decomposition method. Let's suppose so, to give you some perspective, let’s suppose it takes one second to find the inverse of the 10,000 by 10,000 matrix by using the LU decomposition method it'll take 2501 seconds to do it with Gaussian elimination. And 2501 seconds is approximately 41 minutes. So, what are you finding out is that hey if it's gonna take 41 minutes for me to find the inverse using Gaussian elimination as opposed to one second with LU decomposition method. Do you know where the priority is your priority should lie… The general formula for large N, so far as the proportion of the times can ratio of the time is concerned, it is N divided by four as you must have seen here there for thousands about 250, for ten thousands about twenty five hundred, four hundred it's about twenty five, so that's what that comes from that for large N this is approximately N divided four. You can derive it, of course, because the for large N the amount of time it takes to find the inverse by using Gaussian elimination is this quantity right here, and then the amount of time it takes to do LU decomposition, because N is large, we can know mean we can get away with taking only the first term of that expression and this one turns out to be N divided by four. So, that's where that comes from. So, I'm hoping that by listening to this particular lecture that you are able to see that in the first instance when you look at it you think that LU decomposition method is just like Gaussian elimination, may be even more complicated or may be more complex than Gaussian elimination. Why do we learn this particular method? Is that because when we have multiple right-hand sides such as when you are trying to find inverse of matrix it is a computationally more efficient way of finding the inverse of a matrix then by using Gaussian elimination. And, that is the end of this segment. |