Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 61: Строка 61:
 
=== Информационный граф ===
 
=== Информационный граф ===
  
Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.  
+
Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.
 
 
  
 +
[[Файл:File.png|500px|thumb|left|граф последовательного умножения плотной матрицы на вектор]]
  
 
=== Описание ресурса параллелизма алгоритма ===
 
=== Описание ресурса параллелизма алгоритма ===

Версия 09:58, 18 сентября 2014

Содержание

1 Описание свойств и структуры алгоритма

1.1 Словесное описание алгоритма

Умножение матрицы на вектор - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов. Здесь мы рассмотрим умножение [math]y = Ax[/math] плотной неособенной матрицы на вектор (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства опереации сложения.

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

Исходные данные: плотная матрица [math]A[/math] (элементы [math]a_{ij}[/math]), умножаемый на неё вектор [math]x[/math] (элементы [math]x_{i}[/math]).

Вычисляемые данные: вектор решения [math]y[/math] (элементы [math]y_{i}[/math]).

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

[math] \begin{align} y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}, \quad i \in [1, m]. \end{align} [/math]

Существует также блочная версия метода, однако в данном описании разобран только точечный метод.

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

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

[math] \sum_{j = 1}^{n} a_{ij} x_{j}[/math]

в режиме накопления или без него, в зависимости от требований задачи.

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

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

[math] \sum_{j = 1}^{n} a_{ij} x_{j}[/math]

в режиме накопления или без него.

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

Для всех [math]i[/math] от [math]1[/math] до [math]m[/math] по возрастанию выполняются

[math]y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}[/math]

Особо отметим, что вычисления сумм вида [math]\sum_{j = 1}^{n} a_{ij} x_{j}[/math] производят в режиме накопления прибавлением к текущему (временному) значению вычисляемой компоненты вектора [math]y_{i}[/math] произведений [math]a_{ij} x_{j}[/math] для [math]j[/math] от [math]1[/math] до [math]n[/math], c возрастанием [math]j[/math], вначале все компоненты инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.

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

Для умножения квадратной матрицы на вектор порядка [math]n[/math] (т.е. при [math]m=n[/math]) в последовательном (наиболее быстром) варианте требуется:

  • по [math]n^2[/math] умножений и сложений (вычитаний).

Для умножения матрицы размером [math]m[/math] строк на [math]n[/math] столбцов на вектор порядка [math]n[/math] в последовательном (наиболее быстром) варианте требуется:

  • по [math]mn[/math] умножений и сложений (вычитаний).

При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матрицы на вектор.

При классификации по последовательной сложности, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам с квадратической сложностью (в случае неквадратной матрицы - с билинейной).

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

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

граф последовательного умножения плотной матрицы на вектор

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

  • по [math]n[/math] ярусов умножений и сложений (в каждом из ярусов — [math]n[/math] операций).

Для умножения матрицы размером [math]m[/math] строк на [math]n[/math] столбцов на вектор порядка [math]n[/math] в последовательном (наиболее быстром) варианте требуется:

  • по [math]n[/math] ярусов умножений и сложений (в каждом из ярусов — [math]m[/math] операций).

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

При классификации по высоте ЯПФ, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам с линейной сложностью. При классификации по ширине ЯПФ его сложность также будет линейной.

1.9 Описание входных и выходных данных

Входные данные: матрица [math]A[/math] (элементы [math]a_{ij}[/math]), вектор [math]x[/math] (элементы [math]x_{i}[/math]).

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

Выходные данные: вектор [math]y[/math] (элементы [math]y_{i}[/math]).

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

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

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

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

При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

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

В простейшем варианте алгоритм умножения матрицы на вектор на Фортране можно записать так:

         
	DO  I = 1, M
		S = 0.
		DO  J = 1, N
			S = S - DPROD(A(I,J), X(J))
		END DO	
	        Y(I) = S
	END DO

При этом для реализации режима накопления переменная [math]S[/math] должна быть двойной точности.

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

2.2.1 Описание локальности алгоритма

2.2.2 Описание локальности реализации алгоритма

2.2.2.1 Описание структуры обращений в память и качественная оценка локальности
2.2.2.2 Количественная оценка локальности

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

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

2.4.1 Описание масштабируемости алгоритма

2.4.2 Описание масштабируемости реализации алгоритма

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

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

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

3 Литература

  1. В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.