Morning Math-Exchange,
On my homework, we have a problem regarding divide a conquer for matrix multiplication; where if you are multiplying a (4×12) by (12×4) 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)…
Best 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.