矩阵乘法：Strassen 与标准

I tried to implement the Strassen algorithm http://en.wikipedia.org/wiki/Strassen_algorithm for matrix multiplication with C++, but the result isn't that, what I expected. As you can see strassen always takes more time then standard implementation and only with a dimension from a power of 2 is as fast as standard implementation. What went wrong?

matrix mult_strassen(matrix a, matrix b) {
if (a.dim() <= cut)
    return mult_std(a, b);

matrix a11 = get_part(0, 0, a);
matrix a12 = get_part(0, 1, a);
matrix a21 = get_part(1, 0, a);
matrix a22 = get_part(1, 1, a);

matrix b11 = get_part(0, 0, b);
matrix b12 = get_part(0, 1, b);
matrix b21 = get_part(1, 0, b);
matrix b22 = get_part(1, 1, b);

matrix m1 = mult_strassen(a11 + a22, b11 + b22); 
matrix m2 = mult_strassen(a21 + a22, b11);
matrix m3 = mult_strassen(a11, b12 - b22);
matrix m4 = mult_strassen(a22, b21 - b11);
matrix m5 = mult_strassen(a11 + a12, b22);
matrix m6 = mult_strassen(a21 - a11, b11 + b12);
matrix m7 = mult_strassen(a12 - a22, b21 + b22);

matrix c(a.dim(), false, true);
set_part(0, 0, &c, m1 + m4 - m5 + m7);
set_part(0, 1, &c, m3 + m5);
set_part(1, 0, &c, m2 + m4);
set_part(1, 1, &c, m1 - m2 + m3 + m6);

return c; 
}

g++ main.cpp matrix.cpp -o matrix -O3.

一些想法：

• 您是否对其进行了优化以考虑用零填充两个大小的非幂矩阵？我认为该算法假设您不必费心将这些项相乘。这就是为什么您会得到运行时间在 2^n 和 2^(n+1)-1 之间恒定的平坦区域。通过不乘以已知为零的项，您应该能够改进这些领域。或者也许 Strassen 只适用于 2^n 大小的矩阵。
• 考虑到“大”矩阵是任意的，并且该算法仅比简单情况 O(N^3) 与 O(N^2.8) 稍好。在尝试更大的矩阵之前，您可能不会看到可测量的收益。例如，我做了一些有限元建模，其中 10,000x10,000 矩阵被认为是“小”。从你的图表中很难看出，但看起来 511 情况在 Stassen 情况下可能更快。
• 尝试使用各种优化级别进行测试，包括根本不进行优化。
• 该算法似乎假设乘法比加法昂贵得多。 40 年前首次开发时确实如此，但我相信在更现代的处理器中，加法和乘法之间的差异已经变得更小。这可能会降低算法的有效性，该算法似乎减少了乘法，但增加了加法。
• 您是否查看过其他一些 Strassen 实现以寻求想法？尝试对一个已知良好的实现进行基准测试，看看您到底能快多少。