Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
 
{{algorithm
 
{{algorithm
 
| name              = Умножение разреженной матрицы на вектор
 
| name              = Умножение разреженной матрицы на вектор
−
| serial_complexity = <math>O(nz)</math>
+
| serial_complexity = <math>O(l)</math>
−
| pf_height        = <math>O(n)</math>
+
| pf_height        = <math>O(m)</math>
 
| pf_width          = <math>O(n)</math>
 
| pf_width          = <math>O(n)</math>
−
| input_data        = <math>2nz+m+n+1</math>
+
| input_data        = <math>2l+m+n+1</math>
 
| output_data      = <math>n</math>
 
| output_data      = <math>n</math>
 
}}
 
}}
Строка 75: Строка 75:
 
Формулы метода:
 
Формулы метода:
  
−
<math>c_{i} = \sum\limits_{k = 1}^{nz_{i}} a_{i,j=j(k)}b_{j=j(k)}</math>,
+
<math>c_{i} = \sum\limits_{k = 1}^{l_{i}} a_{i,j=j(k)}b_{j=j(k)}</math>,
  
−
где <math>nz_{i}</math> - количество ненулевых элементов строки <math>i</math> матрицы <math>A</math>, <math>j(k)</math> - индекс <math>k</math>-го ненулевого элемента матрицы <math>A</math>.
+
где <math>l_{i}</math> - количество ненулевых элементов строки <math>i</math> матрицы <math>A</math>, <math>j(k)</math> - индекс <math>k</math>-го ненулевого элемента матрицы <math>A</math>.
  
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==
 
Вычислительное ядро последовательной версии умножения разреженной матрицы на вектор можно составить из множественных (всего их <math>n</math>) вычислений скалярных произведений строк матрицы:
 
Вычислительное ядро последовательной версии умножения разреженной матрицы на вектор можно составить из множественных (всего их <math>n</math>) вычислений скалярных произведений строк матрицы:
  
−
<math>c_{i} = \sum\limits_{k = 1}^{nz_{i}} a_{i,j=j(k)}b_{j=j(k)}</math>.
+
<math>c_{i} = \sum\limits_{k = 1}^{l_{i}} a_{i,j=j(k)}b_{j=j(k)}</math>.
  
 
== Макроструктура алгоритма ==
 
== Макроструктура алгоритма ==
Строка 88: Строка 88:
 
Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют множественные (всего <math>n</math>) вычисления сумм:
 
Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют множественные (всего <math>n</math>) вычисления сумм:
  
−
<math>c_{i} = \sum\limits_{k = 1}^{nz_{i}} a_{i,j=j(k)}b_{j=j(k)}</math>.
+
<math>c_{i} = \sum\limits_{k = 1}^{l_{i}} a_{i,j=j(k)}b_{j=j(k)}</math>.
  
 
== Схема реализации последовательного алгоритма ==
 
== Схема реализации последовательного алгоритма ==
Строка 102: Строка 102:
 
После этого (если <math>i \le n</math>) происходит переход к шагу 1 с бо́льшим <math>i</math>.
 
После этого (если <math>i \le n</math>) происходит переход к шагу 1 с бо́льшим <math>i</math>.
  
−
=== Последовательная сложность алгоритма ===
+
== Последовательная сложность алгоритма ==
  
 
Для умножения разреженной матрицы общего вида, хранимой в форме '''RR(C)U''', размером <math>n \times m</math> на заполненный вектор <math>m \times 1</math> в последовательном (наиболее быстром) варианте требуется:
 
Для умножения разреженной матрицы общего вида, хранимой в форме '''RR(C)U''', размером <math>n \times m</math> на заполненный вектор <math>m \times 1</math> в последовательном (наиболее быстром) варианте требуется:
  
−
* <math>nz</math> сложений,
+
* <math>l</math> сложений,
−
* <math>nz</math> умножений.
+
* <math>l</math> умножений.
  
 
Умножения и сложения составляют ''основную часть алгоритма''.
 
Умножения и сложения составляют ''основную часть алгоритма''.
  
−
При классификации по последовательной сложности, таким образом, алгоритм умножения разреженной матрицы на вектор относится к алгоритмам <math>O(nz)</math>.
+
При классификации по последовательной сложности, таким образом, алгоритм умножения разреженной матрицы на вектор относится к алгоритмам <math>O(l)</math>.
  
 
== Информационный граф ==
 
== Информационный граф ==
Строка 136: Строка 136:
 
Для умножения разреженной матрицы общего вида, хранимой в форме '''RR(C)U''', размером <math>n \times m</math> на заполненный вектор <math>m \times 1</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:
 
Для умножения разреженной матрицы общего вида, хранимой в форме '''RR(C)U''', размером <math>n \times m</math> на заполненный вектор <math>m \times 1</math> в параллельном варианте требуется последовательно выполнить следующие ярусы:
  
−
*
+
* Не более чем <math>m</math> сложений и умножений (<math>n</math> вычислений в каждом из ярусов)
−
*
+
 
 +
При классификации по высоте ЯПФ, таким образом, алгоритм умножения разреженной матрицы на вектор относится к алгоритмам со сложностью <math>O(m)</math>. При классификации по ширине ЯПФ его сложность будет <math>O(n)</math>.
  
 
== Входные и выходные данные алгоритма ==
 
== Входные и выходные данные алгоритма ==
 +
 +
'''Входные данные''': разреженная матрица общего вида <math>A</math> с элементами <math>a_{ij}</math> (<math>i = 1,...,n</math> и <math>j = 1,...,m</math>), хранимая в форме '''RR(C)U''' посредством массивов <math>IA</math>, <math>JA</math>, <math>AN</math>. Заполненный вектор-столбец <math>b</math> с элементами <math>b_{j}</math> (<math>j =1,...,m</math>).
 +
 +
'''Объём входных данных''': <math>2l+m+n+1</math>, где <math>l</math> - количество ненулевых элементов в матрице <math>A</math>.
 +
 +
'''Выходные данные''': заполненный вектор-столбец <math>c</math> с элементами <math>c_{i}</math> (<math>i = 1,...,n</math>).
 +
 +
'''Объём выходных данных''': <math>n</math>.
  
 
== Свойства алгоритма ==
 
== Свойства алгоритма ==
 +
 +
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейной''.
 +
 +
При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – ''константа''.
  
 
= Программная реализация алгоритма =
 
= Программная реализация алгоритма =

Версия 20:09, 23 октября 2016


Умножение разреженной матрицы на вектор
Последовательный алгоритм
Последовательная сложность [math]O(l)[/math]
Объём входных данных [math]2l+m+n+1[/math]
Объём выходных данных [math]n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O(m)[/math]
Ширина ярусно-параллельной формы [math]O(n)[/math]

Выполнила: И.В. Близнякова (611 группа).

Содержание

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

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

Разрежённая матрица — это матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевые, матрица считается плотной.[1]

Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов:

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

1.1.1 Хранение разреженной матрицы

1.1.1.1 Формат RR(C)O

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

Рассмотрим матрицу [math]A[/math]:

[math]\begin{pmatrix} 0 & 0 & 0 & 2 & 0 \\ 1 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 6 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 \\ \end{pmatrix}[/math],

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

  IA = [ 1 2 4 4 5 6 ]
  JA = [ 4 1 3 2 3 ]
  AN = [ 2 1 3 6 4 ]

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

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

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

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

1.1.1.2 Формат RR(C)U

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

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

  IA = [ 1 2 4 4 5 6 ]
  JA = [ 4 3 1 2 3 ]
  AN = [ 2 1 3 6 4 ]

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

1.1.1.3 Замечания

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

  1. Очевидно, что представление матрицы в формате RR(C)O так же является и представлением в формате RR(C)U, но не наоборот.
  2. Из представления матрицы в формате RR(C) нельзя получить информацию о точном количестве столбцов исходной матрицы.
  3. Целесообразно (в вопросе экономии памяти) использовать представления RR(C) в случае, если матрица содержит значительное число нулевых элементов.

1.1.2 Умножение разреженной матрицы на вектор

Умножение разреженной матрицы на вектор - важным приложением этих алгоритмов является вычисление векторов Ланцоша, необходимое при итерационном решении линейных уравнений методом сопряженных градиентов, а также при вычислении собственных значений и собственных векторов матрицы. Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матричная операция - это повторное умножение матрицы на последовательность заполненных векторов; сама матрица не меняется.

Мы рассмотрим умножение разреженной матрицы общего вида, хранимой в форме RR(C)U посредством массивов [math]IA[/math], [math]JA[/math], [math]AN[/math] на заполненный вектор-столбец.

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

Исходные данные: разреженная матрица общего вида [math]A[/math] с элементами [math]a_{ij}[/math] ([math]i = 1,...,n[/math] и [math]j = 1,...,m[/math]). Заполненный вектор-столбец [math]b[/math] с элементами [math]b_{j}[/math] ([math]j =1,...,m[/math]).

Вычисляемые данные: заполненный вектор-столбец [math]c[/math] с элементами [math]c_{i}[/math] ([math]i = 1,...,n[/math]).

Формулы метода:

[math]c_{i} = \sum\limits_{k = 1}^{l_{i}} a_{i,j=j(k)}b_{j=j(k)}[/math],

где [math]l_{i}[/math] - количество ненулевых элементов строки [math]i[/math] матрицы [math]A[/math], [math]j(k)[/math] - индекс [math]k[/math]-го ненулевого элемента матрицы [math]A[/math].

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

Вычислительное ядро последовательной версии умножения разреженной матрицы на вектор можно составить из множественных (всего их [math]n[/math]) вычислений скалярных произведений строк матрицы:

[math]c_{i} = \sum\limits_{k = 1}^{l_{i}} a_{i,j=j(k)}b_{j=j(k)}[/math].

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

Как записано и в описании ядра алгоритма, основную часть метода составляют множественные (всего [math]n[/math]) вычисления сумм:

[math]c_{i} = \sum\limits_{k = 1}^{l_{i}} a_{i,j=j(k)}b_{j=j(k)}[/math].

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

Далее предполагаем, что разреженная матрица общего вида [math]A[/math] хранится в форме RR(C)U посредством массивов [math]IA[/math], [math]JA[/math], [math]AN[/math]. Последовательность исполнения метода следующая:

Выполнять для [math]i[/math] от [math]1[/math] до [math]n[/math]

  1. [math]c_{i} = 0[/math]
  2. [math]IAA = IA[i][/math]
  3. [math]IAB = IA[i + 1] - 1[/math]
  4. [math]c_{i} = \sum\limits_{k = IAA}^{IAB} AN(k)b_{JA(k)}[/math].

После этого (если [math]i \le n[/math]) происходит переход к шагу 1 с бо́льшим [math]i[/math].

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

Для умножения разреженной матрицы общего вида, хранимой в форме RR(C)U, размером [math]n \times m[/math] на заполненный вектор [math]m \times 1[/math] в последовательном (наиболее быстром) варианте требуется:

  • [math]l[/math] сложений,
  • [math]l[/math] умножений.

Умножения и сложения составляют основную часть алгоритма.

При классификации по последовательной сложности, таким образом, алгоритм умножения разреженной матрицы на вектор относится к алгоритмам [math]O(l)[/math].

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

Опишем граф алгоритма[2][3][4] как аналитически, так и в виде рисунка.

Граф алгоритма состоит из двух групп вершин, расположенных в целочисленных узлах двух областей одной размерности.

Первая группа вершин расположена в двумерной области, соответствующая ей операция вычисляет функцию [math]a+b[/math]. Естественно введённые координаты области таковы:

  • [math]i[/math] — меняется в диапазоне от [math]1[/math] до [math]n-1[/math], принимая все целочисленные значения;
  • [math]j[/math] — меняется в диапазоне от [math]i+1[/math] до [math]n[/math], принимая все целочисленные значения.

Аргументы операции следующие:

  • [math]a[/math]:
    • при [math]i = 1[/math] — элементы входных данных, а именно [math]a_{j1}[/math];
    • при [math]i \gt 1[/math] — результат срабатывания операции, соответствующей вершине из третьей группы, с координатами [math]i - 1, j, i - 1[/math];
  • [math]b[/math] — результат срабатывания операции, соответствующей вершине из первой группы, с координатой [math]i[/math].

Результат срабатывания операции является выходным данным [math]c_{i}[/math].

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

Для умножения разреженной матрицы общего вида, хранимой в форме RR(C)U, размером [math]n \times m[/math] на заполненный вектор [math]m \times 1[/math] в параллельном варианте требуется последовательно выполнить следующие ярусы:

  • Не более чем [math]m[/math] сложений и умножений ([math]n[/math] вычислений в каждом из ярусов)

При классификации по высоте ЯПФ, таким образом, алгоритм умножения разреженной матрицы на вектор относится к алгоритмам со сложностью [math]O(m)[/math]. При классификации по ширине ЯПФ его сложность будет [math]O(n)[/math].

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

Входные данные: разреженная матрица общего вида [math]A[/math] с элементами [math]a_{ij}[/math] ([math]i = 1,...,n[/math] и [math]j = 1,...,m[/math]), хранимая в форме RR(C)U посредством массивов [math]IA[/math], [math]JA[/math], [math]AN[/math]. Заполненный вектор-столбец [math]b[/math] с элементами [math]b_{j}[/math] ([math]j =1,...,m[/math]).

Объём входных данных: [math]2l+m+n+1[/math], где [math]l[/math] - количество ненулевых элементов в матрице [math]A[/math].

Выходные данные: заполненный вектор-столбец [math]c[/math] с элементами [math]c_{i}[/math] ([math]i = 1,...,n[/math]).

Объём выходных данных: [math]n[/math].

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является линейной.

При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – константа.

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

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

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

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

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

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

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

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

3 Литература

  1. ↑ С.Писсанецки. Технология разреженных матриц. - М.: Мир, 1988. 12 с.
  2. ↑ Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.
  3. ↑ Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.
  4. ↑ Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Blizn/Хранение_ненулевых_элементов_разреженной_матрицы._Умножение_разреженной_матрицы_на_вектор.&oldid=13538