V. Pan has discovered a way of multiplying 68X 68 matrices using 132,464 multiplications, a way of multiplying 70 X70 matrices using 143,640 multiplications, and a way of multiplying 72 X72 matrices using 155,424 multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? Compare it with the running time for Strassen's algorithm.
- LeslieLv 71 0 年前最佳解答
The strassen's divide-and-conquer algorithm for matrix multiplication
has the recurrence for its time complexity
(considering only the counts of scalar multiplications):
T(n) = 7 T(n/2), with the solution
T(n) = O(n^log(2,7)) = O(n^2.807355...)
If, just like Strassen's algorithm, we divide an
nxn matrix into smaller matrices (recursively),
but each with size (n/68)x(n/68), then
when two 68x68 matrices can be multiplied by
132464 scalar multiplications, we'll have the recurrence
T(n) = 132464 T(n/68).
Similarly, the other two ways will have their recurrence:
T(n) = 143640 T(n/70) and
T(n) = 155424 T(n/72), respectively.
The solutions are (respectively) (with big O sign omitted)
n^log(68, 132464) = n^2.795128...,
n^log(70, 143640) = n^2.795122..., and
n^log(72, 155424) = n^2.795147....
So, the 2nd method is the fastest (in theory), and
all of the three Victor Y. Pan's algorithms are better than
(1) I used log(b, v) to mean "log v with base b".
(2) The solution to the recurrence T(n) = a T(n/c) is
n^(log(c, a)) in our case, which is covered by
the "Master Theorem". See Theorem 3.1 on參考資料： Leslie's ALGORITHM lecture notes