Mejora del rendimiento de la multiplicación de matrices dispersas de Scipy

Dado un Scipy CSC Matriz dispersa “sm” con dimensiones (170k x 170k) con 440 millones de puntos no nulos y un vector CSC “v” (170k x 1) con algunos puntos no nulos, hay algo que puede ser Realizado para mejorar el rendimiento de la operación:

resul = sm.dot(v) 

?

Actualmente está tomando aproximadamente 1 segundo. La inicialización de las matrices como CSR aumentó el tiempo hasta 3 segundos, por lo que CSC obtuvo mejores resultados.

SM es una matriz de similitudes entre productos y V es el vector que representa los productos que el usuario compró o hizo clic. Así que para cada usuario sm es lo mismo.

Estoy usando Ubuntu 13.04, Intel i3 @ 3.4GHz, 4 Cores.

Investigando en SO así que leí sobre el paquete de Ablas. Escribí en el terminal:

 ~$ ldd /usr/lib/python2.7/dist-packages/numpy/core/_dotblas.so 

Lo que resultó en:

  linux-vdso.so.1 => (0x00007fff56a88000) libblas.so.3 => /usr/lib/libblas.so.3 (0x00007f888137f000) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f8880fb7000) libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f8880cb1000) /lib64/ld-linux-x86-64.so.2 (0x00007f888183c000) 

Y por lo que entendí, esto significa que ya estoy usando un paquete de alto rendimiento de Ablas. Aún no estoy seguro de si este paquete ya implementa computación en paralelo pero parece que no lo hace.

¿Podría el procesamiento multi-core ayudar a mejorar el rendimiento? Si es así, ¿hay alguna biblioteca que pueda ser útil en python?

También estaba considerando la idea de implementar esto en Cython, pero no sé si esto llevaría a buenos resultados.

Gracias por adelantado.

Las rutinas de multiplicación de matrices dispersas están codificadas directamente en C ++ y, por lo que revela una fuente rápida, no parece haber ningún gancho en ninguna biblioteca optimizada. Además, no parece estar aprovechando el hecho de que la segunda matriz es un vector para minimizar los cálculos. Por lo tanto, probablemente pueda acelerar un poco las cosas accediendo a las entrañas de la matriz dispersa y personalizando el algoritmo de multiplicación. El siguiente código lo hace en Python / Numpy puro, y si el vector realmente tiene “algunos puntos no nulos” coincide con la velocidad del código C ++ de scipy: si lo implementó en Cython, el aumento de velocidad debería ser notable:

 def sparse_col_vec_dot(csc_mat, csc_vec): # row numbers of vector non-zero entries v_rows = csc_vec.indices v_data = csc_vec.data # matrix description arrays m_dat = csc_mat.data m_ind = csc_mat.indices m_ptr = csc_mat.indptr # output arrays sizes = m_ptr.take(v_rows+1) - m_ptr.take(v_rows) sizes = np.concatenate(([0], np.cumsum(sizes))) data = np.empty((sizes[-1],), dtype=csc_mat.dtype) indices = np.empty((sizes[-1],), dtype=np.intp) indptr = np.zeros((2,), dtype=np.intp) for j in range(len(sizes)-1): slice_ = slice(*m_ptr[[v_rows[j] ,v_rows[j]+1]]) np.multiply(m_dat[slice_], v_data[j], out=data[sizes[j]:sizes[j+1]]) indices[sizes[j]:sizes[j+1]] = m_ind[slice_] indptr[-1] = len(data) ret = sps.csc_matrix((data, indices, indptr), shape=csc_vec.shape) ret.sum_duplicates() return ret 

Una explicación rápida de lo que está sucediendo: una matriz CSC se define en tres matrices lineales:

  • data contienen las entradas distintas de cero, almacenadas en el orden mayor de la columna.
  • indices contienen las filas de las entradas que no son cero.
  • indptr tiene una entrada más que el número de columnas de la matriz, y los elementos en la columna j se encuentran en los data[indptr[j]:indptr[j+1]] y están en los indices[indptr[j]:indptr[j+1]] filas indices[indptr[j]:indptr[j+1]] .

Entonces, para multiplicar por un vector de columna disperso, puede iterar sobre data e indices del vector de columna, y para cada par (d, r) , extraiga la columna correspondiente de la matriz y multiplíquelo por d , es decir, data[indptr[r]:indptr[r+1]] * d e indices[indptr[r]:indptr[r+1]] .

Recientemente tuve el mismo problema. Lo resolví así.

 def sparse_col_vec_dot(csc_mat, csc_vec): curr_mat = csc_mat.tocsr() ret curr_mat* csc_vec 

El truco aquí es que tenemos que hacer una versión de la matriz como representación de fila y la otra versión como representación de columna.