Приложение 10

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

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

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

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

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

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

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

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

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

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

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

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

$\sum_{j = 1}^{n} a_{ij} x_{j}$

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

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

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

$\sum_{j = 1}^{n} a_{ij} x_{j}$

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

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

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

$y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}$

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

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

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

• по $n^2$ умножений и сложений.

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

• по $mn$ умножений и сложений.

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

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

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

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

Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция $a+bc$.

Естественно введённые координаты области таковы:

• $i$ — меняется в диапазоне от $1$ до $m$, принимая все целочисленные значения;
• $j$ — меняется в диапазоне от $1$ до $n$, принимая все целочисленные значения.

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

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

Результат срабатывания операции является:

• при $j \lt n$ - промежуточным данным алгоритма;
• при $j = n$ - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая $m = 4, n = 5$. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора $x$, подача элементов матрицы $A$, идущая во все вершины, на рисунке не представлена.

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

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

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

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

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

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

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

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

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

Объём входных данных: $mn+n$ .

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

Объём выходных данных: $m$.

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

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

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

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