PDA

View Full Version : Free source: Sparse Matrix


stuh505
03-15-2006, 11:03 PM
Hey guys, here is some code for a sparse matrix I wrote. This is a very general struct that many people may find useful.

A sparse matrix works like a regular matrix except that it does not waste memory by storing blank entries, so it is ideal if you want to be storing values over a large range of space but still want to be able to look up values quickly.

To store some values at [1,1] and [300,400] in a regular matrix would require a 300x400 matrix....and would store 120,000 values. A sparse matrix can store this using only 6 values.
The sparse matrix also allows you to store and retrieve elements pretty quickly. If your matrix is very sparse it will take O(1) time to get/set a value (same as regular matrix). If your matrix is very dense it can take up to O(r) time to get/set, where r is the number of values in the row you are looking at.

Example:

m = (sparseMatrix2d 0) --where 0 is default value for unassigned coordinates
m.setValue 200 300 4
m.getValue 200 300 --returns 4
m.getValue 200 299 --returns 0
m.erase
m.getValue 200 300 --returns 0

rdg
03-16-2006, 08:27 AM
thank you.
I like it.

Georg

f97ao
03-16-2006, 02:19 PM
thank you.
I like it.

Georg

Haha, this is great. Only yesterday me and a collegue was discussing spare matrices and that they can be extremely useful at times :)
/Andreas

stuh505
03-16-2006, 07:33 PM
I have added two additional types of sparse matrices.

The first type, sparseMatrix2d, is for row/col indexing, starting at 1,1

Now I provide sparseMatrix3d which allows x/y/z indexing starting at 1,1,1

Also, sparseMatrix3dc, which allows x/y/z indexing from negative infinity to infinity

Usage is exactly the same as the first kind

eg,

m = (sparseMatrix3dc 0)
m.setValue -200 0 1 3
m.getValue -200 0 1 --returns 3

CGTalk Moderation
03-16-2006, 07:33 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.