稀疏矩阵的矩阵乘法速度是否比密集矩阵快？ [关闭]

Question

关闭。这个问题是opinion-based。它当前不接受答案。

---

是否要改善此问题？更新问题，以便editing this post可以用事实和引用来回答。

[<11天前关闭。

稀疏矩阵的矩阵乘法速度是否比密集矩阵快？举一个简单的例子确实“ [[[0,0]，[0,0]]乘以[[1,1]，[1,1]]”比...快“ [[[256,256]，[256,256]]乘以[[1,1]，[1,1]]”？

Answer 1

执行乘法的机器代码算法如下：

int mul(int a,int b)
 {
    int result = 0;
    bit sign = sign(a) ^ sign(b);
    a = abs(a); b = abs(b);

    while (b != 0)
     {
        b = b>>1; // shift b right, bit0 into carry
        if (carrySet()) result += a;
        a = a<<1; // shift a left
        // note: checks for overflow being left out
     }
    return (sign==0 ? sum : -sum);
 }

您将很容易看到，在右操作数中设置的位数越多，累加左操作数所需要的计算就越多。因此，只要您的矩阵乘法可以归结为这样的机器代码乘法，那么稀疏矩阵的乘法将比密集矩阵的乘法快得多。
我在这里无法回答的问题是FPU是否将以更有效的方式执行此操作。您将在这里阅读一些规格。但是，即使FPU（或GPU）进行某种调整，我也怀疑基本的乘法磨削循环看起来有很大不同（对此感兴趣）。