计算大型稀疏矩阵的幂和

Question

给定一个大小为 50000x1 的查询向量（单热向量）q 和一个大小为 50000 x 50000 和 nnz 的大稀疏矩阵 A A 是 0.3 亿，我想计算 r=(A + A^2 + ... + A^S)q（通常是 4 <= S <=6）。

我可以使用循环迭代上面的等式

r = np.zeros((50000,1))
for i in range(S):
   q = A.dot(q)
   r += q

但我想要更快速的方法。

首先想到的是 A 可以对称，所以 eigen decomposition would help for compute power of A。但是由于 A 是大的稀疏矩阵，分解后会产生与 A 大小相同的密集矩阵，这会导致性能下降（在内存和速度方面）。

还考虑了低秩近似。但是 A 又大又稀疏，所以不确定哪个排名 r 是合适的。

预先计算一些东西是完全没问题的，比如 A + A^2 + ... + A^S = B。但我希望最后一次计算会很快：计算 Bq 少于 40 毫秒。

是否有任何参考资料或论文或技巧？

Answer 1

即使矩阵不稀疏，迭代方法也是可行的方法。

乘法 A.dot(q) 的复杂度为 O(N^2)，而计算 A.dot(A^i) 的复杂度为 O(N^3).

q 是稀疏的（确实比 A 稀疏得多）这一事实可能会有所帮助。对于第一次迭代 A*q 可以计算为 A[q_hot_index,:].T.

对于第二次迭代，A @ q 的预期密度与 A 的预期密度相同（大约 10%），因此稀疏地进行仍然很好。

对于之后的第三次迭代，A^i @ q 将是密集的。

由于您正在累积结果，因此您的 r 不稀疏是件好事，它可以防止索引操作。有several different ways to store sparse matrices. I myself can't say I understand in depth all of them, but I think csr_matrix, csc_matrix，是最紧凑的通用稀疏矩阵。

当你需要计算一个 P(A) 时，特征分解是好的，计算一个 P(A)*q 只有当 P(A) 具有大小的阶数时，特征分解才变得有利A。本征分解具有复杂性 O(N^3)，矩阵向量乘积具有复杂性 O(N^2)，使用本征分解可以实现 D 次多项式 P(A) 的计算 O(N^3 + N*D).

编辑： 回答评论中的问题

“它可以防止索引操纵”<- 你能详细说明一下吗？

假设您有一个稀疏矩阵 [0,0,0,2,0,7,0]。这可以描述为 ((3,2), (5,7))。现在假设您将 1 分配给一个元素，它变成 [0,0,0,2,1,7,0]，现在表示为 ((3,2), (4,1), (5,7))。赋值是通过插入数组来完成的，插入数组的复杂度O(nnz)，其中nnz是非零元素的个数。如果你有一个密集的矩阵，你总是可以修改一个复杂的元素 O(1).

复杂度中的 N 是多少？

它是矩阵的行数或列数A

关于本征分解，你想说值得吗可以在 O(N^3 +N*D) 而不是 O(N^3 + N^2)

计算 P(A) 将具有复杂性 O(N^3 * D)（具有不同的常数），对于大矩阵，使用特征分解计算 P(A) 可能是最有效的。但是 P(A)x 有 O(N^2 * D) 的复杂性，所以用特征分解计算 P(A)x 可能不是一个好主意，除非你有很大的 D (>N)，当速度是关注。

计算大型稀疏矩阵的幂和

Compute sum of power of large sparse matrix

python

matrix

scipy

linear-algebra

sparse-matrix