Does anybody know the efficient implementation of sparse boolean matrix multiplication? I'm interested in both CPU and GPGPU implementations because it is necessary to multiply matrices of different sizes (from 8x8 to up to 10^8x10^8). Currently, I use cuSPARSE library, but it supports only numerical matrices (float, double etc) and this fact leads to huge overhead (by memory and time) which is critical in my task.
1
votes
Look up Sparse matrices (scipy.sparse)
- jpp
@jp_data_analysis Thanks. But looks like generic sparse matrix library. Is it really better than cuSPARSE? Can it handle boolean matrix optimally? I can't find a way to do it. In any case I should specify a value type, which meens that space for values storage will be allocated. I want to avoid it.
- gsv
For CPU, I've been storing them in a Judy1 array where the top 32 bits are the row and the bottom 32 bits are the column. Traversing rows is quite quick. I haven't used it for multiplication, so I don't know how well it would work for that particular use case, but for managing giant adjacency matrices, it is both time and space efficient. I would keep a swizzled version too for when you need column traversal.
- Robert Fraser
1 Answers
0
votes
Since a boolean matrix can be viewed as the adjacency matrix of some (bipartite) graph, its product with another matrix can be interpreted as the distance 2 connections between the nodes of two subgraphs linked by a common set of nodes. To avoid wasting space and exploit some amount of bit parallelism, you could try using some form of succint data structure for graph storage and manipulation. One such family of data structures which could be useful in your case is the K2-tree (or Kn in general), which uses an approach to store the adjacencies similar to spatial decompositions such as quad- and oct- trers. Ultimately, the best algorithm and data structure will heavily depend on the dimension and sparsity patterns of your matrices.
