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