python - Scipy 稀疏矩阵 - 密集向量乘法性能 - block 与大型矩阵

Question

我有许多 scipy 稀疏矩阵(目前为 CSR 格式)，我需要将它们与密集的 numpy 一维向量相乘。该向量称为 G:

print G.shape, G.dtype
(2097152,) complex64

每个稀疏矩阵的形状都是 (16384,2097152) 并且非常稀疏。密度约为4.0e-6。我有一个包含 100 个稀疏矩阵的列表，称为 spmats。

我可以像这样轻松地将每个矩阵与 G 相乘:

res = [spmat.dot(G) for spmat in spmats]

这会按预期生成形状为 (16384,) 的密集向量列表。

我的应用程序对性能相当关键，所以我尝试了一种替代方法，即首先将所有稀疏矩阵连接成一个大的稀疏矩阵，然后只使用一次 dot() 调用像这样:

import scipy.sparse as sp
SPMAT = sp.vstack(spmats, format='csr')
RES = SPMAT.dot(G)

这会产生一个长向量 RES，其形状为 (1638400,)，并且是 res 中所有结果向量的串联版本> 以上，正如预期的那样。我检查过结果是否相同。

也许我完全错了，但我预计第二种情况应该比第一种情况更快，因为 numpy 调用、内存分配、python 对象的创建、python 循环等要少得多。我不在乎关于连接稀疏矩阵所需的时间，只有计算结果的时间。然而，根据 %timeit:

%timeit res = [spmat.dot(G) for spmat in spmats]
10 loops, best of 3: 91.5 ms per loop
%timeit RES = SPMAT.dot(G)
1 loops, best of 3: 389 ms per loop

我已经检查过我在这两个操作中都没有用完内存，而且似乎没有任何可疑的事情发生。我是疯了，还是这真的很奇怪？这是否意味着所有稀疏矩阵向量乘积都应该分 block 进行，一次几行，以使其更快？据我了解，稀疏矩阵与密集向量的乘法时间应该与非零元素的数量成线性关系，这在上述两种情况下都没有变化。是什么造成了如此大的不同？

我在一个单核 linux 机器上运行，4GB 内存，使用 EPD7.3

编辑:

这是一个为我重现问题的小例子:

import scipy.sparse as sp
import numpy as n

G = n.random.rand(128**3) + 1.0j*n.random.rand(128**3)

spmats = [sp.rand (128**2, 128**3, density = 4e-6, format = 'csr', dtype=float64) for i in range(100)]
SPMAT = sp.vstack(spmats, format='csr')

%timeit res = [spmat.dot(G) for spmat in spmats]
%timeit RES = SPMAT.dot(G)

我得到:

1 loops, best of 3: 704 ms per loop
1 loops, best of 3: 1.34 s per loop

这种情况下的性能差异不如我自己的具有某种结构的稀疏矩阵大(可能是因为缓存)，但连接矩阵仍然更糟。

我已经尝试过 scipy 10.1 和 12.0。

Answer 1

我还没有找到问题中提到的奇怪行为的原因，但是我找到了一种可以显着加快计算速度的方法，这可能对其他人有用。

因为在我的特定情况下，我正在计算 float32 稀疏矩阵和 complex64 密集向量的乘积，所以我可以分别乘以实部和虚部。这为我提供了 4 倍的加速。

使用 SPMAT.shape == (16384000, 2097152) 需要 2.35 秒:

RES = SPMAT.dot(G)

虽然这只需要 541 毫秒:

RES = n.zeros((SPMAT.shape[0],),dtype=complex64)
RES.real = SPMAT.dot(G.real); RES.imag = SPMAT.dot(G.imag)

结果是一样的。我想也许 n.zeros 预分配可能不是必需的，但我不知道该怎么做。