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

Материал из Алговики
Перейти к навигации Перейти к поиску
(Добавлен раздел "Диагональная схема хранения ленточных матриц")
Строка 26: Строка 26:
  
 
Если матрица симметрична, то достаточно хранить ее ''полу­ленту''. Верхняя полулента состоит из элементов, находящихся в верхней части ленты, т. е. таких, что <math>0 < j - i \leq \beta </math>; нижняя полулента состоит из элементов нижней части ленты, т. е. таких, что <math>0 < i - j \leq \beta</math>; в обоих случаях в строке <math>\beta</math> элементов.
 
Если матрица симметрична, то достаточно хранить ее ''полу­ленту''. Верхняя полулента состоит из элементов, находящихся в верхней части ленты, т. е. таких, что <math>0 < j - i \leq \beta </math>; нижняя полулента состоит из элементов нижней части ленты, т. е. таких, что <math>0 < i - j \leq \beta</math>; в обоих случаях в строке <math>\beta</math> элементов.
 +
 +
''Диагональная схема'' хранения симметричной ленточной ма­трицы <math>A</math> порядка <math>n</math> и полуширины ленты  <math>\beta</math> представляет собой массив <math>AN (I, J)</math> размером <math>n \times (\beta + 1)</math>. Главная диагональ хранится в последнем столбце, а нижние кодиагонали — в остальных столбцах со сдвигом на одну позицию вниз при каждом смещении влево.
 +
 +
Для несимметричной матрицы <math>A</math> необходим массив размером <math>n \times(2\beta + 1)</math>; нижняя полулента и главная
 +
диагональ хранятся прежним образом, а верхние кодиагонали — в правой части массива со сдвигом на одну позицию вверх при каждом смещении вправо. Диагональная схема удобна, если <math>\beta << n </math>. Она является схемой прямого доступа в том смысле, что имеется простое взаимно однозначное соответствие между положением элемента в матрице <math>A</math> и его положением в массиве: <math>a_{ij}</math>
 +
хранится компонентой <math>AN (i, j - i + \beta + 1)</math>.
  
 
== Математическое описание алгоритма ==
 
== Математическое описание алгоритма ==

Версия 16:48, 9 октября 2016

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

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

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

и другие.

3 Литература

<references \>

  1. С.Писсанецки. Технология разреженных матриц. - М.: Мир, 1988