Умножение матриц для разреженных матриц в Python

Question

Я хочу умножить разреженную матрицу A на матрицу B, которая имеет 0, -1 или 1 в качестве элементов.Чтобы уменьшить сложность умножения матриц, я могу игнорировать элементы, если они равны 0, или добавить столбец без умножения, если элемент равен 1, или подпрограммам.если это -1.Обсуждение об этом здесь:

Псевдокод алгоритма случайной проекции

Теперь я могу пойти дальше и реализовать этот трюк, но мне интересно, если я использую функции умножения Numpy, это 'будет быстрее.

Кто-нибудь знает, оптимизировали ли они умножение матриц для таких матриц?Или вы можете предложить что-нибудь, чтобы ускорить этот процесс, так как у меня есть матрица 300000x1000.

Answer 1

Вы смотрели на scipy.sparse? Здесь нет смысла заново изобретать колесо. Разреженные матрицы - довольно стандартная вещь.

(В этом примере я использую матрицу 300000x4 для упрощения печати после умножения. Матрица 300000x1000 не должна представлять собой никаких проблем. Однако это будет намного быстрее, чем умножение двух плотных массивов, если у вас есть большинство 0 элементов.)

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()

Это дает:

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