Coordinator
Nov 27, 2012 at 12:40 PM
Edited Nov 27, 2012 at 12:44 PM

Hi,
Uh. Sparse matrices are much slower than dense ones by design, but 4h is unacceptable. Some ideas:
A) If possible, always initialize a sparse matrices row by row, in ascending order.
Quick Example (in F#, but would be equivalent in C#), initializing a matrix (110M fields) with 2M values:
let good = new SparseMatrix(10500,10500)
for row in 0..999 do
for col in 0..999 do
good.At(10*row, 10*col, float32 (Math.Atan2(float row, float col)))
good.At(2+10*row, 3+10*col, float32 (row+col))
This needs roughly 1 minute on my machine. Still slow, but much better than your 4h.
let bad = new DenseMatrix(10500,10500)
for col in 0..999 do
for row in 0..999 do
bad.At(10*row, 10*col, float32 (Math.Atan2(float row, float col)))
bad.At(2+10*row, 3+10*col, float32 (row+col))
This second version is not row by row, and needs almost 20 times the time of the first example (lot of copying involved).
Hence, if you can, sort your fields by rows and then cols, ascending, before insertion. Thinking about it, we could provide some sort of sparse matrix initialization helper to support such scenarios. They could avoid almost if not all copying if the list
of nonzero cells is available in memory at the beginning, speeding it up significantly.
B) Minor: Use At(r,c,v) instead of the [r,c] indexer if you don't need range checking (slightly faster)
Although in this case it probably doesn't make much of a difference
C) Directly populate the underlying storage
Create an instance of the SparseCompressedRowMatrixStorage class and populate the RowPointer/ColumnIndex/Values arrays directly. Then create the matrix using
new SparseMatrix(storage). This is clearly the most performant approach (as long as we do not provide an initializer as mentioned above), but requires knowledge of the chosen storage layout.
D) Consider dense matrices
If I change the above example to use a dense matrix instead (after all such a 100M cell matrix still fits into memory easily):
let dense = new DenseMatrix(10500,10500)
for row in 0..999 do
for col in 0..999 do
dense.At(10*row, 10*col, float32 (Math.Atan2(float row, float col)))
dense.At(2+10*row, 3+10*col, float32 (row+col))
then the example runs in less than a second. However, any operation on that matrix would obviously then be very inefficient, but it depends what you actually want to do with it.
Thinking about it, we should really consider to provide some efficient sparse matrix initializer (as mentioned in A), that avoids any expensive copying at the cost of a twopass process. In your case that may work nicely, since it seems you already know
all possible nonzero value indices at the beginning (in your hash table). Let me know what you think.
Thanks,
Christoph
