已知结构矩阵的NumPy矩阵乘法效率

Question

我有两个NxN矩阵，我想把它们相乘：A和B。在NumPy中，我使用了：

import numpy as np
C = np.dot(A, B)

然而，我碰巧知道，对于矩阵B，只有第n行和第n列是非零的（这直接来自生成矩阵的分析公式，毫无疑问总是如此）。在

为了利用这一事实并减少生成C所需的乘法数，我将上面的内容替换为：

^{pr2}$

从分析上讲，这应该降低总的复杂度如下：在一般情况下（不使用任何花招，只是基本的矩阵乘法）C=AB，其中A和B都是NxN，应该是O（N^3）。也就是说，所有N行必须乘以所有N列，并且这些点积中的每一个都包含N个乘法=>；O（NNN）=O（N^3）。\

利用B的结构，正如我上面所做的，但是应该是O（N^2+N^2）=O（2N^2）=O（N^2）。也就是说，所有N行必须乘以所有N列，但是，对于所有这些行（除了那些涉及“B[：，N]”的列），只需要一个标量乘法：对于m，“B[：，m]”只有一个元素是非零的！=n。当n==m时，将发生n次（A的每一行必须乘以B的第n列），则必须进行n次标量乘法

但是，第一个代码块（使用美国运输部（A，B）要快得多。我知道（通过诸如：Why is matrix multiplication faster with numpy than with ctypes in Python?）的低层实现细节美国运输部很可能要为此负责。所以我的问题是：如何利用矩阵B的结构来提高乘法效率，而不牺牲NumPy的实现效率，而不用在c中构建自己的低级矩阵乘法？在

这种方法是对多个变量进行数值优化的一部分，因此，O（N^3）很难处理，而O（N^2）可能会完成这项工作。在

谢谢你的帮助。另外，我是新手，所以请原谅任何新手的错误。在

Answer 1

我计时了，使用sparse更快：

import numpy as np
from scipy import sparse

from timeit import timeit

A = np.random.rand(100,100)
B = np.zeros(A.shape, dtype=np.float)

B[3] = np.random.rand(100)
B[:,3] = np.random.rand(100)

sparse_B = sparse.csr_matrix(B)

n = 1000

t1 = timeit('np.dot(A, B)', 'from __main__ import np, A, B', number=n)
print 'dense way : {}'.format(t1)
t2 = timeit('A * sparse_B', 'from __main__ import A, sparse_B',number=n)
print 'sparse way : {}'.format(t2)

结果：

^{pr2}$

随着B行数的增加，使用稀疏矩阵乘法的时间优势也会增加。在

Answer 2

如果我正确地理解了A和B，那么我就不理解for循环，以及为什么不只是乘以两个非零向量：

# say A & B are like this:
n, N = 3, 5
A = np.array( np.random.randn(N, N ) )

B = np.zeros_like( A )
B[ n ] = np.random.randn( N )
B[:, n] = np.random.randn( N )

取B的非零行和列：

^{pr2}$

将A乘以这两个向量：

X = np.outer( A[:,n], rowb )
X[:,n] += np.dot( A, colb )

要验证检查：

X - np.dot( A, B )

使用N=100：

%timeit np.dot(A, B)
1000 loops, best of 3: 1.39 ms per loop

%timeit colb = np.copy( B[:,n] ); colb[ n ] = 0; X = np.outer( A[:,n], B[n,:] ); X[:,n] += np.dot( A, colb )
10000 loops, best of 3: 98.5 µs per loop