构造稀疏矩阵后，从稀疏转换为稠密再变为稀疏 [英] Converting from sparse to dense to sparse again decreases density after constructing sparse matrix

问题描述

我正在使用scipy生成稀疏的有限差分矩阵，首先从块矩阵构造它，然后编辑对角线以解决边界条件.所得的稀疏矩阵是BSR类型的.我发现，如果将矩阵转换为密集矩阵，然后使用scipy.sparse.BSR_matrix函数返回到稀疏矩阵，则剩下的矩阵将比以前稀疏.这是我用来生成矩阵的代码:

I am using scipy to generate a sparse finite difference matrix, constructing it initially from block matrices and then editing the diagonal to account for boundary conditions. The resulting sparse matrix is of the BSR type. I have found that if I convert the matrix to a dense matrix and then back to a sparse matrix using the scipy.sparse.BSR_matrix function, I am left with a sparser matrix than before. Here is the code I use to generate the matrix:

size = (4,4)

xDiff = np.zeros((size[0]+1,size[0]))
ix,jx = np.indices(xDiff.shape)
xDiff[ix==jx] = 1
xDiff[ix==jx+1] = -1

yDiff = np.zeros((size[1]+1,size[1]))
iy,jy = np.indices(yDiff.shape)
yDiff[iy==jy] = 1
yDiff[iy==jy+1] = -1

Ax = sp.sparse.dia_matrix(-np.matmul(np.transpose(xDiff),xDiff))
Ay = sp.sparse.dia_matrix(-np.matmul(np.transpose(yDiff),yDiff))

lap = sp.sparse.kron(sp.sparse.eye(size[1]),Ax) + sp.sparse.kron(Ay,sp.sparse.eye(size[0]))

#set up boundary conditions
BC_diag = np.array([2]+[1]*(size[0]-2)+[2]+([1]+[0]*(size[0]-2)+[1])*(size[1]-2)+[2]+[1]*(size[0]-2)+[2])

lap += sp.sparse.diags(BC_diag)

如果我检查此矩阵的稀疏性，则会看到以下内容:

If I check the sparsity of this matrix I see the following:

lap
<16x16 sparse matrix of type '<class 'numpy.float64'>'
with 160 stored elements (blocksize = 4x4) in Block Sparse Row format>

但是，如果将其转换为密集矩阵，然后又恢复为相同的稀疏格式，则会看到稀疏矩阵:

However, if I convert it to a dense matrix and then back to the same sparse format I see a much sparser matrix:

sp.sparse.bsr_matrix(lap.todense())
<16x16 sparse matrix of type '<class 'numpy.float64'>'
with 64 stored elements (blocksize = 1x1) in Block Sparse Row format>

我怀疑发生这种情况的原因是因为我使用sparse.kron函数构造了矩阵，但我的问题是是否有一种方法可以在不首先转换为密集模式的情况下到达较小的稀疏矩阵，例如，如果我结束想要模拟一个非常大的域.

I suspect that the reason this is happening is because I constructed the matrix using the sparse.kron function but my question is if there is a way to arrive at the smaller sparse matrix without converting to dense first, for example if I end up wanting to simulate a very large domain.

推荐答案

BSR将数据存储在密集块中:

BSR stores the data in dense blocks:

In [167]: lap.data.shape                                                        
Out[167]: (10, 4, 4)

在这种情况下，这些块有很多零.

In this case those blocks have quite a few zeros.

In [168]: lap1 = lap.tocsr() 
In [170]: lap1                                                                  
Out[170]: 
<16x16 sparse matrix of type '<class 'numpy.float64'>'
    with 160 stored elements in Compressed Sparse Row format>
In [171]: lap1.data                                                             
Out[171]: 
array([-2.,  1.,  0.,  0.,  1.,  0.,  0.,  0.,  1., -3.,  1.,  0.,  0.,
        1.,  0.,  0.,  0.,  1., -3.,  1.,  0.,  0.,  1.,  0.,  0.,  0.,
        1., -2.,  0.,  0.,  0.,  1.,  1.,  0.,  0.,  0., -3.,  1.,  0.,
        0.,  1.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  1., -4.,  1.,  0., 
        ...
        0.,  0.,  1., -2.])

就地清理:

In [172]: lap1.eliminate_zeros()                                                
In [173]: lap1                                                                  
Out[173]: 
<16x16 sparse matrix of type '<class 'numpy.float64'>'
    with 64 stored elements in Compressed Sparse Row format>

如果在使用kron时指定了csr格式:

If I specify the csr format when using kron:

In [181]: lap2 = sparse.kron(np.eye(size[1]),Ax,format='csr') + sparse.kron(Ay,n
     ...: p.eye(size[0]), format='csr')                                         
In [182]: lap2                                                                  
Out[182]: 
<16x16 sparse matrix of type '<class 'numpy.float64'>'
    with 64 stored elements in Compressed Sparse Row format>

这篇关于构造稀疏矩阵后，从稀疏转换为稠密再变为稀疏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！