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

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

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


== Математическое описание алгоритма ==
== Математическое описание алгоритма ==
== Вычислительное ядро алгоритма ==
Анализ математических формул процесса ортогонализации Грама-Шмидта показывает, что алгоритм имеет три вычислительных ядра:
* вычисления скалярного произведения (к этой операции сводится вычисление длины вектора)
* умножения вектора на число
* сложения векторов.
Эти операции выполняются за время порядка <math>O\left(n\right)</math>


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

Версия от 14:27, 13 октября 2016


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


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



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

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

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

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

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

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

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

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

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

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

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

ЧАСТЬ Программная реализация алгоритма

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

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

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

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

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

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

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

Литература