Strassen’s Matrix Multiplication:

The matrix multiplication of algorithm due to Strassens is the most dramatic example of divide and conquer technique (1969).

The usual way to multiply two n x n matrices A and B, yielding result matrix ‘C’ as follows :

for i := 1 to n do
   for j :=1 to n do
       c[i, j] := 0;
       for K: = 1 to n do
           c[i, j] := c[i, j] + a[i, k] * b[k, j];

This algorithm requires $n^3$ scalar multiplication’s (i.e. multiplication of single numbers) and $n^3$ scalar additions. So we naturally cannot improve upon.

We apply divide and conquer to this problem. For example let us considers three multiplication like this:

Then $c_{ij} $ can be found by the usual matrix multiplication algorithm,

$C_{11} = A_{11} . B_{11} + A_{12} . B_{21}$

$C_{12} = A_{11} . B_{12} + A_{12} . B_{22}$

$C_{21} = A_{21} . B_{11} + A_{22} . B_{21}$

$C_{22} = A_{21} . B_{12} + A_{22} . B_{22} $

This leads to a divide–and–conquer algorithm, which performs nxn matrix multiplication by partitioning the matrices into quarters and performing eight (n/2)x(n/2) matrix multiplications and four (n/2)x(n/2) matrix additions.

$$T(1) = 1$$

$$T(n) = 8T(n/2)$$

Which leads to T (n) = O ($n^3$), where n is the power of 2.

Strassens insight was to find an alternative method for calculating the $C_{ij}$, requiring seven (n/2) x (n/2) matrix multiplications and eighteen (n/2) x (n/2) matrix additions and subtractions:

$P = (A_{11} + A_{22}) (B_{11} + B_{22})$

$Q = (A_{21} + A_{22}) B_{11}$

$R = A_{11} (B_{12} – B_{22})$

$S = A_{22} (B_{21} - B_{11})$

$T = (A_{11} + A_{12}) B_{22}$

$U = (A_{21} – A_{11}) (B_{11} + B_{12})$

$V = (A_{12} – A_{22}) (B_{21} + B_{22})$

$C_{11} = P + S – T + V$

$C_{12} = R + T$

$C_{21} = Q + S$

$C_{22} = P + R - Q + U.$

This method is used recursively to perform the seven (n/2) x (n/2) matrix multiplications, then the recurrence equation for the number of scalar multiplications performed is:

$$T(1) = 1$$

$$T(n) = 7 T(n/2)$$

Solving this for the case of n = $2^k$ is easy:

$$T(2^k) = 7\ T(2^{k–1})$$

$$T(2^k) = 7^2\ T(2^{k–2})$$

$$T(2^k) = -----$$

$$T(2^k) = ----$$

$$T(2^k) = 7^i T(2^{k–i})$$

Put i = k,

$$\ = 7^k\ T(1)$$

$$\ = 7^k$$

That is, $$T(n) = 7 log_{2}^n$$

$$T(n) = n log_{2}^7$$

$$T(n) = O(n log_{2}^7) = O(2_{n}^{81})$$

So, concluding that Strassen’s algorithm is asymptotically more efficient than the standard algorithm. In practice, the overhead of managing the many small matrices does not pay off until ‘n’ revolves the hundreds.