|
|
| (не показаны 2 промежуточные версии этого же участника) |
| Строка 1: |
Строка 1: |
| = Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант) =
| |
|
| |
|
| == Свойства и структура алгоритма ==
| |
|
| |
| === Общее описание алгоритма ===
| |
|
| |
| '''Умножение матрицы на вектор''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
| |
| Здесь мы рассмотрим умножение <math>y = Ax</math> плотной неособенной матрицы на вектор (последовательный вещественный вариант)<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>, то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения.
| |
|
| |
| === Математическое описание алгоритма ===
| |
|
| |
| Исходные данные: плотная матрица <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>
| |
|
| |
| Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
| |
|
| |
| === Вычислительное ядро алгоритма ===
| |
|
| |
| Вычислительное ядро умножения матрицы на вектор можно составить из множественных (всего их <math>m</math>) вычислений скалярных произведений строк матрицы <math>A</math> вектор <math>x</math>:
| |
|
| |
| :<math> \sum_{j = 1}^{n} a_{ij} x_{j}</math>
| |
|
| |
| в режиме накопления или без него, в зависимости от требований задачи.
| |
|
| |
| === Макроструктура алгоритма ===
| |
|
| |
| Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матрицы на вектор составляют множественные (всего <math>m</math>) вычисления скалярных произведений строк матрицы <math>A</math> вектор <math>x</math>
| |
|
| |
| :<math> \sum_{j = 1}^{n} a_{ij} x_{j}</math>
| |
|
| |
| в режиме накопления или без него.
| |
|
| |
| === Схема реализации последовательного алгоритма ===
| |
|
| |
| Для всех <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>, вначале все компоненты инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.
| |
|
| |
| === Последовательная сложность алгоритма ===
| |
|
| |
| Для умножения квадратной матрицы на вектор порядка <math>n</math> (т.е. при <math>m=n</math>) в последовательном (наиболее быстром) варианте требуется:
| |
|
| |
| * по <math>n^2</math> умножений и сложений.
| |
|
| |
| Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:
| |
|
| |
| * по <math>mn</math> умножений и сложений.
| |
|
| |
| При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матрицы на вектор.
| |
|
| |
| При классификации по последовательной сложности, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам ''с квадратической сложностью'' (в случае неквадратной матрицы - с ''билинейной'').
| |
|
| |
| === Информационный граф ===
| |
|
| |
| Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.
| |
|
| |
| [[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]
| |
|
| |
| Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <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 > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
| |
| *<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
| |
| *<math>c</math> - элемент входных данных <math>x_{j}</math>;
| |
|
| |
| Результат срабатывания операции является:
| |
| * при <math>j < n</math> - ''промежуточным данным'' алгоритма;
| |
| * при <math>j = n</math> - выходным данным.
| |
|
| |
| Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.
| |
|
| |
| === Ресурс параллелизма алгоритма ===
| |
|
| |
| Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:
| |
|
| |
| * по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).
| |
|
| |
| Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:
| |
|
| |
| * по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).
| |
|
| |
| При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.
| |
|
| |
| При классификации по высоте ЯПФ, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''линейной''.
| |
|
| |
| === Входные и выходные данные алгоритма ===
| |
|
| |
| '''Входные данные''': матрица <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>.
| |
|
| |
| === Свойства алгоритма ===
| |
|
| |
| Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).
| |
|
| |
| При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.
| |
|
| |
| При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.
| |
|
| |
| == Литература ==
| |
| <references />
| |