How much faster is multiplication using a sparse matrix library than normal multiplication over a hash table?”
A sparse matrix library is going to store the elements of the matrix in the natural order, so that elements in the same row are close to each other. Your current hash algorithm (by definition) scatters the elements of your matrix randomly throughout the buckets. When writing matrix algorithms, the cache hit rate is King in determining performance, and a hash table has very bad locality of reference. Using a hash table gets you quick and easy random access to the elements, but you don’t need that to do multiplication. Matrix multiplication is a very structured operation that lends itself to sequential rather than random access. A packed format may cost you a little in element access time, but it should work fine for multiplication. Plus it cuts down on memory size, which is the whole reason to use a sparse format in the first place. The other thing to consider is that sparselib is going to be optimized for matrix math, and the only people that care about sparse matricies are those using
