Учacтник:Malikovmt/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией: различия между версиями

[непроверенная версия]

Версия 03:00, 30 января 2017

Алгоритм Ланцоша с полной переортогонализацией
Последовательный алгоритм
Последовательная сложность	[math]O(n^2k + nk^2)[/math]
Объём входных данных	[math]n^2 + n[/math]
Объём выходных данных	[math]2k - 1 + nk[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(nk + k^2)[/math]
Ширина ярусно-параллельной формы	[math]O(n)[/math]

Авторы: А.В.Ерошкин (ссылкаКод), М.М.Маликов (ссылка)

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

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

Алгоритм Ланцоша - итерационный метод, разработанный Корнелиусом Ланцошем, является адаптацией power methods для вычисления наиболее полезных собственных значений и собственных векторов n^Шаблон:Th order linear system за ограниченное количество операций m, где m много меньше n. Не смотря на то, что алгоритм является вычислительно эффективным, первоначально сформулированный метод не был полезным из-за его численной неустойчивости. В 1970 году Ojalvo и Ньюман показали как сделать метод численно стабильным и применили его для решения задачи очень крупных инженерных сооружений

1.1.1 Симметричность и положительная определённость матрицы

1.1.2 Режим накопления

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

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

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

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

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

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

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

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

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

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

1.11.1 Локальность реализации алгоритма

1.11.1.1 Структура обращений в память и качественная оценка локальности

1.11.1.2 Количественная оценка локальности

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

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

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

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

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

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

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

2 Литература

@@ Строка 14: / Строка 14: @@
 === Общее описание алгоритма ===
-'''Алгоритм Ланцоша'''
+'''Алгоритм Ланцоша''' - итерационный метод, разработанный Корнелиусом Ланцошем, является адаптацией '''power methods''' для вычисления наиболее полезных собственных значений и собственных векторов n^{{th}} '''order linear system''' за ограниченное количество операций '''m''', где '''m''' много меньше '''n'''. Не смотря на то, что алгоритм является вычислительно эффективным, первоначально сформулированный метод не был полезным из-за его численной неустойчивости. В 1970 году '''Ojalvo''' и Ньюман показали как сделать метод численно стабильным и применили его для решения задачи очень крупных инженерных сооружений
 ==== Симметричность и положительная определённость матрицы ====