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

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

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

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

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

Анализ математических формул процесса ортогонализации Грама-Шмидта показывает, что алгоритм имеет три вычислительных ядра:

• вычисления скалярного произведения (к этой операции сводится вычисление длины вектора)
• умножения вектора на число
• сложения векторов.

Эти операции выполняются за время порядка [math]\displaystyle{ O\left(n\right) }[/math]

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

[math]\displaystyle{ \begin{align} a_{1} & =b_{1}, \\ \beta_{ij} & = \frac{(a_{i},b_j)}{(b_j,b_j)}=-\frac{(a_i,b_j)}{|b_j|^2}, \quad i \in [2, n], \quad j \in [1, n] ,\\ \end{align} }[/math]

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

[math]\displaystyle{ \begin{align} a_{1} & =b_{1}, \\ \beta_{ij} & = \frac{(a_{i},b_j)}{(b_j,b_j)}=-\frac{(a_i,b_j)}{|b_j|^2}, \quad i \in [2, n], \quad j \in [1, n] ,\\ \end{align} }[/math]