space allocated by compressed_matrix in boost

How much space is allocated by boost compressed_matrix? Is it true that it only allocates space for non-zero elements? If this is true, I don't understand why the following code gives bad_alloc error.

namespace bubla = boost::numeric::ublas; 
typedef double value_type; 
typedef bubla::compressed_matrix<value_type> SparseMatrix; 
unsigned int m = 10000*10000; 
SparseMatrix D(m,m,3*m), X; 

It should only allocate space for 3*m=3*10000*10000 elements right?

Could you please help clarify? What data structure in boost I could use to on开发者_Go百科ly allocate space for the non-zero elements. Secondly, how do I set values for the non-zero elements?

Many thanks.

Note that you are defining m to be 10000*10000 in your above example which means you are trying to allocate 300 million doubles or 2.4 GB (assuming 8 bytes per double).

If you just want a sparse 10000 x 10000 matrix just define "m=10000".

The CRS format

First of all a one-minute intro to the compressed format. Given the matrix

+---+---+---+---+
| A | 0 | B | 0 |
+---+---+---+---+
| 0 | C | 0 | 0 |
+---+---+---+---+
| 0 | 0 | D | E |
+---+---+---+---+

you can store it quite efficiently in compressed row storage (CRS) format (which is the default format for ublas::compressed_matrix), if you store the number of non-zeros per row, the column index and the value of each non-zero entry:

                     +---+---+---+
number of non-zeros  | 2 | 1 | 2 |
                     +---+---+---+
                     +---+---+---+---+---+
column index         | 0 | 2 | 1 | 2 | 3 |
                     +---+---+---+---+---+
                     +---+---+---+---+---+
value                | A | B | C | D | E |
                     +---+---+---+---+---+

Note: There are different variants, e.g. instead of the number of non-zeros (NNZ) you can also store for each row the index to its first element in the column index and value vectors. Or you can store pointers to these values where a new row starts and so on. However, they all require more or less the same amount of memory.

Memory requirement

The memory needed for the CRS format is roughly

memoryRequired = numberOfRows * sizeof(index_type) 
                 + NNZ * sizeof(index_type) 
                 + NNZ * sizeof(value_type)

plus some overhead to store the lengths of the arrays, pointers to the data and so on. However, compared to the memory the data itself requires, and given the fact that compressed matrices tend to be quite large (otherwise you could use a dense matrix, anyway), this overhead is usually negligible.

For your example

You are trying to allocate a CRS matrix with m rows, m columns and 3*m non-zero entries, with m being 10^8. This would require the following amount of memory, assuming that you use uint32 as type for the indices and double as type for the entries:

NNZ vector              m * 4 =  381.5 MB
column index vector   3*m * 4 = 1144.4 MB
value vector          3*m * 8 = 2288.8 MB
-----------------------------------------
total                           3814.7 MB

So already your matrix requires roughly 4 GB of memory. If you also want to store some vectors, you are pretty soon out of memory on conventional desktop machines.

3*m = 300000000