标签: strassen

有人可以用直观的方式解释strassen的矩阵乘法算法吗？我已经完成了(好了,试图通过)书中的解释和维基,但它没有点击楼上.网络上使用大量英语而非正式表示法等的任何链接也会有所帮助.是否有任何类比可以帮助我从头开始构建这个算法而不必记住它？

我已经写方案C++,Python和Java的矩阵乘法和测试他们的速度有两个2000×2000矩阵(见相乘后).标准的ikj-implementntation - 在 - 拿:

• C++:15秒(来源)
• Python:6分13秒(来源)

现在我已经实现了用于矩阵乘法的Strassen算法 - 它在 - 在维基百科上的Python和C++中.这些是我的时代:

• C++:45分钟(来源)
• Python:10小时后被杀(来源)

为什么Strassen矩阵乘法比标准矩阵乘法慢得多？

• 一些缓存效果
• 执行:
  • 错误(生成的2000 x 2000矩阵是正确的)
  • null-multiplication(对于2000 x 2000 - > 2048 x 2048不应该那么重要)

这尤其令人惊讶,因为它似乎与其他人的经历相矛盾:

• 为什么我的Strassen Matrix倍增器如此之快？
• 矩阵乘法:Strassen vs. Standard - Strassen对他来说也较慢,但它至少在同一数量级.

编辑:在我的情况下,Strassen矩阵乘法较慢的原因是:

• 我把它完全递归(见tam)
• 我有两个函数strassen和strassenRecursive.第一个将矩阵的大小调整为2的幂,如果需要,称为第二个.但是strassenRecursive没有递归地称呼自己,但是strassen.

我用C++写了两个矩阵乘法程序:常规MM (源)和Strassen的MM (源),它们都在大小为2 ^ kx 2 ^ k的矩形矩阵上运算(换句话说,是偶数大小的方阵).

结果很可怕.对于1024 x 1024矩阵,常规MM需要46.381 sec,而Strassen的MM需要1484.303 sec(25 minutes!!!!).

我试图让代码尽可能简单.在网上找到的其他Strassen的MM示例与我的代码没有太大的不同.Strassen代码的一个问题显而易见 - 我没有切换点,切换到常规MM.

我的Strassen的MM代码有哪些其他问题？

谢谢 !

直接链接到源
http://pastebin.com/HqHtFpq9
http://pastebin.com/USRQ5tuy

EDIT1.拳头,很多很棒的建议.感谢您抽出宝贵时间和分享知识.

我实施了更改(保留了我的所有代码),添加了截止点.具有截止512的2048x2048矩阵的MM已经给出了良好的结果.常规MM:191.49s Strassen的MM:112.179s显着改善.使用英特尔迅驰处理器,使用Visual Studio 2012,在史前联想X61 TabletPC上获得了结果.我将进行更多检查(以确保我得到正确的结果),并将发布结果.

我正在使用python实现Strassen的Matrix Multiplication.在除法步骤中,我们将较大的矩阵划分为较小的子矩阵.是否有内置的numpy函数来分割矩阵？

这是我关于stackoverflow的第一个问题.我一直在解决Tamassia的Goodrich的"算法设计"中的一些练习.但是,我对这个问题很无能为力.Unusre从哪里开始以及如何继续.任何建议都会很棒.这是问题所在:

布尔矩阵是矩阵,使得每个条目为0或1,并且通过使用AND for*和OR for +来执行矩阵乘法.假设我们给出了两个NxN随机布尔矩阵A和B,因此任一条中的任何条目为1的概率为1/k.证明如果k是常数,那么有一个算法用于乘以A和B,其预期运行时间为O(n ^ 2).如果k是n怎么办？

我尝试使用C++ 实现Strassen算法进行矩阵乘法,但结果不是我所期望的.正如您所看到的,strassen总是花费更多时间,然后标准实现,并且只有2的幂的维度与标准实现一样快.什么地方出了错？

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, …

我从某处复制了strassen的算法,然后执行了它.这是输出

n = 256
classical took 360ms
strassen 1 took 33609ms
strassen2 took 1172ms
classical took 437ms
strassen 1 took 32891ms
strassen2 took 1156ms
classical took 266ms
strassen 1 took 27234ms
strassen2 took 734ms

strassen1动态方法在哪里,strassen2对于缓存而言classical是旧的矩阵乘法.这意味着我们古老而简单的经典之作是最好的.这是真的还是我错了？这是Java中的代码.

import java.util.Random;

class TestIntMatrixMultiplication {

    public static void main (String...args) throws Exception {
        final int n = args.length > 0 ? Integer.parseInt(args[0]) : 256;
        final int seed = args.length > 1 ? Integer.parseInt(args[1]) : 256;
        final Random random = new …

我正在努力确定为什么我的Strassen实现如此缓慢.它会在每次迭代时分配内存,但我会在适当时释放它们.

int** multiply(int** a, int** b, int size)
{
int row,col,i,j;

if(size == 1)
{
    int** c = allocate(size);
    c[0][0] = (a[0][0] * b[0][0])%2;
    return c;
}

if(size <= 2)
{
    int a11,a12,a21,a22,b11,b12,b21,b22;    
    int** c = allocate(size);
    a11 = a[0][0];
    a12 = a[0][1];
    a21 = a[1][0];
    a22 = a[1][1];
    b11 = b[0][0];
    b12 = b[0][1];
    b21 = b[1][0];
    b22 = b[1][1];

    c[0][0] = (a11*b11 + a12*b21)%2;
        c[0][1] = (a11*b12 + a12*b22)%2;
        c[1][0] = (a21*b11 + a22*b21)%2;
    c[1][1] = (a21*b12 + …