How much faster is multiplication using a sparse matrix library than normal multiplication over a hash table?

I'm debating whether to rewrite my code to make use of sparse matrix library such as SparseLib (math.nist.gov/sparselib++/). Currently, I'm storing the data in hash tables with the row and column numbers as keys. Any rough guesses as to how much faster using a good sparse data library might be?

How do they get these speed increases? Thank you. Asked by ruteger 57 months ago Similar questions: faster multiplication sparse matrix library normal hash table Computers > Software Development.

Similar questions: faster multiplication sparse matrix library normal hash table.

Possibly halve time, rarely an order of magnitude. They omit "zero multiplications". Speed increases can be achieved by:- tightening up code/loops to better fit into cache memory (both processory & external)- omitting zero and unity multiplications (trying to avoid multiplying by zero or one)- keeping in mind performance costs of various operations and trying to use operations which execute faster"How much faster" is very dependent on:- size (# rows, # columns, and how many non-zero values) of your sparse matrices- what environment (hardware) your code is running in.

Getting a computation to run in half the time can often be achievedif you are willing to spend the effort and time. Getting order of magnitude (10x) improvements can sometimes be achieved,but depends on how inefficient it is now, and again how much effort,benchmarking and testing you are willing to do. "SparseLib++ is a C++ class library for efficient sparse matrix computations across various computational platforms."it is written to take better advantage of available hardware- tightening up loops to better fit into available cache memory (processor and/or external)- possibly taking advantage of parallelism (dual/quad core etc) when available"The software package consists of matrix classes encompassing several sparse storage formats (e.g. Compressed row, compressed column and coordinate formats), and providing basic functionality for managing sparse matrices.

"Your "hash table" storage is similar to the library's "co-ordinate format"i.e. Row, column, and number (triplets)"The Sparse BLAS Toolkit is used to for efficient kernel mathematical operations (e.g. Sparse matrix-vector multiply) and to enhance portability and performance across a wide range of computer architectures. ""Included in the package are various preconditioners commonly used in iterative solvers for linear systems of equations."

Sources: My personal experience and professional opinion.

I would expect it to be dramatically faster 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 very large datasets. Optimization is very important in those domains, so a decent amount of work has probably gone into it.

Especially since it's from a scientifically oriented organization like NIST. As a side note, depending on how sparse your matrix is, you might not be saving much space with your current hash table implementation. The hash table has to maintain a certain percentage of empty space in order to work efficiently, plus you have to store the actual keys.

Depending on how large and how sparse your matricies are, you might try going back to a full matrix format, in which case your multiplication will be dead simple and fast.

1 Thanks for the answer! I hadn't thought much about the CPU's cache.

Thanks for the answer! I hadn't thought much about the CPU's cache.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.