python - 如何忽略矩阵乘法中的零？

Question

假设我有一个带有随机数的 10000 x 10000 矩阵 W，以及两个 10000 dim 向量 U 和 V，U 中有随机数，V 中填充了零。使用 numpy 或 pytorch，计算 U@W 和 V@W 需要相同的时间。我的问题是，有没有一种方法可以优化矩阵乘法，使其在计算过程中跳过或忽略零，从而更快地计算 V @ W 之类的东西？

import numpy as np
W = np.random.rand(10000, 10000)

U = np.random.rand(10000)
V = np.zeros(10000)

y1 = U @ W
y2 = V @ W
# computing y2 should take less amount of time than y1 since it always returns zero vector.

Answer 1

您可以使用 scipy.sparse类来提高你的表现，但这完全取决于矩阵。例如，将 V 用作稀疏矩阵所获得的性能会非常好。通过将 U 转换为稀疏矩阵获得的结果不会很好，或者实际上可能会降低性能(在 U 实际上是密集的情况下)。

import numpy as np
import scipy.sparse as sps

W = np.random.rand(10000, 10000)
U = np.random.rand(10000)
V = np.zeros(10000)

%timeit U @ W
125 ms ± 1.45 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit V @ W
128 ms ± 6.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Vsp = sps.csr_matrix(V)
Usp = sps.csr_matrix(U)
Wsp = sps.csr_matrix(W)

%timeit Vsp.dot(Wsp)
1.34 ms ± 15.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 
%timeit Vsp @ Wsp
1.39 ms ± 37.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit Usp @ Wsp
2.37 s ± 84.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

如您所见，对 V @W 使用稀疏方法有了很大的改进，但实际上您降低了 U @W 的性能，因为没有条目U 或 W 中的值为零。