Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 35: Строка 35:
  
 
Все вершины графа можно разбить на пять групп, каждой из которых соответствует вид исполняемой операции. Дадим описание каждой из групп.
 
Все вершины графа можно разбить на пять групп, каждой из которых соответствует вид исполняемой операции. Дадим описание каждой из групп.
<math>
+
 
'''Первая''' группа - вершины, которым соответствует операция возведение в квадрат. На графе они располагаются в двумерной области. <math>i</math> изменяется от <math>1</math> до <math>n</math>, <math>k</math> изменяется от <math>1</math> до <math>m</math>.
+
'''Первая''' группа - вершины, которым соответствует операция возведение в квадрат. На графе они располагаются в двумерной области.<math> i</math> изменяется от <math>1</math> до <math>n</math>, <math>k</math> изменяется от <math>1</math> до <math>m</math>.
  
 
Значениями аргументов для этих функций являются:
 
Значениями аргументов для этих функций являются:

Версия 18:15, 14 октября 2016


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


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



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

1.1 Общее описание алгоритма

Ортогонализации Грама-Шмидта[1] – алгоритм построения для данной линейно независимой системы векторов евклидова или эрмитова пространства [math]V[/math] ортогональной системы ненулевых векторов, которые имеют ту же самую линейную оболочку, при котором каждый вектор построенной системы линейно выражается через векторы данной системы. Исторически это первый алгоритм, описывающий процесс ортогониализации. Традиционно его связывают с именами Йоргена Педерсена Грама и Эрхарда Шмидта. Эрхард Шмидт[2] был учеником великих математиков Германа Шварца и Давида Гильберта. Алгоритм ортогонализации был опубликован Э. Шмидтом в 1907 году [3] в его исследовании интегральных уравнений, которое в свою очередь дало привело к развитию теории гильбертовых пространств. Шмидт использовал процесс ортогонализации применительно к геометрии гильбертова пространства решений интегральных уравнений отмечал, что процесс ортогонализации принципиально такой же, какой прежде использовал Й. Грам.

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

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

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

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

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

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

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

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

Первая группа - вершины, которым соответствует операция возведение в квадрат. На графе они располагаются в двумерной области.[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 изменяется от \lt math\gt 1[/math] до [math]n[/math], [math]j[/math] изменяется от [math]1[/math] до [math]i[/math], [math]k[/math] изменяется от [math]1[/math] до [math]m div 2[/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*k[/math] и [math]i,1,2*k - 1[/math] ;
  • при [math]j \gt 1, t = 1[/math] - результат выполнения функции в вершинах пятой группы с координатами [math]i,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]k[/math] изменяется от [math]1[/math] до [math]m[/math].

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

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

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

2 ЧАСТЬ Программная реализация алгоритма

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

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература

  1. Математическая энциклопедия / Гл. ред. И. М. Виноградов – М: “Советская энциклопедия”, 1984 – Т.4 Ок–Сло.
  2. Meyer C. D. Matrix analysis and applied linear algebra. – Siam, 2000. – Т. 2.
  3. Erchard Shmidt. Mathematische Annalen Zur Theorie der linearen und nichtlinearen Integralgleichungen, 1. Teil: Entwicklung willkürlicher Funktionen nach Systemen vorgeschriebener. – Mathematische Annalen, 63 (1907), pp. 433–476.