矩阵-矩阵乘法的高效 Hadamard 乘积

Question

我正在尝试在Python中计算以下操作：(AB).C，其中A、B、C是稀疏矩阵，并且带有下面的点“。” 我指出了矩阵的 Hadamard（逐项）乘积，AB 是 A 和 B 之间的矩阵-矩阵乘法。我需要使用不同的矩阵多次执行此操作。

我知道一切都可以做，例如

import scipy.sparse as sp
# Example dimensions for non-square matrices
m, n, p = 1000, 800, 600
# Creating sparse matrices A, B, and D with different dimensions
A = sp.random(m, n, density=0.01, format='csr')  # Sparse matrix A
B = sp.random(n, p, density=0.01, format='csr')  # Sparse matrix B
C = sp.random(m, p, density=0.01, format='csr')  # Sparse matrix C for entrywise product
result = (A@B).multiply(C)

但这最终会计算矩阵-矩阵乘法中的元素，这些元素稍后将乘以零，因此我相信必须有一种更有效的方法来做到这一点。

我尝试存储 C 的稀疏结构并仅计算非零入口的矩阵-矩阵乘积 (AB)（基本上使用嵌套循环），但结果比仅计算所有内容慢得多。

Answer 1

在效率上击败 scipy 和 numpy 是非常困难的。许多矩阵运算都是用 C 实现的，我们用 Python 编写的任何循环都会比 C 语言的等效项慢。但是，根据您的稀疏性和数据大小，有可能获得一点改进。我从这个答案中获得了一些灵感。我们的方法是：

对
1. .find()

    使用 

   C

    操作来了解最终需要的索引。

将所有不使用的索引设置为零。
删除所有零（这会重新索引矩阵）。
对新矩阵执行两个乘法。

sdf

import scipy.sparse as sp
# Example dimensions for non-square matrices
m, n, p = 1000, 800, 600
# Creating sparse matrices A, B, and D with different dimensions
A = sp.random(m, n, density=0.01, format='csr')  # Sparse matrix A
B = sp.random(n, p, density=0.01, format="csr")  # Sparse matrix B
C = sp.random(m, p, density=0.01, format='csr')  # Sparse matrix C for entrywise product

# 1. Find the non-zero indices
# The zipped pairs (a, b) contain each non-zero index of C
a, b, c = sp.find(C)

# 2. Set the non-used indices of A and B to zero
A[list(set(A.indices) - set(a))] = 0
B[list(set(B.indices) - set(b))] = 0

# 3. Eliminate the rows which are all zeros
A.eliminate_zeros()
B.eliminate_zeros()

# The final computation is the same
result = (A@B).multiply(C)

在我的测试中，很难找到在删除行后运行速度明显更快的组合。您的速度提升很大程度上取决于几个因素：

如果您需要对多个矩阵
• A,B

   与相同的 

  C

   进行乘法，您只需

  查找 C

   上的索引一次。但是，如果您每次都必须重新计算不同的 

  C

   矩阵，我的方法可能会比您的简单方法慢，因为您每次都必须计算。

如果
• A

   和 

  B

   非常稀疏，那么丢弃它们不会带来太多好处。我发现 

  density

   和 

  A

   的 

  B

   越高且 

  C

   的密度越低，结果越好。这是有道理的，因为我们使用 

  C

   中的信息来跳过越来越多的点积乘法。

使用您的原始值时，我根本没有注意到太大的差异。我按如下方式调整了密度，以表明这种方法在正确的情况下确实可以提高速度。注意

A,B

 的密度比最初给出的更高，而 

C

 的密度更低。这

非常取决于您的数据，因此请尝试一下，看看是否有任何改进。

m, n, p = 1000, 800, 600
A = sp.random(m, n, density=0.1, format="csr")
B = sp.random(n, p, density=0.1, format="csr")
C = sp.random(m, p, density=0.002, format='csr')

# Naive result
(A@B).multiply(C)
82 ms ± 6.18 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# Result after dropping rows
(A@B).multiply(C)
47.1 ms ± 6.04 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

查看是否会获得一些改进的最简单方法是比较稀疏矩阵。请注意“存储的元素”计数。

# "A" before dropping rows
<1000x800 sparse matrix of type '<class 'numpy.float64'>'
    with 80000 stored elements in Compressed Sparse Row format>

# "A" after dropping rows
<1000x800 sparse matrix of type '<class 'numpy.float64'>'
    with 62922 stored elements in Compressed Sparse Row format>