It is
interesting that
matrix multiplication (on
square matrices) can be performed with time bounds considerably lower than O(n^3). In fact, it is
not known that multiplying 2
n*n square matrices cannot be done in time O(n^2) (although
nobody believes that this is possible).
The current best bound on multiplication is O(n^2.31), and is suitable only for unreasonably large matrices. The first better-than-O(n^3) algorithm was due to Strassen. It is very simple, and explained below.
We shall only be concerned with mutiplying matrices when n=2^k (although any matrix can be zero-padded to attain this size, which just multiplies the time by some constant factor). To multiply 2 such matrices, divide each into 4 equal-sized blocks, and multiply as follows:
(A | B) (E | F) (AE+BG | AF+BH)
(--+--) (--+--) = (------+------)
(C | D) (G | H) (CE+DG | CF+DH)
So it would appear that to multiply 2 large matrices, we need to multiply 8 pairs of half-sized matrices; this would save us no time. So let's get by with only 7 multiplications!
Additions and
subtractions can be done in time
proportional to the size of the matrix, so we're less worried about them.
Define the following seven n/2 * n/2 matrices:
- a = (A+D)*(E+H)
- b = (C+D)*E
- c = A*(F-H)
- d = D*(G-E)
- e = (A+B)*H
- f = (C-A)*(E+F)
- g = (B-D)*(G+H)
Then all four submatrices of the desired result are sums of these 7 matrices:
- AE+BG = a+d-e+g
- AF+BH = c+e
- CE+DG = b+d
- CF+DH = a+f-b+c
How long does it take? Well, obviously we're going to multiply our smaller matrices using the same
algorithms,
recursively. All the additions and subtractions used to combine the smaller matrices are O(n^2) (since we only make a fixed number of them, and each takes time O(n^2)), so we get the recurrence
T(n) = O(n^2) + 7*T(n/2)
This has solution
T(n) = c*n^2 * (1 + 7/4 + 49/16 + (7/4)^(k-1)) =
= c' * 7^k = O(n ^ (lg_2 7))
and the
exponent of n is less than 2.81.