Равномерная норма вектора, вещественная версия, последовательный вариант

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

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

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

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

Исходные данные: одномерный массив [math]\displaystyle{ n }[/math] чисел. Вычисляемые данные: максимум абсолютной величины элементов массива. Формулы метода: для вектора [math]\displaystyle{ \vec{a} }[/math] из [math]\displaystyle{ n }[/math] элементов вычисляется выражение [math]\displaystyle{ \max\limits_i |a_i| }[/math].

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

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

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

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

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

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

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

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

Для вычисления равномерной нормы массива, состоящего из [math]\displaystyle{ N }[/math] элементов, количество операций вычисления модуля неизменно и равно [math]\displaystyle{ N }[/math], а количество операций вычисления максимума равно [math]\displaystyle{ N-1 }[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.

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

Опишем граф алгоритма в виде рисунка. Изображен граф для случая [math]\displaystyle{ n = 6 }[/math].

Вычисление с нормы вектора с экономией вызовов функции максимума

Однако следует отметить, что в большинстве случаев программисты не экономят на одном вызове функции максимума, а инициализируют начальное значение переменной нулём. В этом случае граф становится таким, как на втором рисунке ([math]\displaystyle{ n = 6 }[/math]).

Упрощенная реализация вычисления нормы вектора

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

Последовательный вариант вычисления равномерной нормы массива, несмотря на название, имеет ресурс параллелизма степени 2. Дело в том, что, если рассматривать отдельно вычисления модуля и максимума, то видно, что при выполнении очередного выбора максимума «подготовительное» отбрасывание знака к следующему можно выполнить заранее. В принципе, можно, если использовать дополнительную память для хранения всех модулей, вообще выполнить все отбрасывания знаков параллельно, а потом последовательно выполнить выбор максимального из вычисленных абсолютных величин. Таким образом, в получившемся алгоритме высота параллельной формы будет равна 1 операции вычисления функции ABS плюс [math]\displaystyle{ N-1 }[/math] операций выбора максимума. В таком виде алгоритм должен быть отнесён к алгоритмам линейной сложности как по высоте, так и по ширине параллельной формы. Однако если мы будем последовательно выполнять и вычисления абсолютных величин, то ширина параллельной формы может быть уменьшена до 2, что даёт нам постоянную сложность по ширине параллельной формы.

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

Входные данные: массив [math]\displaystyle{ a }[/math] (элементы [math]\displaystyle{ a_i }[/math]).

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

Объём входных данных: [math]\displaystyle{ n }[/math].

Выходные данные: максимум модулей элементов массива.

Объём выходных данных: один скаляр.

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

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

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

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

В простейшем (входные данные — вектор) варианте на Фортране можно записать так:

	NORMX = ABS(A(1))
	DO I = 2,N
		NORMX = MAX( NORMX, ABS(A(I)) )
	END DO

В варианте с «холостым» выбором максимума запись такая:

	NORMX = 0.
	DO I = 1,N
		NORMX = MAX( NORMX, ABS(A(I)) )
	END DO

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

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