Java Reference
In-Depth Information
this notation, we can think of matrix multiplication using divide and conquer in the
following way:
A
11
A
12
A
21
A
22
B
11
B
12
B
21
B
22
A
11
B
11
+ A
12
B
21
A
11
B
12
+ A
12
B
22
A
21
B
11
+ A
22
B
21
A
21
B
12
+ A
22
B
22
=
:
Of course, each of the multiplications and additions on the right side of this
equation are recursive calls on arrays of half size, and additions of arrays of half
size, respectively. The recurrence relation for this algorithm is
T(n) = 8T(n=2) + 4(n=2)
2
= (n
3
):
This closed form solution can easily be obtained by applying the Master Theo-
rem 14.1.
Strassen's algorithm carefully rearranges the way that the various terms are
multiplied and added together. It does so in a particular order, as expressed by the
following equation:
A
11
A
12
A
21
A
22
B
11
B
12
B
21
B
22
s
1
+ s
2
s
4
+ s
6
s
4
+ s
5
s
6
+ s
7
s
2
s
3
+ s
5
s
7
=
:
In other words, the result of the multiplication for an n n array is obtained by
a different series of matrix multiplications and additions for n=2 n=2 arrays.
Multiplications between subarrays also use Strassen's algorithm, and the addition
of two subarrays requires (n
2
) time. The subfactors are defined as follows:
s
1
= (A
12
A
22
) (B
21
+ B
22
)
s
2
= (A
11
+ A
22
) (B
11
+ B
22
)
s
3
= (A
11
A
21
) (B
11
+ B
12
)
s
4
= (A
11
+ A
12
) B
22
s
5
= A
11
(B
12
B
22
)
s
6
= A
22
(B
21
B
11
)
s
7
=
(A
21
+ A
22
) B
11
With a little effort, you should be able to verify that this peculiar combination of
operations does in fact produce the correct answer!
Now, looking at the list of operations to compute the s factors, and then count-
ing the additions/subtractions needed to put them together to get the final answers,
we see that we need a total of seven (array) multiplications and 18 (array) addi-
tions/subtractions to do the job. This leads to the recurrence
7T(n=2) + 18(n=2)
2
T(n)
=
(n
log
2
7
) = (n
2:81
):
T(n)
=
