Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What's the fastest way to represent and multiply sparse boolean matrices?

So, I'm using boolean matrices whose dimension is usually a couple dozen to a couple hundred, they are usually quite sparse (just some 2-4 non-zeros in most rows and columns) and my runtime is heavily dominated by their multiplication.

What datastructure suits best for speeding up multiplication under these circumstances?

Currently I'm storing each matrix in a contiguous bitset (array of 64-bit longs) row-wise, and multiplicating them with basically the standard algorithm, just sped up for sparsity with the fast operation of locating the next set bit in a word, and with vectorization by bitmask operations.

Should I perhaps use some sparse representation indeed?

like image 739
jkff Avatar asked Sep 05 '10 13:09

jkff


1 Answers

You might want to consider using a quadtree representation. The quadtree can encode a sparse matrix pretty well, and lends itself to a pretty easy (and cache efficient) recursive multiply implementation. Make the base case a 8x8 matrix so you can implement the multiply as a (assembly-optimized?) 64-bit by 64-bit operation.

like image 50
Keith Randall Avatar answered Nov 15 '22 21:11

Keith Randall