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