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.

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