Быстрый вектор / разреженная матрица / векторное умножение - PullRequest
Новая
       40

Быстрый вектор / разреженная матрица / векторное умножение

0 голосов
/ 03 ноября 2019

Я хочу выполнить «разреженный внешний продукт» из двух одномерных массивов x и y с учетом разреженной «матрицы шаблонов» T. Например, я хочу вычислить что-то вроде 

x= np.array([1,2,3,4])
y= np.array([5,6,7])
T=np.array([[1,0,0],[0,0,1],[1,1,0],[0,1,0]])
np.multiply(T,np.outer(x,y))

который производит 

array([[ 5,  0,  0],
   [ 0,  0, 14],
   [15, 18,  0],
   [ 0, 24,  0]])

Задача состоит в том, чтобы сделать это быстро. Основная вычислительная проблема с этим наивным кодом состоит в том, что он выполняет много ненужных умножений во внешнем продукте. Нужно только выполнять умножения, если шаблон ненулевой.

Я пытался использовать разреженные методы SciPy, например: 

T_lil=lil_matrix(T)
T_csr=T_lil.tocsr()
diags(x).dot(T_csr.dot(diags(y)))

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

Я также пробовал что-то вроде 

x_column=np.array([x]).T
(T_csr.multiply(x_column)).multiply(y)

, которое (после применения .toarray ()) дает тот же ответ, но это нелепо неуклюже и опять не может быть оптимальным.

Не думаю, что это поможет преобразовать x и y в разреженную кодировку, потому что они, как правило, НЕ разрежены в моем приложении.

Кто-нибудь может помочь? Для моего приложения T может иметь 10 ^ 4 строки и 10 ^ 5 столбцов. Я совсем не против копаться в кишечнике кодировки csr (или csc, coo или dok), но я ожидаю, что кто-то знает лучший ответ, чем я могу себе представить.

1 Ответ

1 голос
/ 03 ноября 2019

Вот кое-что простое, что вы можете сделать с матрицей COO-формата T. Используйте расширенное индексирование для умножения T.data на правильные элементы x и y: 

result = coo_matrix((T.data * x[T.row] * y[T.col], (T.row.copy(), T.col.copy())),
                    shape=T.shape)

Вызовы copy позволяют избежать нескольких случаев, когда изменение одного из T или resultможет повлиять на другого. Вы можете удалить их, если уверены, что не будете изменять свои матрицы.

Также имейте в виду, что у этого result могут быть явные нули, особенно если x или y имеют нули.

...