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

Версия 00:17, 16 октября 2016

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

Основные авторы описания: Белов Н. А., Богомолов Д. А..

1 Свойства и структура алгоритма

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

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

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

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

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

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

Рассмотрим [math]n[/math] векторов длины [math]m[/math].

Скалярное произведение векторов требует [math]n - 1[/math] сложение и [math]n[/math] произведений.
Нормализация вектора требует 1 скалярного произведения, 1 вычисления квадратного корня и [math]n[/math] делений, то есть:
1. [math]n-1[/math] ([math]+[/math]);
2. [math]n[/math] ([math]\times[/math]);
3. [math]n[/math] ([math]\div[/math]);
4. [math]1[/math] ([math]\sqrt{}[/math]).
Вычитание проекции вектора требует 1 скалярного произведения, [math]n[/math] сложений и [math]n[/math] умножений, то есть:
1. [math]2n-1[/math] ([math]+[/math]);
2. [math]2n[/math] ([math]\times[/math]).
Вычисление [math]i[/math]-го вектора требует [math]i-1[/math] вычитаний проекций с нормализацией, то есть:
1. [math](2n-1)(i-1)+n-1[/math] ([math]+[/math]);
2. [math]2n(i-1)+n[/math] ([math]\times[/math]);
3. [math]n[/math] ([math]\div[/math]);
4. [math]1[/math] ([math]\sqrt{}[/math]).
Мы вычисляем вектора от [math]i=1[/math] до [math]m[/math], поэтому [math]i-1[/math] множителей выражаются треугольным числом [math](m-1)\frac{m}{2}[/math], а элементы независимых [math]i[/math] умножаются на [math]m[/math].
1. [math](2n-1)(m-1)\frac{m}{2}+(n-1)m[/math] ([math]+[/math]);
2. [math]2n(m-1)\frac{m}{2}+nm[/math] ([math]\times[/math]);
3. [math]nm[/math] ([math]\div[/math]);
4. [math]m[/math] ([math]\sqrt{}[/math]).
В скалярном произведении [math]n[/math] делений могут быть рассмотрены как [math]n[/math] умножений:
1. [math](2n-1)(m-1)\frac{m}{2}+(n-1)m[/math] ([math]+[/math]);
2. [math]2n(m-1)\frac{m}{2}+2nm[/math] ([math]\times[/math]);
3. [math]m[/math] ([math]\div[/math]);
4. [math]m[/math] ([math]\sqrt{}[/math]).

Таким образом, требуется [math]2nm^2[/math] операций. Сложность алгоритма [math]O(nm^2)[/math].

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

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

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

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

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

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

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

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

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

Срок сдачи продлен до 15 ноября.

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

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

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

3 Литература

@@ Строка 22: / Строка 22: @@
 *
 === Последовательная сложность алгоритма ===
-*
+Рассмотрим <math>n</math> векторов длины <math>m</math>.
+# Скалярное произведение векторов требует <math>n - 1</math> сложение и <math>n</math> произведений.
+# Нормализация вектора требует 1 скалярного произведения, 1 вычисления квадратного корня и <math>n</math> делений, то есть:
+## <math>n-1</math> (<math>+</math>);
+## <math>n</math> (<math>\times</math>);
+## <math>n</math> (<math>\div</math>);
+## <math>1</math> (<math>\sqrt{}</math>).
+# Вычитание проекции вектора требует 1 скалярного произведения, <math>n</math> сложений и <math>n</math> умножений, то есть:
+## <math>2n-1</math> (<math>+</math>);
+## <math>2n</math> (<math>\times</math>).
+# Вычисление <math>i</math>-го вектора требует <math>i-1</math> вычитаний проекций с нормализацией, то есть:
+## <math>(2n-1)(i-1)+n-1</math> (<math>+</math>);
+## <math>2n(i-1)+n</math> (<math>\times</math>);
+## <math>n</math> (<math>\div</math>);
+## <math>1</math> (<math>\sqrt{}</math>).
+# Мы вычисляем вектора от <math>i=1</math> до <math>m</math>, поэтому <math>i-1</math> множителей выражаются ''треугольным числом'' <math>(m-1)\frac{m}{2}</math>, а элементы независимых <math>i</math> умножаются на <math>m</math>.
+## <math>(2n-1)(m-1)\frac{m}{2}+(n-1)m</math> (<math>+</math>);
+## <math>2n(m-1)\frac{m}{2}+nm</math> (<math>\times</math>);
+## <math>nm</math> (<math>\div</math>);
+## <math>m</math> (<math>\sqrt{}</math>).
+# В скалярном произведении <math>n</math> делений могут быть рассмотрены как <math>n</math> умножений:
+## <math>(2n-1)(m-1)\frac{m}{2}+(n-1)m</math> (<math>+</math>);
+## <math>2n(m-1)\frac{m}{2}+2nm</math> (<math>\times</math>);
+## <math>m</math> (<math>\div</math>);
+## <math>m</math> (<math>\sqrt{}</math>).
+Таким образом, требуется <math>2nm^2</math> операций. Сложность алгоритма <math>O(nm^2)</math>.
 === Информационный граф ===
 *