In-place implementation of Strassen algorithm?

Question

I managed to implement an in-place solution though index manipulations for naive Divide & Conquer algorithm for matrix multiplication which requires 8 recursive calls in each recurrence. However, when trying to implement Strassen algorithm, I couldn't find a way to do it in-place. Instead, I have to malloc 19 sub matrices for the 7 recursive calls while using C to program.

How to implement Strassen algorithm in-place? Or is it possible?

Answer 1

Say you're multiplying two nxn matrices. You'll need room for 4n^2 integers: 2n^2 for the matrices being multiplied, n^2 for the result, and a final n^2 for scratch work. You use the scratch work matrix recursively. That is, you use 1/4 of it for each of the two submatrices you create by adding in Strassen's, 1/4 for the result of the multiplication, and the final 1/4 for the scratch work of that multiplication. Etc... as far as you want to recurse.