有人知道稀疏布尔矩阵乘法的有效实现吗？我对CPU和GPGPU实现感兴趣，因为有必要将不同大小的矩阵（从8x8到10 ^ 8x10 ^ 8）相乘。目前，我使用cuSPARSE库，但它只支持数值矩阵（float，double等），这一事实导致了巨大的开销（按内存和时间），这对我的任务至关重要。
由于布尔矩阵可以被视为某些（二分）图的邻接矩阵，因此其与另一个矩阵的乘积可以被解释为由一组公共节点链接的两个子图的节点之间的距离2连接。为了避免浪费空间并利用一些位并行性，您可以尝试使用某种形式的succint数据结构进行图形存储和操作。在你的情况下可能有用的一个这样的数据结构系列是K2树（或一般的Kn），它使用一种方法来存储类似于空间分解的邻接，例如四边形和八边形。最终，最好的算法和数据结构将在很大程度上取决于矩阵的维度和稀疏性模式。