如何在 SciPy 中加速稀疏矩阵和密集 ndarray 向量之间的乘法

Question

我正在尝试加速算法。该算法的瓶颈在于计算“Ax”，其中，A 是具有 n X m 维度的大 稀疏矩阵，x 是具有 m 维度的稠密向量。 我的算法试图从 m d m 的列中选择 A 的特定 << d 列，我们还在 x 中选择相应的 d 元素。我们称它们为 sub_A 和 sub_x，我们只需要计算 sub_A 和 sub_x 之间的乘法。

但是，我发现，scipy中的这种乘法显示出不明显的加速效果。即使我做d< m/100，加速也只能达到2倍，这很奇怪。由于A的二次元缩小了这么多。我在matlab中尝试了类似的代码，并得到了更明显的加速。如果我做 d，我可以将计算速度提高近 50-100 倍。

我在网上查了一下，发现scipy代码中有一些奇怪的瓶颈，导致稀疏矩阵与密集[tag:NumPy]向量的乘法非常慢。 人们建议使用 pysparse 或 cysparse 但是这些模块几年前就停止更新了。

python有没有其他方法可以解决这个问题？否则我必须将我的整个项目移动到matlab.

我已经在 python 和 matlab 中尝试了计算，具有 99% 稀疏矩阵 A 和密集 x.

import scipy.sparse as sp
import numpy as np
import time
m = 10000
n = 100
d = 100
times = 100
x = np.ones((m,1))

A = sp.random(n, m, density=0.01, format='csr')

start_time = time.time()
for i in range(times):
    c = A.dot(x)
end_time = time.time()

print("Ax cost:", end_time - start_time)

row_indices = np.random.choice(m, d, replace=False)
sub_x = x[row_indices]

sub_A = A[:,row_indices]

start_time = time.time()
for i in range(times):
    c = sub_A.dot(sub_x)
end_time = time.time()

print("sub_A x cost:", end_time - start_time)

输出为

Ax cost: 0.002000093460083008
sub_A dot sub_x cost: 0.0010018348693847656

即使是d = m/100，计算速度也没有太大的差别

Answer 1

如果你反对解释器开销，这似乎是共识，那么你无能为力。

我通过使用

@

运算符而不是

.dot

方法发现了一些改进，因为运算符具有更快的代码路径。除此之外，您可能想尝试一下Numba，但我现在无法测试它。

其他口译员也可能值得一试。 Python-3.11 带来了一些改进.

除此之外，一般来说，减少开销的最佳方法是用更少的调用做更多的事情。尝试将多个矩阵-向量积聚合为一个矩阵-矩阵积。