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

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

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

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

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

Основное время работы алгоритма приходится на вычисление сумм [math]\sum_{i=1}^{j-1} \mathbf{proj}_{\mathbf{b}_i} \mathbf{a}_i \forall j: j=\overline{1, m}[/math].

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

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

1. Скалярное произведение векторов требует [math]n - 1[/math] сложение и [math]n[/math] произведений.
2. Нормализация вектора требует 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]).
3. Вычитание проекции вектора требует 1 скалярного произведения, [math]n[/math] сложений и [math]n[/math] умножений, то есть:
   1. [math]2n-1[/math] ([math]+[/math]);
   2. [math]2n[/math] ([math]\times[/math]).
4. Вычисление [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]).
5. Мы вычисляем вектора от [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]).
6. В скалярном произведении [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].

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

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

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