所以我读到 Strassen 的矩阵乘法算法具有复杂度 O(n^2.8) 但它仅在 A 为 n x n 且 B 为 n x n 时有效 如果什么 A 是 m x n,B 是 n x o m 比 n 和 o 大得多,但 n 和 o 仍然很大 用零填充可能会使乘法花费更长的时间
我在做一个需要乘法这样的矩阵的项目,所以我希望能得到一些建议 我应该使用传统算法还是有办法修改 Strassen 的算法以更快地完成?
最佳答案
https://en.m.wikipedia.org/wiki/Strassen_algorithm
A product of size [2N x N] * [N x 10N] can be done as 20 separate [N x N] * [N x N] operations, arranged to form the result;
A product of size [N x 10N] * [10N x N] can be done as 10 separate [N x N] * [N x N] operations, summed to form the result.
These techniques will make the implementation more complicated, compared to simply padding to a power-of-two square; however, it is a reasonable assumption that anyone undertaking an implementation of Strassen, rather than conventional, multiplication, will place a higher priority on computational efficiency than on simplicity of the implementation.
关于algorithm - 一维远大于另一维时的矩阵乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37799530/