2
$\begingroup$

Morning Math-Exchange,

On my homework, we have a problem regarding divide a conquer for matrix multiplication; where if you are multiplying a (4x12) by (12x4) the original total of multiplications is 192, but can be further dropped to 147.

I get that why the original big O for this problem is 192 for the total amount of multiplication because you need to multiply this by 4*12*4 and know Strassen's algorithm for square matrices, but not for non-square matrices...

I know according to the Wikipedia page for Strassen's algorithm that I need to turn the dimensions to closer to 2^n by filling the remaining rows/columns to 0's so you can make smaller square matrices, but I do not know what to do after that and how to cut the number of multiplications to 147 with 2^2 (no zeroes needed here) and 2^4 (Added 4 more to the 12)...

$\endgroup$
2
$\begingroup$

Write your left factor as a row of three square matrices and your right factor as a column of three square matrices. Then use Strassen.

$\endgroup$
  • $\begingroup$ Huh...? Three square matrices? The square matrices are still (2x2) each right? $\endgroup$ – rezey Sep 21 '15 at 14:20
  • $\begingroup$ Forget the last comment, sorry; I used Strassen for each 2x2 as a factor by 3, by expanding the 4 to 6, and with that, gave me 7 multiplication for each 2x2 and multiplied by 18, but got 126...? Am I doing Strassen right? $\endgroup$ – rezey Sep 21 '15 at 14:27
  • 1
    $\begingroup$ Never mind... I feel really awful for making this more difficult than it seems; just turn the matrices by (4x4) matrix cells which in turn makes the total number of multiplications for each one 49, and multiply it by 3 because that's the total amount of (4x4) partitions, thus giving 147... Big thanks! $\endgroup$ – rezey Sep 21 '15 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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