Recursion in Strassen's Algorithm

问题:

I'm wondering how you would make the recursive calls in Strassen's algorithm, and where exactly they're required.

I understand that the 7 multipliers is more efficient than the 8 we would have otherwise, but I'm confused as to how these multipliers are calculated recursively. In particular, if we are following the divide and conquer paradigm, exactly which part of the matrices are we "dividing" and how are we going about doing that until we get to a base case in which we can conquer the recursive parts separately?

Thank you!

回答1:

We make recursive calls while calculating these 7 multipliers. At first we extend the size of the matrices to the power of 2 and then on each step we divide the each matrix into 4 pieces.

回答2:

We divide A and B evenly into quarters or sixteenths or sixty-fourths etc in order to reduce them to 2x2 matrices. Strassen's method can only be applied to matrices of type 2^n x 2^n.

For matrices not of type 2^n x 2^n you can zero pad until the requirement is met.