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