計算矩陣乘法的子集

Question

當我有兩個非稀疏矩陣A和B時，有什麼方法可以有效地計算C=A.T.dot(B)當我只想要C的元素的子集？我有指定here CSC格式存儲所需的指數C。

Answer 1

忽略CSC業務，也許回答一個比你問的更簡單的問題。給出C索引值的元組列表，我將如何計算C的元素子集。

既然你正在評估C = ATdot（B）你是B.所以列乘以列，

for i, j in indexList: 
    C[i, j] = np.dot(A[:,i], B[:,j]) 

我猜，是不是你在找什麼，但我發現簡單的答案有時有助於澄清問題。

Answer 2

如果您事先知道您需要哪些C部分以及這些部分中的某些部分是連續的和矩形區域*，那麼您可以使用與分區矩陣乘法（1）或塊矩陣乘法相關的矩陣代數規則2）來加速其中一些計算。因此，例如，您可以使用@GaryBishop的相同基本邏輯，但不是具有「i」和「j」元素的列表，而是具有i_start，i_end和j_start的四元組的列表（或數組），j_end定義C的子矩陣，那麼你可以使用這些指數（儘管在這些鏈接中建立的規則）來找出需要爲所需的C塊求解的A和B的子矩陣。

對於簡單的例子，假設你只想要C的中間塊，所以我們將C分割成C1，C2和C3，我們關心的只有C2。如果A^{T}同樣被劃分成三組A1，A2，A3，那麼C2 = A2 * B。這個想法推廣到任何形狀的矩形，它只需要計算A和B的不同分區。這個想法是一樣的。

• - 這很平凡，但如果區域大於單個元素，則只會節省時間。

Answer 3

相反在使用Python（GaryBishop的答案）座標迭代的，你可以有numpy的做循環，從而構成實質性加速（以下計時）：

def sparse_mult(a, b, coords) : 
    rows, cols = zip(*coords) 
    rows, r_idx = np.unique(rows, return_inverse=True) 
    cols, c_idx = np.unique(cols, return_inverse=True) 
    C = np.dot(a[rows, :], b[:, cols]) 
    return C[r_idx, c_idx] 

>>> A = np.arange(12).reshape(3, 4) 
>>> B = np.arange(15).reshape(3, 5) 
>>> np.dot(A.T, B) 
array([[100, 112, 124, 136, 148], 
     [115, 130, 145, 160, 175], 
     [130, 148, 166, 184, 202], 
     [145, 166, 187, 208, 229]]) 
>>> sparse_mult(A.T, B, [(0, 0), (1, 2), (2, 4), (3, 3)]) 
array([100, 145, 202, 208]) 

sparse_mult返回扁平您提供的座標值的數組作爲元組列表。我不是很熟悉，稀疏矩陣格式，所以我不知道如何從上面的數據定義CSC，但以下工作：

>>> coords = [(0, 0), (1, 2), (2, 4), (3, 3)] 
>>> sparse.coo_matrix((sparse_mult(A.T, B, coords), zip(*coords))).tocsc() 
<4x5 sparse matrix of type '<type 'numpy.int32'>' 
    with 4 stored elements in Compressed Sparse Column format> 

這是各種替代方案的時機：

>>> import timeit 
>>> a = np.random.rand(2000, 3000) 
>>> b = np.random.rand(3000, 5000) 
>>> timeit.timeit('np.dot(a,b)[[0, 0, 1999, 1999], [0, 4999, 0, 4999]]', 'from __main__ import np, a, b', number=1) 
5.848562187263569 
>>> timeit.timeit('sparse_mult(a, b, [(0, 0), (0, 4999), (1999, 0), (1999, 4999)])', 'from __main__ import np, a, b, sparse_mult', number=1) 
0.0018596387374678613 
>>> np.dot(a,b)[[0, 0, 1999, 1999], [0, 4999, 0, 4999]] 
array([ 758.76351111, 750.32613815, 751.4614542 , 758.8989648 ]) 
>>> sparse_mult(a, b, [(0, 0), (0, 4999), (1999, 0), (1999, 4999)]) 
array([ 758.76351111, 750.32613815, 751.4614542 , 758.8989648 ])