Python中稀疏矩阵的矩阵乘法 [英] Matrix multiplication for sparse matrices in Python

问题描述

我想将一个稀疏矩阵A与一个以0，-1或1为元素的矩阵B相乘.为了降低矩阵乘法的复杂性，如果项为0，则可以忽略这些项；或者，如果项为1或子项，则可以继续添加不相乘的列.如果是-1.有关此的讨论在这里:

I want to multiply a sparse matrix A, with a matrix B which has 0, -1, or 1 as elements. To reduce the complexity of the matrix multiplication, I can ignore items if they are 0, or go ahead and add the column without multiplication if the item is 1, or subs. if it's -1. The discussion about this is here:

随机投影算法伪代码

现在我可以继续实施此技巧了，但是我想知道是否使用Numpy的乘法功能会更快.

Now I can go ahead and implement this trick but I wonder if I use Numpy's multiplication functions it'll be faster.

有人知道他们是否针对此类矩阵优化了矩阵乘法吗?或者，由于我有一个300000x1000的矩阵，您是否可以提出一些建议来加快此过程.

Does anyone knows if they optimised matrix multiplication for such matrices? Or can you suggest something to speed this process up since I have a matrix 300000x1000.

推荐答案

您是否看过scipy.sparse?这里没有重新发明轮子的意义.稀疏矩阵是相当标准的事情.

Have you looked at scipy.sparse? There's no point in re-inventing the wheel, here. Sparse matricies are a fairly standard thing.

(在示例中，我使用300000x4矩阵进行乘法运算后更容易打印.但是，300000x1000矩阵应该没问题.这比将两个密集数组相乘要快得多.您拥有大多数0元素.)

(In the example, I'm using a 300000x4 matrix for easier printing after the multiplication. A 300000x1000 matrix shouldn't be any problem, though. This will be much faster than multiplying two dense arrays, assuming you have a majority of 0 elements.)

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.]]

这篇关于Python中稀疏矩阵的矩阵乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！