计算效率:稀疏与完全

Question

我发现如果一个矩阵(几乎)已满,那么将它存储在稀疏中会导致(更多)时间计算.

虽然以稀疏形式存储完整矩阵是微不足道的,但我只是想知道这个事实背后的原因.

我的猜测是稀疏的索引读数将是计算时间的主要贡献者.还有其他优雅的想法？

Answer 1

几乎完全稀疏矩阵比仅使用完整矩阵在计算上更昂贵的原因有几个.正如您所指出的,最明显的是稀疏元素必须被索引(对于一般的稀疏矩阵,我相信Matlab使用压缩行存储方案).

另一个不太明显的减速是由于向量化和将数据流水线化到处理器中.在完全存储矩阵的情况下,数据采用整齐的线性格式,因此操作可以很容易地进行矢量化.对于像CRS这样的存储方案,情况并非如此,特别是对于Matrix*Vector操作,这些操作往往是最常用的(例如,当使用迭代求解器来求解方程组时).对于CRS方案,在矩阵行上移动可以以漂亮的线性方式馈送到处理器,然而,从矩阵乘以的向量中拉出的元素将跳转.

Answer 2

考虑以下密集矩阵:

1 2 3
4 5 6
7 8 9

如果我将它存储在一个连续的块中:

1 2 3 4 5 6 7 8 9

我可以使用一些基本算法直接访问给定行号和列号的矩阵元素.

现在考虑这个稀疏矩阵:

1 0 0
0 0 2
0 3 0

为了有效地存储这个矩阵,我丢弃了非零元素,现在它变成了

1 2 3

但这显然不足以进行像矩阵向量乘法这样的操作!因此,我们需要添加其他信息以从矩阵中提取元素.

但是你可以看到,无论使用何种存储方法,我们都需要

1. 做额外的工作来访问元素
2. 存储更多信息以保持矩阵的结构

正如您所看到的,只有当矩阵中有足够的零来补偿我们存储的额外信息以保留矩阵的结构时,才会产生存储的好处.例如,在耶鲁格式中,当非零(NNZ)值的数量小于(m(n ? 1) ? 1) / 2其中m=行n数和=列数时,我们仅节省内存 .