Построение разреженной матрицы CSR напрямую по сравнению с использованием COO tocsr () - Scipy - PullRequest
Новая
       14

Построение разреженной матрицы CSR напрямую по сравнению с использованием COO tocsr () - Scipy

0 голосов
/ 17 января 2019

Моя цель здесь - очень быстро построить матрицу разреженных CSR. В настоящее время это является главным узким местом в моем процессе, и я уже оптимизировал его, построив матрицу coo относительно быстро, а затем используя tocsr ().

Однако я бы предположил, что построение матрицы CSR напрямую должно быть быстрее?

У меня есть очень специфический формат разреженной матрицы, который также является большим (то есть при заказах 100000x50000). Я смотрел в Интернете на эти другие ответы, но большинство не отвечает на вопрос, который у меня есть.

  • Эффективно построить матрицу FEM / FVM Рассматривается построение очень специфичной отформатированной разреженной матрицы по сравнению с использованием coo, что привело к улучшению скорости слияния с помощью слияния со скоростью tocsr ().

Структура разреженной матрицы:

Разреженная матрица H состоит из W списков размера N или построена из исходного массива размера NxW, назовем его A. По диагонали повторяющиеся списки размера N для N раз. Таким образом, для первых N строк H повторяется A [:, 0], но скользит вдоль N шагов для каждой строки.

Сравнение с COO.tocsr ()

Когда я масштабирую N и W и сначала строю матрицу COO, а затем запускаю tocsr (), это на самом деле быстрее, чем просто создавать матрицу CSR напрямую. Я не уверен, почему это так? Мне интересно, могу ли я каким-то образом воспользоваться структурой моей разреженной матрицы H? Поскольку там много повторяющихся элементов.

Пример кода

Вот пример кода для визуализации того, что происходит для небольшого размера выборки: 

from scipy.sparse import linalg, dok_matrix, coo_matrix, csr_matrix
import numpy as np
import matplotlib.pyplot as plt

def test_csr(testdata):
    indices = [x for _ in range(W-1) for x in range(N**2)]
    ptrs = [N*(i) for i in range(N*(W-1))]
    ptrs.append(len(indices))

    data = []
    # loop along the first axis
    for i in range(W-1):
        vec = testdata[:,i].squeeze()

        # repeat vector N times
        for i in range(N):
            data.extend(vec)

    Hshape = ((N*(W-1), N**2))
    H = csr_matrix((data, indices, ptrs), shape=Hshape)
    return H

N = 4
W = 8

testdata = np.random.randn(N,W)
print(testdata.shape)
H = test_csr(testdata)
plt.imshow(H.toarray(), cmap='jet')
plt.show()

Figure that shows the repeating structure of the sparse matrix

1 Ответ

0 голосов
/ 17 января 2019

Похоже, ваш вывод содержит только первые W-1 строки тестовых данных. Я не уверен, является ли это намеренным или нет. Мои решения предполагают, что вы хотите использовать все testdata.

Когда вы строите матрицу COO, вы также строите индексы и данные аналогичным образом?

Одна вещь, которая может ускорить создание csr_matrix, - это использовать встроенные функции numpy для генерации данных для csr_matrix, а не в циклах и массивах python. Я ожидаю, что это значительно улучшит скорость генерации индексов. Вы можете настроить тип d для типа int в зависимости от размера вашей матрицы. 

N = 4
W = 8
testdata = np.random.randn(N,W)

ptrs = N*np.arange(W*N+1,dtype='int')
indices =  np.tile(np.arange(N*N,dtype='int'),W)
data = np.tile(testdata,N).flatten()

Hshape = ((N*W, N**2))
H = csr_matrix((data, indices, ptrs), shape=Hshape)

Другая возможность состоит в том, чтобы сначала создать большой массив, а затем определить каждый из N вертикальных блоков столбцов сразу. Это означает, что вам не нужно делать тонну копий исходных данных, прежде чем поместить их в разреженную матрицу. Однако преобразование типа матрицы может быть медленным. 

N = 4
W = 8
testdata = np.random.randn(N,W)

Hshape = ((N*W, N**2))
H = sp.sparse.lol_matrix(Hshape)

for j in range(N): 
    H[N*np.arange(W)+j,N*j:N*(j+1)] = testdata.T

H = H.tocsc()
...