/sci/ - Science & Math

The third parameter is the output, so PROC(X, Y, Z) would calculate X \cdot Y and store it in Z. So something like

//construct A, B somehow
double[][] Result = new double[n][n];
PROC(A, B, Result);
//Result is now the product of A, B

Write A and B as sums of 4 nxn matrices (each) where A1 is zero except in the upper left quarter, A2 is zero except in the upper right, A3 zero except in the lower left, and A4 zero except in the lower right. Similar for B. So if

A =
[1,2]
[3,4]

then

A1 =
[1,0]
[0,0]

A2 =
[0,2]
[0,0]

A3 =
[0,0]
[3,0]

A4 =
[0,0]
[0,4]

Then A*B = (A1+A2+A3+A4)*(B1+B2+B3+B4), but A2 or A4 times B1 or B2 will be zero, and so are A1 or A3 times B3 or B4 (because when you do the matrix multiplication, any entry that isn't zero is going to be multiplied by zeros from the other matrix) so that simplifies to

(A1+A3)*(B1+B2)+(A2+A4)*(B3+B4)

Multiplying any two of these smaller matrices (A1, A2, ...) gives a result that's zero except in one quadrant, and the quadrants of the result come out like this

Upper left = A1*B1 + A2*B3
Upper right = A1*B2 + A2*B4
Bottom left = A3*B1 + A4*B3
Bottom right = A3*B2 + A4*B4

Now since you're effectively only multiplying n/2 x n/2 matrices, you can trim off all the zeros and think of A1, A2, etc. as n/2 x n/2 matrices. Then "A(n/2+1:n,1:n/2)" is A3 and so on. The values of P1, ..., P7 from the worksheet are:

P1 = (A1 + A4) * (B1 + B4)
P2 = (A3 + A4) * B1
P3 = A1 * (B2 - B4)
P4 = A4 * (B3 - B1)
P5 = (A1 + A2) * B4
P6 = (A3 - A1) * (B1 + B2)
P7 = (A2 - A4) * (B3 + B4)

and the formulas for the result give

Upper left = P1+P4-P5+P7 = A1*B1 + A2*B3
Upper right = P3+P5 = A1*B2 + A2*B4
Bottom left = P2+P4 = A3*B1 + A4*B3
Bottom right = P1+P3-P2+P6 = A3*B2 + A4*B4

as above. The only justification for making it this horribly complicated is that you wind up only needing 7 matrix multiplications at each recursion step instead of 8.

<span class="math">f(x) = -f(a-x) + C[/spoiler]. Letting <span class="math">x = 0[/spoiler] gives <span class="math">C = f(0) + f(a)[/spoiler].

<span class="math">\int_0^a f(x) dx + \int_0^a f(a-x)dx = \int_0^a [f(x) + f(a-x)] dx = a [f(0) + f(a)][/spoiler].

But <span class="math">\int_0^a f(a-x) dx = -\int_0^a f(x) dx[/spoiler], so <span class="math">\int_0^a f(x) dx = \frac{a}{2} [f(0) + f(a)][/spoiler]

<span class="math">f(x) = -f(a-x) + C[/spoiler]. Letting <span class="math">x = 0[/spoiler] gives <span class="math">C = f(0) + f(a)[/spoiler].

<span class="math">\int_0^a f(x) dx + \int_0^a f(a-x)dx = \int_0^a [f(x) + f(a-x)] dx = a [f(0) + f(a)][/spoiler].

But <span class="math">\int_0^a f(a-x) dx = -\int_0^a f(x) dx[/spoiler], so <span class="math">\int_0^a f(x) dx = \frac{1}{2} [f(0) + f(a)][/spoiler]

>>4359990

>>4308674