2

我生成了一个稀疏度为 0.5 的矩阵，我想知道它乘以密集向量与以正常方式乘法相比的速度。 

function sparseTest()
    A = sprand(1000, 1000, 0.5);
    test(A);
    test(full(A));
end
function test(A)
    tic;
    b = rand(size(A, 2), 1);
    for i = 1:10000
        c = A * b;
    end
    toc;
end

结果是 

Elapsed time is 10.968797 seconds.
Elapsed time is 10.194440 seconds.

让我感到困惑的是，由于只有一半非零数字，我认为稀疏乘法应该以某种方式更快。

4

1 回答 1

11

不，那根本不是稀疏矩阵。您误解了稀疏矩阵何时有用。我们这些经常使用它们的人会说矩阵并不是真正稀疏的，除非它的密度小于 1%。甚至那个密度也不是很稀疏！

稀疏矩阵在使用时有额外的簿记，因为现在 MATLAB 基本上需要担心非零在哪里。因此，如果您制作一个本质上是密集矩阵的矩阵，并假装它是稀疏的，那么您就违背了该工具的价值。

让我们做一两个比较。首先，一个完全密集的矩阵。我将使用来自文件交换的 Steve Eddins timeit 工具。这可以很好地估计花费的时间，并且不需要显式循环。

A = rand(1000);
As = sparse(A);
b = rand(1000,1);

whos A As
  Name         Size                 Bytes  Class     Attributes
  A         1000x1000             8000000  double              
  As        1000x1000            16008008  double    sparse

看到完全密集矩阵比稀疏矩阵占用的空间要少得多。

timeit(@() A*b)
ans =
   0.00039474

timeit(@() As*b)
ans =
    0.0023663

简单乘法中稀疏矩阵的开销太大了。

As = sprand(1000,1000,.5);
A = full(As);
b = rand(1000,1);

whos A As
Name         Size                Bytes  Class     Attributes
  A         1000x1000            8000000  double              
  As        1000x1000            6303448  double    sparse

在这里，这两个矩阵几乎没有显示稀疏版本的大小减少。因此，就所消耗的空间而言，称其为稀疏是浪费时间。同样，正如您发现的那样，乘法所花费的时间仍然不是收益。

timeit(@() A*b)
ans =
   0.00027594

timeit(@() As*b)
ans =
    0.0005011

但是，当矩阵更接近我在稀疏性方面的建议时会发生什么？

As = sprand(1000,1000,.01);
A = full(As);
b = rand(1000,1);

whos A As
  Name         Size                Bytes  Class     Attributes

  A         1000x1000            8000000  double              
  As        1000x1000             167176  double    sparse   

timeit(@() A*b)
ans =
   0.00023629

timeit(@() As*b)
ans =
   5.3167e-05

好的，所以现在这节省了一些空间。还有一些严肃的时间。

但实际上，乘法的时间并不是我们使用稀疏矩阵的原因。求解线性方程组所需的时间使我们使用稀疏矩阵。这可以节省大量资金，使用完整矩阵基本上无法解决问题。我的一个常见问题可能涉及 40000x40000 矩阵，密度可能为 0.02%。我会花几天时间等待完整版完成，但在这种情况下，只需几秒钟即可完成稀疏解决。

例如，考虑 gridfit，这是我在文件交换中的一个功能。它从分散的数据创建表面。在此示例中，该工具将需要求解具有 40000 个未知数的线性方程组。

timeit(@() gridfit(rand(100,1),rand(100,1),rand(100,1),linspace(0,1,200),linspace(0,1,200)))
ans =
      0.83624

所以对于一切，包括建立方程组，只用了不到 1 秒。

它解决的（在这种情况下，非方形）线性系统非常稀疏。

whos A
  Name          Size                 Bytes  Class     Attributes
  A         80100x40000            4126408  double    sparse

它有多稀疏？

nnz(A)
ans =
      237900

nnz(A)/40000
ans =
       5.9475

所以平均而言，每行只有 5.9475 个非零，有 40000 列。而且我们没有时间用那个系统来做一个完整的线性求解。至少我没有任何尝试的欲望。

于 2013-07-19T08:20:14.853 回答