array - La multiplicación de matriz para matrices dispersas en Python

numpy.ndarray to array

Question

Quiero multiplicar una matriz dispersa A, con una matriz B que tiene 0, -1 o 1 como elementos. Para reducir la complejidad de la multiplicación de la matriz, puedo ignorar los ítems si son 0, o continuar y agregar la columna sin multiplicación si el ítem es 1 o subs. si es -1. La discusión sobre esto está aquí:

Algoritmo de proyección aleatorio pseudo código

Ahora puedo continuar e implementar este truco, pero me pregunto si usaré las funciones de multiplicación de Numpy, será más rápido.

¿Alguien sabe si optimizaron la multiplicación de matrices para tales matrices? O puede sugerir algo para acelerar este proceso ya que tengo una matriz de 300000x1000.

Answer 1

¿Has mirado a scipy.sparse ? No tiene sentido reinventar la rueda, aquí. Las matrículas dispersas son algo bastante estándar.

(En el ejemplo, estoy usando una matriz de 300000x4 para imprimir más fácilmente después de la multiplicación. Sin 300000x1000 matriz de 300000x1000 no debería ser ningún problema. Esto será mucho más rápido que multiplicar dos matrices densas, suponiendo que tienes una mayoría de 0 elementos .)

import scipy.sparse
import numpy as np

# Make the result reproducible...
np.random.seed(1977)

def generate_random_sparse_array(nrows, ncols, numdense):
    """Generate a random sparse array with -1 or 1 in the non-zero portions"""
    i = np.random.randint(0, nrows-1, numdense)
    j = np.random.randint(0, ncols-1, numdense)
    data = np.random.random(numdense)
    data[data <= 0.5] = -1
    data[data > 0.5] = 1
    ij = np.vstack((i,j))
    return scipy.sparse.coo_matrix((data, ij), shape=(nrows, ncols))

A = generate_random_sparse_array(4, 300000, 1000)
B = generate_random_sparse_array(300000, 5, 1000)

C = A * B

print C.todense()

Esto produce:

[[ 0.  1.  0.  0.  0.]
 [ 0.  2. -1.  0.  0.]
 [ 1. -1.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.]]