3
$\begingroup$

Square-Matrix-Multiply-Recursive

The above image, describing Strassen's matrix multiplication algorithm, is from the book Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. The algorithm multiplies two square matrices of order $n$, where $n$ is a power of $2$, i.e., $n=2,4,8,16,32,\dots$ and so on.

Can this algorithm be modified so that we can multiply two square matrices of order $n$, for all $n$?

$\endgroup$
3
  • $\begingroup$ I don't have my copy of CLR to hand, so I can't check: is this one of the exercises later in the chapter? If so, does that give any hints? $\endgroup$ Commented Oct 1, 2018 at 13:35
  • $\begingroup$ Pad the matrices with zeros. $\endgroup$ Commented Oct 1, 2018 at 13:52
  • $\begingroup$ In the first edition, this was exercise 31.2-2. $\endgroup$ Commented Oct 2, 2018 at 18:57

1 Answer 1

3
$\begingroup$

The solution is to pad the matrices with zeroes, using the block matrix identity $$ \begin{bmatrix} A & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} B & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} AB & 0 \\ 0 & 0 \end{bmatrix} . $$

Here $A,B$ are $n\times n$ matrices, and the big matrices are $N\times N$ for some $N > n$. In other words, we add $N-n$ rows and $N-n$ columns of zeroes.

You can do this in two ways:

  • Pad the original $n \times n$ matrices to $N \times N$ matrices, where $N$ is the closest power of 2. Note that $N < 2n$, so this doesn't affect the asymptotic complexity.

  • Pad the matrices recursively. Whenever a recursive call gets $m \times m$ matrices with $m > 1$ odd, we pad them to $(m+1) \times (m+1)$ matrices by adding a single row and a single column of zeroes. This also doesn't affect the asymptotic complexity.

A third option is to make use of, say, a 3x3 matrix multiplication algorithm if the dimension is odd but divisible by 3. Laderman found such an algorithm which uses 23 multiplications (instead of the trivial 27).

$\endgroup$
7
  • $\begingroup$ this would alter the complexity of the algorithm. $\endgroup$
    – Sc00by_d00
    Commented Oct 2, 2018 at 10:05
  • $\begingroup$ Say for n=27 and n=32 we would have same asymptotic complexity. $\endgroup$
    – Sc00by_d00
    Commented Oct 2, 2018 at 10:06
  • $\begingroup$ because we would actually be multiplying 32 X 32 matrix padded with zeros instead of 27 X 27 matrix. So can't the algorithm be modified keeping the complexity of the algorithm unaltered ? $\endgroup$
    – Sc00by_d00
    Commented Oct 2, 2018 at 10:09
  • $\begingroup$ @Sc00by_d00, it doesn't affect the complexity of the algorithm, assuming it's in $P$, because the padding is by a bounded factor. $\endgroup$ Commented Oct 2, 2018 at 11:45
  • $\begingroup$ The asymptotic complexity doesn’t depend on constant factors, which is all you lose here. $\endgroup$ Commented Oct 2, 2018 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.