algorithm - 如何使用施特拉森算法将除 2 次方以外的度数矩阵相乘？

Question

我正在学习算法课程。在谈到分而治之时，我遇到了施特拉森算法。

所以，问题是我们如何乘以奇数度的矩阵，或者不是 2 的幂的偶数度数？

此外，我们如何将 Strassen 算法应用于不同维度的矩阵（例如将 2X3 矩阵与 3X1 矩阵相乘）？

标签： algorithmmatrix-multiplicationstrassen

Answer 1

说矩阵是 degree n。如果你想相乘A，你可以做一件简单的事情，就是用零B填充A和（比如，这样它们是暗淡的，其中2 的最小幂是上限。因为最多是原始尺寸的两倍，BA_padB_pad(k,k)knk

k^log_2(7)<=3 * N^log_2(7)

所以算法依旧O(N^log_2(7))。

在其中一个矩阵“薄”（例如 A 的长度支配 A 的高度）的情况下，这种方法不太适用于不同维度的矩阵。在这种情况下，您需要对矩阵进行切片以获得更像正方形的矩阵，正如@neil-edelman 的评论所述。您确定薄度的方法可能是查看是否预先选择BND>dim(A)[1]/dim(A)[0]>bnd了一些常数参数bnd，BND接近 1。