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

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

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

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

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

Исходные данные: два одномерных массива <math>n</math> чисел.

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

Формулы метода: для векторов <math>\vec{x}</math> и <math>\vec{b}</math> размерности <math>n</math> и <math>m</math>, соответственно, вычисляются суммы 
:<math>b_i + \sum_{j = 1}^n a_{ij} x_j</math>
для всех <math>i</math> от <math>1</math> до <math>m</math>.

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

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

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

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

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

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

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

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

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

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

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

[[file:matrix-vector product plus vector (dense matrix).png|center|thumb|400px]][[file:matrix-vector product plus vector (dense matrix) in_out.png|center|thumb|400px]]

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

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

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

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

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

Объём входных данных: <nowiki/><math>m n + m + n</math>. 

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

Объём выходных данных: <nowiki/><math>m</math>.

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

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

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

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

В простейшем варианте на Фортране можно записать так:
<source lang="fortran">
	DO I = 1, M
	DO J = 1, N
		B(I) = B(I) + A(I,J)* X(J)
	END DO
	END DO
</source>

=== Описание локальности данных и вычислений ===
==== Описание локальности алгоритма ====
==== Описание локальности реализации алгоритма ====
===== Описание структуры обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
===== Анализ на основе теста Apex-Map =====
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Описание масштабируемости алгоритма ====
==== Описание масштабируемости реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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