algorithm - Strassen算法的就地实现？

Question

我设法通过索引操作实现了一个就地解决方案，用于矩阵乘法的天真的分治算法，每次重复需要 8 次递归调用。但是，在尝试实现 Strassen 算法时，我找不到就地执行它的方法。相反，我必须在使用 C 编程时为 7 个递归调用分配 19 个子矩阵。

如何就地实现 Strassen 算法？或者有可能吗？

Answer 1

假设您将两个 nxn 矩阵相乘。您将需要 4n^2 个整数的空间：2n^2 用于相乘的矩阵，n^2 用于结果，最后一个 n^2 用于临时工作。您递归地使用临时工作矩阵。也就是说，您将其中的 1/4 用于通过添加 Strassen 创建的两个子矩阵中的每一个，1/4 用于乘法的结果，最后的 1/4 用于该乘法的临时工作。等等......只要你想递归。