Участник:Janyell/Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор

Авторы страницы: Сычева Е.А и Хахалин А.С.

Свойства и структура алгоритмов

Общее описание алгоритма

Разреженная матрица — матрица с большим количеством нулевых элементов.

Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разреженной. Матрицу порядка [math]\displaystyle{ n }[/math] называют разреженной, если число ее ненулевых элементов :

• есть [math]\displaystyle{ O(n) }[/math]. Приве­денное определение полезно только для теоретических целей типа попытки оценить асимптотическое поведение алгоритма.
• ограничено в строке, в типичном случае от 2 до 10.
• выражается как [math]\displaystyle{ n^{1+\gamma} }[/math], где [math]\displaystyle{ \gamma \lt 1 }[/math].
• таково, что для данной матрицы, данного алгоритма и данной вычислительной машины имеет смысл извлекать выгоду из на­личия в ней многих нулей.

Всякую разреженную матрицу можно обрабатывать так, как если бы она была плотной: напротив, вся­кую плотную, или заполненную, матрицу можно обрабатывать алгоритмами для разреженных матриц. В обоих случаях полу­чатся правильные численные результаты, но вычислительные затраты возрастут. Приписывание матрице свойства разреженности эквивалентно утверждению о существовании алгоритма, исполь­зующего ее разреженность и делающего вычисления с ней дешевле по сравнению со стандартными алгоритмами.

Три основных идеи, которые направляли развитие большей части технологии разреженных матриц:

• хранить только ненулевые элементы. Разреженная матрица, будучи множеством чисел, не имеющим регулярности, не может быть представлена в памяти машины тем же простым способом, что и полная матрица. Поэтому возникает необходимость дополнительно хранить индексную информацию, указывающую расположение каждого элемента в регулярном массиве.
• оперировать только с ненулевыми элементами. Число операций, производимых машиной при исполнении алгоритма, пропорционально числу ненулевых элементов, а не числу всех элементов матрицы.
• сохранять разреженность. Хоро­ший алгоритм для разреженных матриц пытается сохранить раз­реженность, по возможности уменьшая заполнение.

Однако многие схемы хранения допускают определенную долю нулей, и алгоритм обрабатывает их, как если бы они не были нулями. Алгоритм, хранящий и обрабатывающий меньшее число нулей, более сложен, труднее программируется и целесообразен только для достаточно больших матриц.

Диагональная схема хранения ленточных матриц

С ленточными матрицами связана простейшая и наиболее широко применяемая стратегия использования нулевых элементов матрицы. Матрицу [math]\displaystyle{ A }[/math] называют ленточной, если все ее ненулевые элементы заключены внутри ленты, образованной диагоналями, параллельными главной диагонали. Таким образом, [math]\displaystyle{ a_{ij} = 0 }[/math], если [math]\displaystyle{ |i - j| \gt b }[/math], и [math]\displaystyle{ a_{k, k-b} \ne 0 }[/math], либо [math]\displaystyle{ a_{k, k+b} \ne 0 }[/math] хотя бы для одного значения [math]\displaystyle{ k }[/math]. Здесь [math]\displaystyle{ b }[/math] — полуширина, а [math]\displaystyle{ 2b + 1 }[/math] — ширина ленты. Лентой матрицы [math]\displaystyle{ A }[/math] называется множество элементов, для которых [math]\displaystyle{ |i - j| \leq b }[/math]. Другими словами, для всякой строки [math]\displaystyle{ i }[/math] ленте принадлежат все элементы со столбцовыми индексами от [math]\displaystyle{ i - b }[/math] до [math]\displaystyle{ i + b }[/math], т. е. [math]\displaystyle{ 2b + 1 }[/math] элементов.

Если матрица симметрична, то достаточно хранить ее полу­ленту. Верхняя полулента состоит из элементов, находящихся в верхней части ленты, т. е. таких, что [math]\displaystyle{ 0 \lt j - i \leq \beta }[/math]; нижняя полулента состоит из элементов нижней части ленты, т. е. таких, что [math]\displaystyle{ 0 \lt i - j \leq \beta }[/math]; в обоих случаях в строке [math]\displaystyle{ \beta }[/math] элементов.

Диагональная схема хранения симметричной ленточной ма­трицы [math]\displaystyle{ A }[/math] порядка [math]\displaystyle{ n }[/math] и полуширины ленты [math]\displaystyle{ \beta }[/math] представляет собой массив [math]\displaystyle{ AN (I, J) }[/math] размером [math]\displaystyle{ n \times (\beta + 1) }[/math]. Главная диагональ хранится в последнем столбце, а нижние кодиагонали — в остальных столбцах со сдвигом на одну позицию вниз при каждом смещении влево.

Для несимметричной матрицы [math]\displaystyle{ A }[/math] необходим массив размером [math]\displaystyle{ n \times(2\beta + 1) }[/math]; нижняя полулента и главная диагональ хранятся прежним образом, а верхние кодиагонали — в правой части массива со сдвигом на одну позицию вверх при каждом смещении вправо. Диагональная схема удобна, если [math]\displaystyle{ \beta \lt \lt n }[/math]. Она является схемой прямого доступа в том смысле, что имеется простое взаимно однозначное соответствие между положением элемента в матрице [math]\displaystyle{ A }[/math] и его положением в массиве: [math]\displaystyle{ a_{ij} }[/math] хранится компонентой [math]\displaystyle{ AN (i, j - i + \beta + 1) }[/math].

Программная реализация алгоритма

Существующие реализации алгоритма

Для вычислений с разреженными матрицами создано несколько библиотек:

• SparseLib++ (C++)
• uBLAS (C++, в составе Boost)
• SPARSPAK (Fortran)
• CSparse (C)

и другие.

Литература

<references \>