scipy 稀疏矩阵的对称化

Question

有没有一种简单有效的方法来使稀疏 scipy 矩阵（例如 lil_matrix 或 csr_matrix）对称？

在填充大型稀疏共生矩阵时，同时填充 [row, col] 和 [col, row] 会非常低效。我想做的是：

for i in data:
    for j in data:
        if cond(i, j):
            lil_sparse_matrix[i, j] = some_value
            # want to avoid this:
            # lil_sparse_matrix[j, i] = some_value
# this is what I'm looking for:
lil_sparse.make_symmetric() 

这类似于stackoverflow 的 numpy-smart-symmetric-matrix question，但特别适用于 scipy 稀疏矩阵。

Answer 1

好的，它使赋值语句的数量增加了一倍，但从总体上看，这有多少惩罚？

lil是索引分配的最有效格式，但我已经在其他帖子中探讨了替代方案。如果我没记错的话，直接分配给 a 的data和rows属性lil会更快，尽管这在一次填充整行时主要是有价值的。

Adok也相对较快，但我发现分配给常规字典，然后更新到dok更快。（Adok是字典子类）。

但是如果你走这coo条路线 - 建立data,rows和cols值的列表，同时创建i,j和j,i条款并不昂贵。如果您可以一次定义一堆值，而不是遍历所有i,j.

因此，有效地创建对称矩阵只是有效矩阵定义问题的一个子集。

我不知道稀疏包中的任何对称化函数。我想知道是否有任何线性代数函数具有对称规定。我怀疑最有效的处理程序只是假设矩阵是上三角形或下三角形，而没有明确的对称值。

您可以创建一个上三矩阵，然后将值复制到下三矩阵。在密集情况下，最简单的方法是对矩阵及其转置求和（并可能减去对角线）。但是稀疏矩阵求和有点效率，所以这可能不是最好的。但我没有做过任何测试。

============

转置的总和至少没有给我任何效率警告：

In [383]: M=sparse.lil_matrix((10,10),dtype=int)
In [384]: 
In [384]: for i in range(10):
     ...:     for j in range(i,10):
     ...:         v=np.random.randint(0,10)
     ...:         if v>5:
     ...:             M[i,j]=v
     ...:             
In [385]: M
Out[385]: 
<10x10 sparse matrix of type '<class 'numpy.int32'>'
    with 22 stored elements in LInked List format>
In [386]: M.A
Out[386]: 
array([[0, 7, 7, 0, 9, 0, 7, 0, 0, 9],
       [0, 0, 7, 8, 0, 8, 0, 0, 9, 0],
       [0, 0, 0, 7, 0, 0, 9, 0, 8, 0],
       [0, 0, 0, 0, 0, 0, 6, 0, 6, 6],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 8, 9, 0, 8],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 8, 8],
       [0, 0, 0, 0, 0, 0, 0, 0, 6, 8],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

转置总和（减去重复的对角线）：

In [389]: M+M.T-sparse.diags(M.diagonal(),dtype=int)
Out[389]: 
<10x10 sparse matrix of type '<class 'numpy.int32'>'
    with 43 stored elements in Compressed Sparse Row format>
In [390]: _.A
Out[390]: 
array([[0, 7, 7, 0, 9, 0, 7, 0, 0, 9],
       [7, 0, 7, 8, 0, 8, 0, 0, 9, 0],
       [7, 7, 0, 7, 0, 0, 9, 0, 8, 0],
       [0, 8, 7, 0, 0, 0, 6, 0, 6, 6],
       [9, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 8, 0, 0, 0, 0, 8, 9, 0, 8],
       [7, 0, 9, 6, 0, 8, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 9, 0, 0, 8, 8],
       [0, 9, 8, 6, 0, 0, 0, 8, 6, 8],
       [9, 0, 0, 6, 0, 8, 0, 8, 8, 0]], dtype=int32)

双分配方法：

In [391]: M=sparse.lil_matrix((10,10),dtype=int)
In [392]: for i in range(10):
     ...:     for j in range(i,10):
     ...:         v=np.random.randint(0,10)
     ...:         if v>5:
     ...:             M[i,j]=v
     ...:             M[j,i]=v

我没有做过任何计时。

一种coo做法：

In [398]: data,rows,cols=[],[],[]
In [399]: for i in range(10):
     ...:     for j in range(i,10):
     ...:         v=np.random.randint(0,10)
     ...:         if v>5:
     ...:             if i==j:
     ...:                 # prevent diagonal duplication
     ...:                 data.append(v)
     ...:                 rows.append(i)
     ...:                 cols.append(j)
     ...:             else:
     ...:                 data.extend((v,v))
     ...:                 rows.extend((i,j))
     ...:                 cols.extend((j,i))
     ...:                 
In [400]: sparse.coo_matrix((data,(rows,cols)),shape=(10,10)).A
Out[400]: 
array([[0, 8, 0, 6, 8, 9, 9, 0, 0, 0],
       [8, 7, 0, 0, 0, 6, 0, 8, 0, 0],
       [0, 0, 0, 0, 0, 0, 9, 9, 7, 9],
       [6, 0, 0, 0, 7, 0, 0, 0, 0, 6],
       [8, 0, 0, 7, 0, 0, 8, 0, 0, 0],
       [9, 6, 0, 0, 0, 0, 6, 0, 0, 0],
       [9, 0, 9, 0, 8, 6, 8, 0, 0, 0],
       [0, 8, 9, 0, 0, 0, 0, 6, 0, 6],
       [0, 0, 7, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 9, 6, 0, 0, 0, 6, 0, 9]])

================

制作上面的 tri coo 矩阵可能会快一点，并通过列表（或数组）连接扩展到较低的矩阵

In [401]: data,rows,cols=[],[],[]
In [402]: for i in range(10):
     ...:     for j in range(i,10):
     ...:         v=np.random.randint(0,10)
     ...:         if v>5:
     ...:            data.append(v)
     ...:            rows.append(i)
     ...:            cols.append(j)

In [408]: sparse.coo_matrix((data,(rows,cols)),shape=(10,10)).A
Out[408]: 
array([[8, 0, 0, 9, 8, 7, 0, 7, 9, 0],
       [0, 7, 6, 0, 0, 7, 0, 0, 9, 0],
       [0, 0, 9, 8, 0, 9, 6, 0, 0, 6],
...]])

In [409]: data1=data+data
In [410]: rows1=rows+cols
In [411]: cols1=cols+rows
In [412]: sparse.coo_matrix((data1,(rows1,cols1)),shape=(10,10)).A

这复制了对角线，我需要以一种或其他方式解决它（重复的 coo 索引相加）。但它给出了如何将coo样式输入收集到更大的块中的想法。

Answer 2

是的，肯定有更有效和简单的方法。如果您正在创建矩阵，hpaulj 的答案应该有效，但如果您已经有一个，则可以执行以下操作：

rows, cols = sparse_matrix.nonzero()
sparse_matrix[cols, rows] = sparse_matrix[rows, cols]

这应该适用于除 coo_matrix 之外的所有类型的 scipy 稀疏矩阵。

编辑：注意到 coo_matrix。