algorithm - 施特拉森矩阵乘法

Question

嗯，是《算法导论》的一道题，题号是4.2-6 .是这样描述的:

你能多快倍增a kn*n matrix by an n*kn matrix , 使用 Strassen's algorithm作为 subroutine ？

我正在考虑将两个矩阵扩展到 kn*kn matrix ，那么我可以将 Strassen 的算法应用到这个问题上。但我会得到一个Math.pow(kn, lg7) running time .

有没有人有更好的解决方案。祝大家新年快乐。

Answer 1

思考而不是将 k*1 向量乘以 1*k 向量。这需要 k^2 次乘法，最后得到一个 k*k 矩阵。这里唯一不同的是你的向量的元素是 n*n 矩阵，所以如果你使用 Strassen 的算法将 n*n 相乘，你最终会做 O(k^2 n​​^(log 7)) 标量乘法矩阵。