Operation Count for LU Decomposition

[twoski]

Homework Statement

Consider the n x n matrix A = diag[1,3,1]

and vector x: (1,2,3)

Determine the number of operations needed to compute the LU decomposition of this n x n matrix.

The Attempt at a Solution

So for a general n x n matrix, my prof's notes say that LU decomposition takes n^{3}/3 - n/3 + mn^{2} operations for m right hand sides.

however this question is different since there are zeroes in the matrix. Specifically, there are only n-1 values on the left hand side of the diagonal that i need to deal with. So this means the total number of multiplications for getting the U matrix is 2(n-1) (because each multiplication affects the diagonal as well).

Does the nature of this matrix affect the operation count for the Lg=f and Ux=g calculations?

 

[Ray Vickson]

Homework Statement

Consider the n x n matrix A = diag[1,3,1]

and vector x: (1,2,3)

Determine the number of operations needed to compute the LU decomposition of this n x n matrix.

The Attempt at a Solution

So for a general n x n matrix, my prof's notes say that LU decomposition takes n^{3}/3 - n/3 + mn^{2} operations for m right hand sides.

however this question is different since there are zeroes in the matrix. Specifically, there are only n-1 values on the left hand side of the diagonal that i need to deal with. So this means the total number of multiplications for getting the U matrix is 2(n-1) (because each multiplication affects the diagonal as well).

Does the nature of this matrix affect the operation count for the Lg=f and Ux=g calculations?

Never mind using formulas that you may not really understand; just DO IT!. That is: compute the LU decomposition of your matrix A = diag[1,3,1]. How many computations did you perform?

 

[twoski]

The problem is, this is going to be one of many problems on an upcoming test, and there seems to be a general method for determining how many operations are needed... Given that there is a strict time limit, it might not be wise to manually tally up the operation counts...

Here is the portion of my prof's notes which details how operation counts are done... I suppose it might be easy to just alter the diagrams based on the zero structure of the matrix?

I find it hard to decipher what is actually going on in the diagram though. And the conversion from summation form is equally confusing.

 

[Ray Vickson]

The problem is, this is going to be one of many problems on an upcoming test, and there seems to be a general method for determining how many operations are needed... Given that there is a strict time limit, it might not be wise to manually tally up the operation counts...

Here is the portion of my prof's notes which details how operation counts are done... I suppose it might be easy to just alter the diagrams based on the zero structure of the matrix?

I find it hard to decipher what is actually going on in the diagram though. And the conversion from summation form is equally confusing.

OK, but that is (probably) NOT what the question asked: it said " ... LU decomposition of this n x n matrix", so it (presumably) had that particular matrix in mind, not just any general matrix. At least, that would be my interpretation when including the word "this".

I guess there could be a subtler issue at work here: if you can say "Aha... that matrix is very special" you can do much better than using the general LU Decomposition algorithm. However, a computer (not necessarily a human) would need to do a lot of preliminary work to "recognize" whether or not a matrix is special: it would need at least to examine each element of the matrix one-by-one, and probably do a lot more as well. A human, on the other hand, can just look at the matrix and make an instant conclusion. I must leave it up to you to decide on the "correct" interpretation, but maybe the best answer is to present two possible scenarios and to do the analysis for each.

 

[twoski]

For this question i believe that i have to determine the operation count for this specific matrix...

So there would only be 4 total operations to calculate the U matrix, and then i'd just add that to mn^2 i guess? I don't see where m actually comes into this since there's only one right hand side, so i suppose i could just say n^2 +4 is the answer?

 

[Ray Vickson]

For this question i believe that i have to determine the operation count for this specific matrix...

So there would only be 4 total operations to calculate the U matrix, and then i'd just add that to mn^2 i guess? I don't see where m actually comes into this since there's only one right hand side, so i suppose i could just say n^2 +4 is the answer?

Have you not noticed that your matrix is already a "U", so you don't need an "L"? That is, you don't need to do any work at all to put it into LU form; all you need to do is perform 3 divisions of the form $x_i = b_i/a_{ii}$, where $b$ is the given right-hand-side vector (which you called x, but I don't believe that is what was meant).

 

[twoski]

Apologies, i forgot to mention that my professor may have a different definition for what diag[1,3,1] means. In his example, the matrix for diag[1,3,1] looks like:

3 1 0
1 3 1
0 1 3

So in order to make this upper diagonal, we need to eliminate both bottom 1's, which means a total of 4 multiplications will occur before they are eliminated.