Форматы представления разреженных матриц

Представление разреженных матриц.

Рассмотрим форматы представления разреженных матриц, т.е. матриц имеющих большое число нулевых элементов. В этом случае обычное представление матриц в виде массива будет избыточно, поэтому используются специальные форматы: RR(C)O и RR(C)U. Рассмотрим сначала формат RR(C)O. Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Ordered" (строчное представление, полное и упорядоченное). В данном формате вместо одного двумерного массива, используются три одномерных. Значения ненулевых элементов матрицы и соответствующие им столбцовые индексы хранятся в этом формате по строкам в двух массивах AN и JA. Массив указателей IA, используется для ссылки на компоненты массивов AN и JA, с которых начинается описание очередной строки. Последняя компонента массива IA содержит указатель первой свободной компоненты в массивах AN и JA, т.е. равна числу ненулевых элементов матрицы, увеличенному на единицу.

Проще всего разобраться с представлением на примере, пусть A матрица с тремя строками и десятью столбцами:

тогда ее представление в формате RR(C)O будет иметь вид:

Т.е. массив AN содержит все не нулевые элементы исходной матрицы A, массив JA номер столбца в котором находится соответствующий элемент из AN и наконец массив IA содержит номер с которого начинается описание элементов в массивах JA и AN. Таким образом информация об элементах 3 строки матрицы храниться в элементах с IA[3]=4 по IA[4]-1=5 массивов JA и AN. Заметим, что IA(2)=IA(3)=4, а это означает, что вторая строка матрицы A нулевая.

В общем случае описание r-й строки матрицы A хранится в компонентах с IA[r] до IA[r + 1]-1 массивов AN и JA. Если IA[r + 1] = IA[r], то это означает, что r - я строка нулевая. Количество элементов в массиве IA на единицу больше, чем число строк исходной матрицы, а количество элементов в массивах JA и AN равно числу ненулевых элементов исходной матрицы.

Рассмотренный формат называют полным, поскольку в нем указываются все ненулевые элементы матрицы A, упорядоченным, поскольку элементы каждой строки матрицы A хранятся по возрастанию столбцовых индексов, и строчным, поскольку информация о матрице A указывается по строкам.

Говорят, что массивы IA и JA представляют портрет (структуру) матрицы A. Если алгоритм, реализующий какую - либо операцию над разреженными матрицами, разбит на этапы символической обработки, на котором определяется портрет результирующей матрицы, и численной обработки, на котором определяются значения элементов результирующей матрицы, то массивы IA и JA заполняются на первом этапе, а массив AN - на втором.

Рассмотрим теперь формат RR(C)U.

Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Unordered" (строчное представление, полное, но неупорядоченное). Формат RR(C)U отличается от RR(C)O тем, что в данном случае соблюдается упорядоченность строк, но внутри каждой строки элементы исходных матриц могут храниться в произвольном порядке. Такие неупорядоченные представления могут быть весьма удобны в практических вычислениях. Результаты большинства матричных операций получаются неупорядоченными, а их упорядочение стоило бы значительных затрат машинного времени. В то же время, за немногими исключениями, алгоритмы для разреженных матриц не требуют, чтобы их представления были упорядоченными. Для приведенной выше матрицы A, например, ее представление в формате RR(C)U может иметь вид:

Несколько замечаний по поводу рассмотренных форматов представления.

Первое. Понятно, что представление матрицы в формате RR(C)O так же является и представлением в формате RR(C)U, но не наоборот.

Второе. Из представления матрицы в формате RR(C) нельзя получить информацию о количестве столбцов исходной матрицы. Действительно, если с количеством строк все достаточно ясно, их на единицу меньше, чем элементов массива IA, то единственно, что мы можем сказать относительно числа столбцов, это то, что их не больше чем максимум среди всех элементов массива JA. Например, возьмем матрицу рассмотренную выше, на основе представления в формате RR(C)U мы можем сказать только, что столбцов не меньше 8, но ни что не указывает нам на то, что их ровно 10.

Третье. Целесообразно использовать представления RR(C) в случае, если матрица содержит значительное число нулевых элементов. Получим связь между числом ненулевых элементов исходной матрицы и экономией памяти при использовании форматов RR(C).

Пусть дана матрица A размера NxM, содержащая NNZ не нулевых элементов. Положим для хранения значения элемента матрицы мы используем u - байт памяти, для хранения номера строки/стобца - v - байт. Тогда для хранения матрицы в обычном формате нам понадобиться u*N*M байт, а для хранения в формате RR(C) v*(N+1)+(u+v)*NNZ. И следовательно, представление в формате RR(C) целесообразно использовать в случае когда, NNZ < (uNM-vN-v)/(u+v).

Так если элементы матрицы действительные числа(тогда обычно u=8) и число строк и столбцов не превосходит 255(v=1), то получаем оценку NNZ < (8NM-N-1)/9. Так вновь возращаясь к примеру, описанному выше, получаем, что число ненулевых элементов не должно превышать (8*10*3-10-1)/9=25. А в нашем случае, когда NNZ=5 получаем экономию 8*10*3-(4+5*(8+1))=191 байт.