Dense matrix-vector multiplication
Основные авторы описания: А.В.Фролов, Вад.В.Воеводин (раздел 2.2), А.М.Теплов (раздел 2.4)
Contents
- 1 Описание свойств и структуры алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Описание схемы реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Описание ресурса параллелизма алгоритма
- 1.9 Описание входных и выходных данных
- 1.10 Свойства алгоритма
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]m[/math]) вычислений скалярных произведений строк матрицы [math]A[/math] вектор [math]x[/math]:
- [math] \sum_{j = 1}^{n} a_{ij} x_{j}[/math]
в режиме накопления или без него, в зависимости от требований задачи.
1.4 Макроструктура алгоритма
Как уже записано в описании ядра алгоритма, основную часть умножения матрицы на вектор составляют множественные (всего [math]m[/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 Информационный граф
Опишем граф алгоритма как аналитически, так и в виде рисунка.
Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция [math]a+bc[/math].
Естественно введённые координаты области таковы:
- [math]i[/math] — меняется в диапазоне от [math]1[/math] до [math]m[/math], принимая все целочисленные значения;
- [math]j[/math] — меняется в диапазоне от [math]1[/math] до [math]n[/math], принимая все целочисленные значения.
Аргументы операции следующие:
- [math]a[/math]:
- при [math]j = 1[/math] константа [math]0.[/math];
- при [math]j \gt 1[/math] — результат срабатывания операции, соответствующей вершине с координатами [math]i, j-1[/math];
- [math]b[/math] — элемент входных данных, а именно [math]a_{ij}[/math];
- [math]c[/math] - элемент входных данных [math]x_{j}[/math];
Результат срабатывания операции является:
- при [math]j \lt n[/math] - промежуточным данным алгоритма;
- при [math]j = n[/math] - выходным данным.
Описанный граф можно посмотреть на рисунке, выполненном для случая [math]m = 4, n = 5[/math]. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора [math]x[/math], подача элементов матрицы [math]A[/math], идущая во все вершины, на рисунке не представлена.
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 Свойства алгоритма
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является линейным (отношение квадратической или билинейной к линейной).
При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь константа.
При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.
