boost中compressed_matrix分配的空间 [英] space allocated by compressed_matrix in boost

问题描述

boostcompressed_matrix分配了多少空间?是否只为非零元素分配空间，这是真的吗?如果这是真的，我不明白为什么下面的代码会出现bad_alloc错误.

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; 

它应该只为3 * m = 3 * 10000 * 10000个元素分配空间，对吗?

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

能否请您澄清一下?我可以使用boost中的哪种数据结构来仅为非零元素分配空间.其次，如何设置非零元素的值?

Could you please help clarify? What data structure in boost I could use to only allocate space for the non-zero elements. Secondly, how do I set values for the non-zero elements?

非常感谢.

推荐答案

CRS格式

首先，一分钟介绍压缩格式.给定矩阵

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 |
+---+---+---+---+

您可以以压缩行存储(CRS)格式(即 ublas::compressed_matrix的默认格式)，如果您存储每行的非零数，列索引和每个非零条目的值:

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 |
                     +---+---+---+---+---+

注意:有不同的变体，例如除了非零数(NNZ)，您还可以为每一行存储在column index和value向量中其第一个元素的索引.或者，您可以在新行开始处存储指向这些值的指针，依此类推.但是，它们都需要或多或少相同的内存量.

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.

CRS格式所需的内存大约为

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.

您正在尝试分配具有m行，m列和3*m非零条目的CRS矩阵，其中m为10^8.假设您将uint32用作索引的类型并将double用作条目的类型，这将需要以下内存量:

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

因此，您的矩阵已经需要大约4 GB的内存.如果您还想存储一些矢量，则很快就会在传统台式机上出现内存不足的情况.

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.

这篇关于boost中compressed_matrix分配的空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！