矩阵乘法，当一个尺寸远远大于其他

Question

所以我读了施特拉森的矩阵乘法算法的复杂度为O（n^2.8） 但它只能如果A为n×n和B是n×n的 如果 A是MXN和B是NXO ，m是比N和O非常非常大，但N和O仍然是非常大的 填充用零可能使乘法需要更长的时间

我这样做，需要这样一个矩阵的乘法这样一个项目，我希望得到一些建议 我应该使用传统的算法还是有办法修改Strassen的算法来更快地实现它？

Answer 1

https://en.m.wikipedia.org/wiki/Strassen_algorithm

• 大小的产物[2N×N个] * [N X 10N]可以做到20个单独的[N×N个] * [N X N]的操作，设置成形成结果;

• 大小为[N×10N] * [10N×N]的乘积可以作为10次单独的[N×N] * [N×N]运算完成，相加形成结果。

这些技术将使实现更复杂，相比之下，简单地填充到2的幂次方;然而，这是一个合理的假设，任何人实施斯特拉森而不是传统的乘法，将会使计算效率的优先级高于实现的简单性。