A x = b
Actually corresponds to two steps:
L y = b
U x = y
We count operations involved in transforming Ax=b to the problem Ly=b
. There will be n-1 steps:
Step1:
a) compute n-1 multipliers l1j, j=2:n
n-1 divides
b) perform n-1 rows operations
row2 <- row2 - l12 * row1
.
.
.
rown <- rown - l1n * row1
each of these rows operations works with the n-1
components (2:n) of the row since we know that
zeros will be appearing in column 1
(n-1)^2 multiplies
(n-1)^2 adds
Step2:
a) compute n-2 multipliers l2j, j=3:n
n-2 divides
b) perform n-2 rows operations
row3 <- row3 - l23 * row2
.
.
.
rown <- rown - l2n * row2
each of these rows operations works with the n-2
components (3:n) of the row since we know that
zeros appeared in column 1 in Step 1b and will be
appear as a result of this step in column 2.
(n-2)^2 multiplies
(n-2)^2 adds
Step(n-1):
a) compute the multiplier ln-1,n 1 divide
b) perform 1 row operation
rown <- rown - ln-1,n * row(n-1)
1 multiply
1 add
There are some very handy results from combinatorics that let us simply sums
M M(M+1) SUM j = 1 + 2 + ... + M = ------ j=1 2 M M(M+1)(2M+1) SUM j^2 = 1 + 2^2 + ... + M^2 = ------------ j=1 6
(These can be proved by induction, by it would be easier if you would just believe me. Or test it yourself for some small value of m, or come see me in office hours and we'll go through by the proof by induction - but send me email ahead of time so I can prepare cause I probably can't do this off the top of my head.)
In our use M = n-1 above.
This whole process comsumes:
(n-1)n
1 + 2 + ... + n-2 + n-1 divides = ------ divides
2
(n-1) n [2(n-1)+1]
1 + 2^2 + ... + (n-1)^2 adds = ------------------ adds
6
And the same number of multiplies which can be simplified
n (n-1) (2n-1) 2n^3 - 3n^2 + n
-------------- = ---------------
6 6
n^3
~ --- for large n for the count of adds/mults
3
U x = y
This costs:
n(n+1)
cost in FLOPS is 1 + 2 + ... + n multiplies/divides = ------
2
n(n-1)
0 + 1 + ... + n-1 adds/subtracts = ------
2
Back to Report2_Diffusion