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.

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