Сумма вектора и произведения матрицы на другой вектор, вещественная версия, последовательный вариант, плотная матрица

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

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

Сумма вектора и произведения матрицы на другой вектор используется в качестве одной из базовых операций в широком круге методов. При этом сумма вектора и произведения матрицы на другой вектор используется как в версии для собственно векторов (одномерных массивов размеров $n$ и $m$), так и в версии для линейных подмножеств массивов большей размерности. Последняя отличается от первой тем, что соответствующая подпрограмма получает, кроме стартовых адресов векторов и массива, также и параметры смещения следующих элементов относительно предыдущих (в первой версии эти смещения равны 1). Здесь мы рассматриваем только вещественную арифметику.

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

Исходные данные: два одномерных массива $n$ чисел.

Вычисляемые данные: сумма попарных произведений элементов массива.

Формулы метода: для векторов $\vec{x}$ и $\vec{b}$ размерности $n$ и $m$, соответственно, вычисляются суммы

$b_i + \sum_{j = 1}^n a_{ij} x_j$

для всех $i$ от $1$ до $m$.

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

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

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

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

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

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

Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов), при этом суммировать начинают сразу с элементом вектора $\vec{b}$.

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

Для вычисления скалярного сумма вектора и произведения матрицы, количество операций умножения неизменно и равно $m n$, и количество операций сложения тоже равно $m n$. Поэтому алгоритм, в случае если размеры векторов совпадают, должен быть отнесён к алгоритмам квадратичной сложности по количеству последовательных операций.

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

Опишем граф алгоритма в виде рисунка. Пример приведён для $m = 4$, $n = 7$. Вершине графа соответствует составная операция умножения двух чисел с последующим сложением с третьим числом.

Сумма вектора и произведения матрицы на вектор с отображением только выходных данных

Сумма вектора и произведения матрицы на вектор с отображением входных и выходных данных

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

Последовательный вариант вычисления суммы вектора и произведения матрицы на другой вектор, имеет ресурс параллелизма степени $m$. Таким образом, в получившемся алгоритме высота параллельной формы будет равна $n$ операций умножения плюс $n$ операций сложения. В таком виде алгоритм, если мы предполагаем равенство размеров векторов, должен быть отнесён к алгоритмам линейной сложности как по высоте, так и по ширине параллельной формы.

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

Входные данные: массивы $\vec{x}$ (элементы $x_i$), $\vec{b}$ (элементы $b_i$), матрица $A$ (элементы $a_{ij}$).

Дополнительные ограничения: отсутствуют.

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

Выходные данные: сумма произведения матрицы $A$ и вектора $\vec{x}$ с вектором $\vec{b}$.

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

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, равно $m$. При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 2 (количество входных и выходных данных по порядку такое же, как у операций). При этом алгоритм полностью детерминирован. Дуги информационного графа локальны.

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

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

В простейшем варианте на Фортране можно записать так:

	DO I = 1, M
	DO J = 1, N
		B(I) = B(I) + A(I,J)* X(J)
	END DO
	END DO

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

Помимо выписанных выше простейших реализаций, существуют более сложные коды, реализующие тот же алгоритм. Это объясняется тем, что порой чисто программистскими приёмами оптимизируют работу с регистрами, с кэшем и т. п. В частности, даже в Линпаке есть разные реализации кода. Большинство их сводится к сведению одинарного цикла длиной $n$ к двойному циклу либо к одинарному с меньшим числом итераций, но более длинной операцией в теле цикла. Между тем, разбиения циклов на группы для вычислений частных сумм могут быть полезны и для лучшего использования кэша на отдельных узлах, когда одинаковых выражений вычисляется сразу много и распараллеливание программы состоит в их распределении между узлами.