Thread: What did I miss about boosts sparse matrix library?

Hi,

I want to store 2D terrain information in memory (to be able to process it online) which can become very large. But because the terrain abstractions I'm using are sparsely populated this should not be a problem.
I took a look at the boost sparse matrix adapter classes:

http://www.boost.org/doc/libs/1_35_0...rix_sparse.htm

and tried to play with their little demo program:

Code:

#include <boost/numeric/ublas/matrix_sparse.hpp>
#include <boost/numeric/ublas/io.hpp>


int main ()
{
    using namespace boost::numeric::ublas;
    
    mapped_matrix<char> m (3000, 3000);
    
    for (unsigned i = 0; i < m.size1 (); ++ i)
    {
        for (unsigned j = 0; j < m.size2 (); ++ j)
        {
            m (i, j) = rand() + 1;
        }
    }
    sleep(8);
}

This should fill a matrix with all but zeros of size 3000x3000.
So it is not sparse and should take up 9 megabytes in memory.
If I instead use a vector<vector<char> > it does.
But if I run the test program I see top showing the VmSize going up to about 280 megabytes. Why is that?

Now even more weird: If I fill the matrix completely with zeros it should be very very sparse and should take up far below 9 megabytes in memory. But Top shows exactly the same as if I fill it with non-zero values.

The other sparse matrix adapters the boost library offers (I did not get the difference between them yet) behave about the same.

What did I miss?

Thank you in advance!

But if I run the test program I see top showing the VmSize going up to about 280 megabytes. Why is that?

The sparse matrix needs more memory per non-zero element than a dense matrix. That's the price you pay for the sparseness. mapped_matrix uses a std::map<size_t, T> internally - depending on the tree's implementation, that means that every non-zero node requires 5 or more machine words - that's 40 bytes on a 64-bit system! (As opposed to 1 byte in a dense char-matrix.) So you see, a matrix has to be very sparse indeed before this is worth it.
compressed_matrix uses run-length encoding, if I understand the documentation correctly, so it's good when you have many elements with the same value.

But Top shows exactly the same as if I fill it with non-zero values.

I don't think the matrix is meant to be filled with zeros. Those are there by default, but sparse. I can't find anything in the code that indicates that the matrix frees elements when you assign zero to them. Basically, you're meant to leave the map alone, except for setting the few elements that you care about.

The example in the documentation is poor - notice that it is the same for every matrix type. It doesn't demonstrate anything specific to the sparse matrices.

I have no idea how the Yale format works. The std::map approach has the advantage of being simple.