3

ブロックの合計をとって新しい小さな行列を作成することで、これを凝縮する必要がある大きな scipy スパース対称行列があります。

たとえば、4x4 疎行列の場合、AI は B[i,j] = sum(A[i:i+2,j:j+2]) である 2x2 行列 B を作成します。

現在、ブロックごとに圧縮されたマトリックスを再作成するだけですが、これは遅いです。これを最適化する方法についてのアイデアはありますか?

更新:これは正常に動作するサンプル コードですが、10.000x10.000 に凝縮したい 50.000x50.000 のスパース マトリックスでは遅いです:

>>> A = (rand(4,4)<0.3)*rand(4,4)
>>> A = scipy.sparse.lil_matrix(A + A.T) # make the matrix symmetric

>>> B = scipy.sparse.lil_matrix((2,2))
>>> for i in range(B.shape[0]):
...     for j in range(B.shape[0]):
...         B[i,j] = A[i:i+2,j:j+2].sum()
4

3 に答える 3

1

まず第一に、lilあなたが合計しているマトリックスはおそらく本当に悪いです、私は試してみるCOOか、多分CSR/CSS（どちらが良いかわかりませんが、lilおそらくこれらの操作の多くで本質的に遅くなります。私はテストしていませんが、遅くなります）。（たとえば、dia完全に適合することがわかっている場合を除きます）

に基づいCOOて、いくつかのトリックを行うことを想像できました。と配列COOが正確な位置を与えるため:rowcol

matrix = A.tocoo()

new_row = matrix.row // 5
new_col = matrix.col // 5
bin = (matrix.shape[0] // 5) * new_col + new_row
# Now do a little dance because this is sparse,
# and most of the possible bin should not be in new_row/new_col
# also need to group the bins:
unique, bin = np.unique(bin, return_inverse=True)
sum = np.bincount(bin, weights=matrix.data)
new_col = unique // (matrix.shape[0] // 5)
new_row = unique - new_col * (matrix.shape[0] // 5)

result = scipy.sparse.coo_matrix((sum, (new_row, new_col)))

(どこかで行と列を混同していないことを保証しません。これは正方行列でのみ機能します...)

于 2012-12-20T10:49:02.640 に答える
1

サイズNの正方行列と分割サイズd (したがって、行列はサイズdのN/d * N/dサブ行列に分割されます) を考えると、それらのサブ行列のコレクションを構築するために数回使用できますか? 、それらのそれぞれを合計して、それらを元に戻しますか?numpy.split

これは、効率的な実装というより疑似コードとして扱われるべきですが、私の考えを表現しています:

    def chunk(matrix, size):
        row_wise = []
        for hchunk in np.split(matrix, size):
            row_wise.append(np.split(hchunk, size, 1))
        return row_wise

    def sum_chunks(chunks):
        sum_rows = []
        for row in chunks:
            sum_rows.append([np.sum(col) for col in row])
        return np.array(sum_rows)

またはよりコンパクトに

    def sum_in_place(matrix, size):
        return np.array([[np.sum(vchunk) for vchunk in np.split(hchunk, size, 1)]
                         for hchunk in np.split(matrix, size)])

これにより、次のようなものが得られます。

    In [16]: a
    Out[16]: 
    array([[ 0,  1,  2,  3],
           [ 4,  5,  6,  7],
           [ 8,  9, 10, 11],
           [12, 13, 14, 15]])

    In [17]: chunk.sum_in_place(a, 2)
    Out[17]: 
    array([[10, 18],
           [42, 50]])
于 2012-12-19T19:47:21.570 に答える
0

4x4の例では、次のことができます。

In [43]: a = np.arange(16.).reshape((4, 4))
In [44]: a 
Out[44]: 
array([[  0.,   1.,   2.,   3.],
       [  4.,   5.,   6.,   7.],
       [  8.,   9.,  10.,  11.],
       [ 12.,  13.,  14.,  15.]])
In [45]: u = np.array([a[:2, :2], a[:2, 2:], a[2:,:2], a[2:, 2:]])
In [46]: u
Out[46]: 
array([[[  0.,   1.],
        [  4.,   5.]],

       [[  2.,   3.],
        [  6.,   7.]],

       [[  8.,   9.],
        [ 12.,  13.]],

       [[ 10.,  11.],
        [ 14.,  15.]]])

In [47]: u.sum(1).sum(1).reshape(2, 2)
Out[47]: 
array([[ 10.,  18.],
       [ 42.,  50.]])

itertoolsのようなものを使用すると、の式を自動化および一般化できるはずですu。

于 2012-12-19T13:19:48.830 に答える