Участник:BDA/Ортогонализация Грама-Шмидта: различия между версиями
Перейти к навигации
Перейти к поиску
BDA (обсуждение | вклад) Нет описания правки |
Zodiac (обсуждение | вклад) |
||
| Строка 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>. | |||
=== Информационный граф === | === Информационный граф === | ||
* | * | ||
Версия от 21:17, 15 октября 2016
| Ортогонализация Грама-Шмидта | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(nm^2) }[/math] |
| Объём входных данных | [math]\displaystyle{ nm }[/math] |
| Объём выходных данных | [math]\displaystyle{ nm }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ ? }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ ? }[/math] |
Основные авторы описания: Белов Н. А., Богомолов Д. А..
Свойства и структура алгоритма
Общее описание алгоритма
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Рассмотрим [math]\displaystyle{ n }[/math] векторов длины [math]\displaystyle{ m }[/math].
- Скалярное произведение векторов требует [math]\displaystyle{ n - 1 }[/math] сложение и [math]\displaystyle{ n }[/math] произведений.
- Нормализация вектора требует 1 скалярного произведения, 1 вычисления квадратного корня и [math]\displaystyle{ n }[/math] делений, то есть:
- [math]\displaystyle{ n-1 }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ n }[/math] ([math]\displaystyle{ \times }[/math]);
- [math]\displaystyle{ n }[/math] ([math]\displaystyle{ \div }[/math]);
- [math]\displaystyle{ 1 }[/math] ([math]\displaystyle{ \sqrt{} }[/math]).
- Вычитание проекции вектора требует 1 скалярного произведения, [math]\displaystyle{ n }[/math] сложений и [math]\displaystyle{ n }[/math] умножений, то есть:
- [math]\displaystyle{ 2n-1 }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ 2n }[/math] ([math]\displaystyle{ \times }[/math]).
- Вычисление [math]\displaystyle{ i }[/math]-го вектора требует [math]\displaystyle{ i-1 }[/math] вычитаний проекций с нормализацией, то есть:
- [math]\displaystyle{ (2n-1)(i-1)+n-1 }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ 2n(i-1)+n }[/math] ([math]\displaystyle{ \times }[/math]);
- [math]\displaystyle{ n }[/math] ([math]\displaystyle{ \div }[/math]);
- [math]\displaystyle{ 1 }[/math] ([math]\displaystyle{ \sqrt{} }[/math]).
- Мы вычисляем вектора от [math]\displaystyle{ i=1 }[/math] до [math]\displaystyle{ m }[/math], поэтому [math]\displaystyle{ i-1 }[/math] множителей выражаются треугольным числом [math]\displaystyle{ (m-1)\frac{m}{2} }[/math], а элементы независимых [math]\displaystyle{ i }[/math] умножаются на [math]\displaystyle{ m }[/math].
- [math]\displaystyle{ (2n-1)(m-1)\frac{m}{2}+(n-1)m }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ 2n(m-1)\frac{m}{2}+nm }[/math] ([math]\displaystyle{ \times }[/math]);
- [math]\displaystyle{ nm }[/math] ([math]\displaystyle{ \div }[/math]);
- [math]\displaystyle{ m }[/math] ([math]\displaystyle{ \sqrt{} }[/math]).
- В скалярном произведении [math]\displaystyle{ n }[/math] делений могут быть рассмотрены как [math]\displaystyle{ n }[/math] умножений:
- [math]\displaystyle{ (2n-1)(m-1)\frac{m}{2}+(n-1)m }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ 2n(m-1)\frac{m}{2}+2nm }[/math] ([math]\displaystyle{ \times }[/math]);
- [math]\displaystyle{ m }[/math] ([math]\displaystyle{ \div }[/math]);
- [math]\displaystyle{ m }[/math] ([math]\displaystyle{ \sqrt{} }[/math]).
Таким образом, требуется [math]\displaystyle{ 2nm^2 }[/math] операций. Сложность алгоритма [math]\displaystyle{ O(nm^2) }[/math].
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Срок сдачи продлен до 15 ноября.