Как сделать эффективное умножение матриц между плотной матовой матрицей и разреженным вектором? - PullRequest
Новая
       22

Как сделать эффективное умножение матриц между плотной матовой матрицей и разреженным вектором?

0 голосов
/ 12 сентября 2018

Умножение плотной матрицы с разреженными векторами скиппи с помощью @ невероятно неэффективно. Кажется, что он совсем не использует разреженность вектора.

Скажем, у нас есть 

A = np.eye(5000)
x = np.eye(5000)[333]
x = scipy.sparse.coo_matrix(x).T # make it a sparse vector

Затем умножение с использованием @ дает: 

%timeit A @ x
8 ms ± 78.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Давайте сами напишем невероятно редкое умножение: 

def mult_dense_with_sparse(A, x):
  return (A[:,x.nonzero()[0]] @ x.toarray()[x.nonzero()[0]]).T[0]

О чудо: 

%timeit mult_dense_with_sparse(A, x)
50.3 µs ± 45.3 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Это намного быстрее! Несмотря на то, что эта реализация сначала создает плотный вектор, снова добавляя все нули, а затем снова удаляя все нули ... Поэтому мне интересно, если не @, как я могу умножить плотную матрицу с кусочками на разреженный scipy? вектор эффективно? Конечно, такая основная операция является частью scipy?

Редактировать: предоставленное решение в другом вопросе не помогает, поскольку оно столь же неэффективно, как @: 

%timeit scipy.sparse.csr_matrix.dot(A, x)
7.97 ms ± 113 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Редактировать 2 в ответе Хамир Аббаси: 

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
   101                                                       @profile
   102                                                       def ratio(self, n):
   103        80         51.0      0.6      0.0                  s = n + 1
   104        80   11401854.0 142523.2     16.1                  self.sfpc = self.scolPCA(s) # sparse first principal component
   106        80     351898.0   4398.7      0.5                  wSums = (self.signals[:,self.sfpc.nonzero()[0]] @ self.sfpc.toarray()[self.sfpc.nonzero()[0]]).T[0]
   108        80   56487433.0 706092.9     79.7                  wSums = self.sfpc.T.dot(self.signals.T)[0]
   110        80    2521189.0  31514.9      3.6                  self.Flag, self.threshold, self.incline, self.deltaVar = self.actFunctOpt(list(wSums))
   111        80        160.0      2.0      0.0                  return  self.deltaVar / (2 + s)

Здесь вы можете видеть, что наш «взлом» занимает около 0,5% времени этой функции, в то время как использование dot занимает 79,7% времени этой функции.

1 Ответ

0 голосов
/ 12 сентября 2018

В вашем примере A имеет тип np.ndarray, а x имеет тип scipy.sparse.coo_matrix.

Если вы ищете самый простой ответ, который можно ускорить, вот он: 

import numpy as np
import scipy.sparse as sps
A = np.random.rand(5000, 5000)
v = np.zeros((5000, 1))
v[333] = 1
v_s = sps.csc_matrix(v)
%timeit v_s.T.dot(A).T # 46.6 µs ± 1.11 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit A @ v # 6.75 ms ± 29.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Однако, если вы хотите разобраться в механике этого ответа: В настоящее время оператор @ не поддерживает перегрузку для массива NumPy из-за ошибки . Кроме того, scipy.sparse.coo_matrix даже не пытается переопределить @, и умножение матриц быстрее для scipy.sparse.csr_matrix (coo_matrix сначала будет преобразован в csr_matrix для умножения в любом случае).

Итак, NumPy преобразует ваш разреженный вектор в массив NumPy, а затем выполняет плотное умножение.

Однако csr_matrix.dot существует и поддерживает умножение с плотными массивами NumPy. Поэтому мы используем свойство A @ B = (B.T @ A.T).T, а также тот факт, что csc_matrix.T создает csr_matrix для создания вышеуказанного оптимизированного кода.

...