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

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

Материал из Алговики
Перейти к навигации Перейти к поиску


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


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

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

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

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

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

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

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

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

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].

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 Литература