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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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