4

2 つの非疎行列Aとがある場合、 の要素のサブセットのみが必要な場合にB効率的に計算する方法はありますか? ここで指定されている CSC 形式で格納されている必要なインデックスがあります。C=A.T.dot(B)CC

4

3 に答える 3

2

Cのどの部分が必要で、これらの部分の一部が連続した長方形の領域*であるかを事前に知っている場合は、区分行列の乗算（1）またはブロック行列の乗算（2）に関連する行列代数規則を使用して速度を上げることができます。これらの計算のいくつかをアップします。したがって、たとえば、@ GaryBishopと同じ基本ロジックを使用できますが、「i」要素と「j」要素のリストを使用する代わりに、i_start、i_endおよびj_start、j_endの4つのタプルのリスト（または配列）を使用できます。 Cの部分行列を定義する場合は、これらのインデックスを使用して（ただし、これらのリンクでルールが確立されています）、Cの目的のブロックを解く必要があるAとBの部分行列を把握できます。

簡単な例として、Cの中央のブロックのみが必要であるとすると、Cを行ごとにC1、C2、およびC3に分割し、気にするのはC2だけです。A ^ {T}が同様に行A1、A2、A3の3つのセットに分割されている場合、C2 = A2 * Bです。アイデアは任意の形状の長方形に一般化され、計算にはAとBの異なる分割が必要です。考え方は同じです。

  • -これは自明なことですが、リージョンが単一の要素よりも大きい場合にのみ時間の節約になります。
于 2012-12-21T12:54:36.037 に答える
2

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 ])
于 2013-01-07T23:23:15.600 に答える
1

CSC ビジネスを無視し、おそらくあなたが求めているよりも簡単な質問に答えています。C インデックス値のタプルのリストを指定して、C の要素のサブセットを計算する方法を次に示します。

C=ATdot(B) を評価しているので、A の列に B の列を掛けています。

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

それはあなたが探しているものではないと思いますが、簡単な答えが質問を明確にするのに役立つ場合があります。

于 2012-12-07T16:50:32.437 に答える