Участник:KibAndrey/Ортогонализация Грама-Шмидта: различия между версиями
KibAndrey (обсуждение | вклад) |
Amelie (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
= ЧАСТЬ. Свойства и структура алгоритма = | = ЧАСТЬ. Свойства и структура алгоритма = | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
Версия 19:59, 14 октября 2016
| Ортогонализация Грама-Шмидта | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O\left(n^3\right)[/math] |
| Объём входных данных | [math][/math] |
| Объём выходных данных | [math][/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math][/math] |
| Ширина ярусно-параллельной формы | [math][/math] |
Основные авторы описания: А.В.Кибанов, Т.З.Аджиева.
Содержание
- 1 ЧАСТЬ. Свойства и структура алгоритма
- 2 ЧАСТЬ Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 ЧАСТЬ. Свойства и структура алгоритма
1.1 Математическое описание алгоритма
1.2 Макроструктура алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Последовательная сложность алгоритма
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.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] является линейной комбинацией предыдущих строк. В этом случае для корректного продолжения работы алгоритма необходима дополнительная проверка на равенство строки нулю и пропуск соответствующих строк. Количество построенных векторов будет равняться размерности пространства, порождаемого строками матрицы.
