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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	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

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

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