Участник:KibAndrey/Ортогонализация Грама-Шмидта

Ортогонализация Грама-Шмидта
Последовательный алгоритм
Последовательная сложность	[math]O\left(n^3\right)[/math]
Объём входных данных	[math][/math]
Объём выходных данных	[math][/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math][/math]
Ширина ярусно-параллельной формы	[math][/math]

Основные авторы описания: А.В.Кибанов, Т.З.Аджиева.

1 ЧАСТЬ. Свойства и структура алгоритма

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

Представим граф алгоритма с помощью текстового описания, а также с помощью изображения.

Все вершины графа можно разбить на шесть групп, каждой из которых соответствует вид исполняемой операции. Каждая вершина расположена в точках с целочисленными координатами, в пространствах с числом измерений от [math]1[/math] до [math]4[/math] Дадим описание каждой из групп.

Первая группа - вершины, которым соответствует операция возведение в квадрат. На графе они располагаются в двумерной области. [math]i[/math] изменяется от [math]1[/math] до [math]n[/math], [math]k[/math] изменяется от [math]1[/math] до [math]m[/math].

Значениями аргументов для этих функций являются:

• при [math]i = 1[/math] - входные данные [math]a_{1k}[/math];
• при [math]i \gt 1[/math] - результат выполнения функции в вершине шестой группы с координатами [math]i-1,1,k[/math]

Результат является промежуточным данным алгоритма.

Вторая группа - вершины соответствующие операции сложения, которые проще разбить на две подгруппы, соответствующие четным и нечетным индексам. Они располагаются в четырехмерной области, [math]i[/math] изменяется от [math]1[/math] до [math]2n-1[/math], [math]j[/math] равно [math]1[/math] для нечетных [math]i[/math] и изменяется от [math]2[/math] до [math]n+1-\lceil{\dfrac{i}{2}}\rceil[/math] для четных [math]i[/math], [math]k[/math] изменяется от [math]1[/math] до [math]\lceil{\dfrac{m}{2^{i}}}\rceil[/math], [math]t[/math] изменяется от [math]1[/math] до [math]T = \lceil{\log_{2}(k)}\rceil+1[/math].

Значениями аргументов для этих функций являются:

• при [math]j = 1, t = 1[/math] - результат выполнения функций в вершинах первой группы с координатами [math](i+1)/2,1,2*k[/math] и [math](i+1)/2,1,2*k - 1[/math] ;
• при [math]j \gt 1, t = 1[/math] - результат выполнения функции в вершинах пятой группы с координатами [math]i/2,j-1,2*k[/math] и [math]i,j-1,2*k - 1[/math];
• при [math]t \gt 1[/math] - результат выполнения функций в вершинах второй группы с координатами [math]i,j,2*k,t-1[/math] и [math]i,j,2*k-1,t-1[/math] (это точно верно для случаев k являющихся степенью двойки. Для остальных вариантов аргументом может являться результат выполнения функций в вершинах второй группы с последней координатой меньшей чем [math]t-1[/math]).

Результат является промежуточным данным алгоритма.

Третья группа - вершины, которым соответствует операция SQRT извлечения квадратного корня. Они расположены в одномерной области, [math]i [/math]изменяется от [math]1[/math] до [math]n[/math]. Значением аргумента для этих функций является результат выполнения функции в вершине второй группы, с координатами [math]i,1,1,T[/math]

Результат является промежуточным данным алгоритма

Четвертая группа - вершины, которым соответствует операция деления. Располагаются в двумерной области, [math]i[/math] изменяется от [math]1[/math] до [math]n[/math], [math]k[/math] изменяется от [math]1[/math] до [math]m[/math]. Значениями аргументов для этих функций являются:

• делимое:
  • при [math]i = 1[/math] - входные данные [math]a_{1k}[/math];
  • при [math]i \gt 1[/math] - результат выполнения функции в вершине шестой группы с координатами [math]i-1,1,k[/math];
• делитель - результат выполнения функции в вершине третьей группы с координатой [math]i[/math]

Результат является выходным данным алгоритма [math]e_{ik}[/math]

Пятая группа - вершины, которым соответствует операция [math]a*b[/math]. Располагаются в трехмерной области, [math]i[/math] изменяется от [math]1[/math] до [math]n-1[/math], [math]j[/math] изменяется от [math]1[/math] до [math]n-i\lt math\gt , \lt math\gt k[/math] изменяется от [math]1[/math] до [math]m[/math]. Значениями аргументов для этих функций являются:

• [math]a[/math]:
  • при [math]i = 1[/math] - входные данные [math]a_{1+j,k}[/math];
  • при [math]i \gt 1[/math] - результат выполнения функции в вершине шестой группы с координатами [math]i-1,j+1,k[/math];
• [math]b[/math] - результат выполнения функции в вершине четвертой группы с координатой [math]i[/math]

Результат является промежуточным данным алгоритма

Шестая группа - вершины которые соответствуют операции [math]a - b*c[/math]. Располагаются в трехмерной области, [math]i[/math] изменяется от [math]1[/math] до [math]n-1[/math], [math]j[/math] изменяется от [math]1[/math] до [math]n-i[/math], [math]k[/math] изменяется от [math]1[/math] до [math]m[/math]. Значениями аргументов для этих функций являются:

• [math]a[/math]:
  • при [math]i = 1[/math] - входные данные [math]a_{1+j,k}[/math];
  • при [math]i \gt 1[/math] - результат выполнения функции в вершине шестой группы с координатами [math]i-1,j+1,k[/math];
• [math]b[/math] - результат выполнения функции в вершине второй группы, с координатами [math]i,j+1,1,T[/math]
• [math]c[/math] - результат выполнения функции в вершине четвертой группы с координатой [math]i[/math]

Результат является промежуточным данным алгоритма

Описанный граф для случая [math]n = 3[/math], [math]k = 4[/math] изображен на рисунке. Каждая группа вершин отличается цветом и буквенным обозначением. "S" - первая группа, "+" - вторая группа, "SQ" - третья группа, "Div" - четвертая группа, "M" - пятая группа, "f" - шестая группа. Квадратные метки "In" и "out" обозначают передачу входных и выходных данных соответственно. Поскольку координаты вдоль оси [math]k[/math] в большинстве случаев соответствуют номеру компоненты рассматриваемого вектора, для удобства визуализации изменение этой координаты зафиксировано локально в каждой подгруппе вершин с одинаковыми координатами [math]i,j[/math] параллельно оси [math]j[/math].

Рисунок 1. Граф алгоритма с отображением входных и выходных данных

1.6 Ресурс параллелизма алгоритма

Для построения ортонормированного базиса методом Грама-Шмидта необходимо выполнить следующие ярусы операций:

• [math]n[/math] ярусов вычисления квадратов числа (по [math]k[/math] операций на каждом)
• [math](2n-1)*(\lceil{\log_{2}(k)}\rceil+1)[/math] ярусов суммирования (от [math]1[/math] до [math](n-1)*\dfrac{k}{2}[/math] операций на каждом)
• [math]n[/math] ярусов вычисления квадратного корня (по одной операции на каждом)
• [math]n[/math] ярусов деления( по [math]k[/math] операций на каждом)
• [math]n-1[/math] ярус умножения пары чисел (от [math]1[/math] до [math]k*(n-1)[/math] операций на каждом)
• [math]n-1[/math] ярус умножения/вычитания чисел (от [math]k[/math] до [math]k*(n-1)[/math] операций на каждом)

В этом случае сложность алгоритма при классификации по высоте ЯПФ - [math]O(n\log{k})[/math], при классификации по ширине ЯПФ - [math]O(n*k)[/math]

1.7 Входные и выходные данные алгоритма

Входные данные: Невырожденная матрица [math]A[/math](с элементами [math]a_{ij}[/math]), по строкам которой записаны [math]n[/math] векторов некоторого пространства размерности [math]k[/math].

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

Выходные данные: Матрица [math]B_e[/math](с элементами [math]e_{ij}[/math]). Строки этой матрицы также задают вектора, такие, что длина каждого вектора равна единицы, а скалярное произведение двух различных векторов равно [math]0[/math].

Объем выходных данных: [math]nk[/math]

Замечание: Алгоритм может работать с вырожденной матрицей, он выдаёт нулевую строку на шаге [math]j[/math], если строка [math]j[/math] матрицы [math]A[/math] является линейной комбинацией предыдущих строк. В этом случае для корректного продолжения работы алгоритма необходима дополнительная проверка на равенство строки нулю и пропуск соответствующих строк. Количество построенных векторов будет равняться размерности пространства, порождаемого строками матрицы.