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.

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