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, заключается в том, что все элементы в строках хранятся в порядке возрастания их индекса строки, что ускоряет определенные операции. Однако это налагает необходимость сортировки элементов при создании разреженных матриц. Неупорядоченные элементы потенциально являются преимуществом, поскольку это упрощает и ускоряет операции, такие как конкатенация двух разреженных матриц, но добавляет сложность и проблемы со скоростью в других местах.