# Strassen's Algorithm for Non-Square Matrices

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)...

## 1 Answer

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.

• Huh...? Three square matrices? The square matrices are still (2x2) each right? – rezey Sep 21 '15 at 14:20
• 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? – rezey Sep 21 '15 at 14:27
• 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! – rezey Sep 21 '15 at 15:05