пространство, выделенное сжатой_матрицей в boost - PullRequest
Новая
       21

пространство, выделенное сжатой_матрицей в boost

0 голосов
/ 20 сентября 2010

Сколько места выделено boost сжатым_matrix? Правда ли, что он выделяет место только для ненулевых элементов? Если это правда, я не понимаю, почему следующий код выдает ошибку bad_alloc. 

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 элементов, верно?

Не могли бы вы помочь уточнить? Какую структуру данных в boost я мог бы использовать, чтобы выделить место только для ненулевых элементов. Во-вторых, как мне установить значения для ненулевых элементов?

Большое спасибо.

Ответы [ 3 ]

1 голос
/ 20 сентября 2010

Обратите внимание, что в приведенном выше примере вы определяете m как 10000 * 10000, что означает, что вы пытаетесь выделить 300 миллионов удвоений или 2,4 ГБ (при условии 8 байтов на удвоение).

Если вы просто хотите разреженную матрицу 10000 x 10000, просто определите "m = 10000".

1 голос
/ 26 июля 2012

Формат CRS

Прежде всего, введение в сжатый формат за одну минуту.Учитывая матрицу 

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

, вы можете довольно эффективно хранить ее в формате сжатого хранения строк (CRS) (который является форматом по умолчанию для ublas::compressed_matrix), если вы храните число ненулей в строке,индекс столбца и значение каждой ненулевой записи: 

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

Примечание: Существуют различные варианты, например, вместо числа ненулевых элементов (NNZ) вы также можетесохранить для каждой строки индекс до его первого элемента в векторах column index и value.Или вы можете хранить указатели на эти значения, где начинается новая строка и так далее.Однако все они требуют более или менее одинакового объема памяти.

Требования к памяти

Объем памяти, необходимый для формата CRS, составляет примерно 

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

плюс некоторые накладные расходыхранить длины массивов, указатели на данные и так далее.Однако, по сравнению с памятью, которой требуются сами данные, и с учетом того факта, что сжатые матрицы имеют тенденцию быть достаточно большими (в противном случае вы могли бы использовать плотную матрицу, в любом случае), эти издержки обычно незначительны.

Вы пытаетесь выделить матрицу CRS с m строками, m столбцами и 3*m ненулевыми записями, с m, равным 10^8.Для этого потребуется следующий объем памяти, при условии, что вы используете uint32 в качестве типа для индексов и double в качестве типа для записей: 

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 ГБ памяти,Если вы также хотите сохранить некоторые векторы, на обычных настольных компьютерах у вас скоро не хватит памяти.

0 голосов
/ 20 сентября 2010

3*m = 300000000

...