A.1.6.2 Создание разреженных матриц в файлах Oct ¶

Существуют два полезных подхода к созданию разреженной матрицы. Первый заключается в создании трех векторов, представляющих индексы строк, индексы столбцов и значения данных, и построении матрицы на основе этих векторов. Второй вариант — создание разреженной матрицы с соответствующим объёмом памяти и последующее заполнение значений. Оба метода имеют свои преимущества и недостатки.

Ниже приведен пример создания небольшой разреженной матрицы с использованием первого метода

int nz, nr, nc;
nz = 4, nr = 3, nc = 4;

ColumnVector ridx (nz);
ColumnVector cidx (nz);
ColumnVector data (nz);

ridx(0) = 1; cidx(0) = 1; data(0) = 1;
ridx(1) = 2; cidx(1) = 2; data(1) = 2;
ridx(2) = 2; cidx(2) = 4; data(2) = 3;
ridx(3) = 3; cidx(3) = 4; data(3) = 4;
SparseMatrix sm (data, ridx, cidx, nr, nc);

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

Как обсуждалось в главе о разреженных матрицах, значения разреженной матрицы хранятся в порядке возрастания по столбцам. Хотя данные, передаваемые пользователем, не обязаны соответствовать этому требованию, предварительная сортировка данных существенно ускорит создание разреженной матрицы.

Недостатком этого метода создания разреженной матрицы является кратковременное существование двух копий данных. Для задач с очень ограниченными ресурсами памяти этот метод может быть не лучшим способом создания разреженной матрицы.

Альтернативный метод заключается в первоначальном создании разреженной матрицы с необходимым количеством ненулевых элементов, а затем их последующем заполнении. Пример кода:

int nz, nr, nc;
nz = 4, nr = 3, nc = 4;
SparseMatrix sm (nr, nc, nz);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;

Это создаёт ту же матрицу, что и ранее. Опять же, хотя это не строго необходимо, существенно быстрее, если разреженная матрица создаётся, а элементы добавляются в порядке возрастания по столбцам. Причина в том, что при вставке элементов в конец текущего списка известных элементов, перемещать элементы матрицы для вставки нового элемента не нужно; обновляются только индексы столбцов.

Есть несколько дополнительных моментов, которые следует учесть при использовании этого метода создания разреженных матриц. Во-первых, возможно создание разреженной матрицы с меньшим количеством элементов, чем фактически вставлено в матрицу. Поэтому

int nr, nc;
nr = 3, nc = 4;
SparseMatrix sm (nr, nc, 0);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;

является вполне допустимым. Однако это очень плохая идея, потому что при добавлении каждого нового элемента в разреженную матрицу матрица запрашивает больше памяти и перераспределяет её. Это дорогостоящая операция, которая существенно замедлит данный метод создания разреженной матрицы. Допустимо создание разреженной матрицы с избыточным объёмом памяти, поэтому в данном примере значение nz больше 4 также допустимо. Недостатком является то, что матрица занимает больше памяти, чем строго необходимо.

Конечно, не всегда возможно определить количество ненулевых элементов до заполнения матрицы. По этой причине дополнительный неиспользуемый объём памяти разреженной матрицы может быть удалён после её создания с помощью maybe_compress функции. Помимо освобождения неиспользуемого объёма памяти, maybe_compress также может удалить нулевые элементы из матрицы. Удаление нулевых элементов из матрицы контролируется установкой аргумента функции maybe_compress на true. Однако стоимость удаления нулей высока, поскольку это подразумевает повторную сортировку элементов. Если возможно, лучше, чтобы пользователь избегал добавления ненулевых нулей изначально.

Пример использования maybe_compress:

int nz, nr, nc;
nz = 6, nr = 3, nc = 4;

SparseMatrix sm1 (nr, nc, nz);
sm1(0,0) = 1; sm1(0,1) = 2; sm1(1,3) = 3; sm1(2,3) = 4;
sm1.maybe_compress ();   // No zero elements were added

SparseMatrix sm2 (nr, nc, nz);
sm2(0,0) = 1; sm2(0,1) = 2; sm(0,2) = 0; sm(1,2) = 0;
sm1(1,3) = 3; sm1(2,3) = 4;
sm2.maybe_compress (true);  // Zero elements were added

Использование функции maybe_compress следует избегать, если это возможно, так как это замедлит создание матрицы.

Третий способ создания разреженной матрицы — работа непосредственно с данными в сжатом формате строк. Пример этого расширенного метода может быть

octave_value arg;
...
int nz, nr, nc;
nz = 6, nr = 3, nc = 4;   // Assume we know the max # nz
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();

int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
  {
    for (int i = 0; i < nr; i++)
      {
        double tmp = m(i,j);
        if (tmp != 0.)
          {
            sm.data(ii) = tmp;
            sm.ridx(ii) = i;
            ii++;
          }
      }
    sm.cidx(j+1) = ii;
 }
sm.maybe_compress ();  // If don't know a priori the final # of nz.

что, вероятно, является наиболее эффективным методом создания разреженной матрицы.

Наконец, иногда может возникнуть ситуация, когда первоначально выделенного объёма памяти недостаточно для полного хранения разреженной матрицы. Поэтому существует метод change_capacity для перераспределения памяти разреженной матрицы. В таком случае предыдущий пример необходимо изменить на

octave_value arg;
...
int nz, nr, nc;
nz = 6, nr = 3, nc = 4;   // Guess the number of nz elements
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();

int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
  {
    for (int i = 0; i < nr; i++)
      {
        double tmp = m(i,j);
        if (tmp != 0.)
          {
            if (ii == nz)
              {
                nz += 2;   // Add 2 more elements
                sm.change_capacity (nz);
              }
            sm.data(ii) = tmp;
            sm.ridx(ii) = i;
            ii++;
          }
      }
    sm.cidx(j+1) = ii;
 }
sm.maybe_compress ();  // If don't know a priori the final # of nz.

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