Data Structure for Storing Sparse Matrices

Question

I need to do some mathematics operations on sparse matrices. I noticed that using arrays may not be the most efficient way to utilize my memory, especially since the matrices may have over 200 rows. I have considered using a linked list too, but I'm not sure if that'll be better. Is there any suitable data structure [approach] to this situation.

Answer 1

How many "over 200 rows"? How sparse? A 1000x1000 matrix of doubles is still less than 8MB, which is not something I'd worry about unless you need to work with a lot of them simultaneously.

The ideal data structure depends mainly on what kind of operations you need to perform.

Note that there are ready-to-use sparse matrix libraries for all common languages out there - you're much better off using one of those than rolling your own.

Answer 2

Here are a few open source Java maths libraries that include sparse matrices. You could study the data structures used (or even just use one of them if programming in Java).

• Colt
• Jsci
• Matrix Toolkits Java

Answer 3

There's a new matrix library out for java that looks like it might have good Sparse Matrix support: UJMP: The Universal Java Matrix Package