22.1.1 Хранение разреженных матриц

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

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

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

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

Фактически, индекс столбца содержит на один элемент больше, чем количество столбцов, причем первый элемент всегда равен нулю. Преимущество этого — упрощение кода, так как нет специального случая для первого или последнего столбца. Вот короткий пример, демонстрирующий это на C.

for (j = 0; j < nc; j++)
    for (i = cidx(j); i < cidx(j+1); i++)
       printf ("nonzero element (%i,%i) is %d\n",
           ridx(i), j, data(i));

Ясность можно получить, рассмотрев пример того, как вышесказанное применяется к матрице-примеру. Рассмотрим матрицу

1   2   0  0
    0   0   0  3
    0   0   0  4

Ненулевые элементы этой матрицы:

(1, 1)  ⇒ 1
   (1, 2)  ⇒ 2
   (2, 4)  ⇒ 3
   (3, 4)  ⇒ 4

Эти элементы будут храниться в виде трех векторов cidx, ridx и data, представляющих индексацию столбцов, индексацию строк и данные соответственно. Содержимое этих трех векторов для вышеприведенной матрицы будет:

cidx = [0, 1, 2, 2, 4]
  ridx = [0, 0, 1, 2]
  data = [1, 2, 3, 4]

Обратите внимание, что это представление этих элементов при предположении, что первая строка и первый столбец начинаются с нуля, в то время как в самом Octave индексация строк и столбцов начинается с единицы. Таким образом, количество элементов в i-м столбце задается cidx (i + 1) - cidx (i).

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

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