自定义类元素的稀疏矩阵运算实现方案咨询

问题 #

我想定义元素为自定义半环类的稀疏矩阵，比如极小加半环的MinPlus类：

class MinPlus(float):
    def __init__(self, value):
        super(MinPlus, self).__init__(value)
      
    def __add__(self, other):
        return MinPlus(min(self, other))
        
    def __mul__(self, other):
        return MinPlus(self + other)

希望让稀疏矩阵的加法和乘法使用自定义的__add__和__mul__逻辑。我已经自己实现了一个Bimodule类的乘法：

def __mul__(self, other):
    if len(self.output) != len(other.input):
        raise ValueError("Bimodule shapes are incompatible.")
    mat = {i+";"+j: reduce(lambda x, y: x + y,[self.mat.get(i+';'+k,self.semiring(0)) * other.mat.get(k+';'+j,self.semiring(0)) for k in self.output]) for i in self.input for j in other.output}
    return Bimodule(self.input, other.output, mat,self.semiring)

其中self.semiring是自定义的半环类。现在想把这个逻辑扩展到大型稀疏矩阵，既可以是针对极小加半环的方案，也想了解其他自定义半环（比如下面的反布尔类）的实现可能：

class AntiBoolean():
    def __init__(self, v):
        self.value=v
        
    def __repr__(self):
        return str(self.value)
        
    def __add__(self, other):
        return AntiBoolean(self.value and other.value)
        
    def __mul__(self, other):
        return AntiBoolean(self.value or other.value)
        
    def zero():
        return AntiBoolean(1)     
    def one():
        return AntiBoolean(0)
   
    def __eq__(self,other):
        return self.value==other.value

想问下能不能用scipy.sparse实现？有没有其他合适的库？之前试过numpy的方案但有问题，不知道从哪入手。

解决方案 #

1. SciPy Sparse 无法直接实现 #

SciPy的稀疏矩阵（比如csr_matrix、csc_matrix）底层依赖numpy数组存储元素，而numpy对自定义类的支持非常有限：

• numpy的元素级运算不会调用自定义类的__add__/__mul__魔术方法，而是依赖内置的数值运算逻辑。
• 稀疏矩阵的核心运算（比如乘法、加法）都是用C语言实现的优化代码，完全硬编码了常规的算术规则，无法替换为自定义半环的运算逻辑。
  所以直接用scipy.sparse来实现自定义半环的矩阵运算走不通。

2. 极小加半环的专属实现 #

极小加半环（热带半环）属于比较常用的特殊半环，你可以基于scipy.sparse的结构手动实现矩阵运算：
比如对于两个CSR矩阵，热带矩阵乘法的逻辑是C[i,j] = min(A[i,k] + B[k,j] for all k)，可以利用稀疏矩阵的非零元素特性来优化计算：

import scipy.sparse as sp

def tropical_mult(A, B):
    # A是csr_matrix，B是csr_matrix
    m, n = A.shape
    n, p = B.shape
    data = []
    indices = []
    indptr = [0]
    
    for i in range(m):
        # 获取A第i行的非零元素和对应的列索引
        a_row_start = A.indptr[i]
        a_row_end = A.indptr[i+1]
        a_cols = A.indices[a_row_start:a_row_end]
        a_vals = A.data[a_row_start:a_row_end]
        
        # 存储当前行的临时结果
        row_result = {}
        for k, a_val in zip(a_cols, a_vals):
            # 获取B第k行的非零元素
            b_row_start = B.indptr[k]
            b_row_end = B.indptr[k+1]
            b_cols = B.indices[b_row_start:b_row_end]
            b_vals = B.data[b_row_start:b_row_end]
            
            for j, b_val in zip(b_cols, b_vals):
                current = a_val + b_val
                if j not in row_result or current < row_result[j]:
                    row_result[j] = current
        
        # 把临时结果转成稀疏格式需要的结构
        indices.extend(row_result.keys())
        data.extend(row_result.values())
        indptr.append(len(indices))
    
    return sp.csr_matrix((data, indices, indptr), shape=(m, p))

这个函数可以直接处理存储为常规数值的稀疏矩阵，实现极小加半环的乘法逻辑，如果你需要用MinPlus类包装元素，只需要在最后把data里的数值转成MinPlus实例即可（不过注意numpy对自定义类的数组支持有限，可能需要用列表存储再转成矩阵）。

3. 通用自定义半环的替代方案 #

如果要支持任意自定义半环，有几个方向可选：

• 手动实现稀疏矩阵结构：像你之前的Bimodule类那样，用字典或类似结构存储非零元素，然后实现自定义的加法和乘法逻辑。这种方式完全可控，适合小众半环，缺点是需要自己处理性能优化（比如按行/列排序、减少遍历次数）。
• 使用代数专用库：
  • NetworkX：虽然是图论库，但它的邻接矩阵可以配合自定义运算，比如在处理路径问题时，可以基于半环规则实现矩阵乘法，适合和图相关的半环应用场景。
  • PyAlgebra：专门面向代数结构的库，支持自定义半环和矩阵运算，对稀疏矩阵的支持也比较灵活，能直接映射你定义的__add__和__mul__逻辑。

内容的提问来源于stack exchange，提问作者edenstar