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

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

Версия 17:00, 1 февраля 2017

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

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

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

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

Алгоритм Ланцоша - итерационный метод, используемый для вычисления части собственных значений и соответствующих им собственных векторов матрицы [math]A[/math] размера [math]n*n[/math], изначально разработанный Корнелием Ланцошем. Преимуществами использования метода является относительно небольшое потребление памяти и вычислительных ресурсов, а также наличие параметра [math]k[/math], [math]k \lt \lt n[/math], контролирующего количество итераций. Несмотря на то, что алгоритм является вычислительно эффективным, первоначально сформулированный метод был плохо применим из-за численной неустойчивости - метод хорошо работал на целочисленных значениях, однако в арифметике с плавающей точкой ошибки округления давали большую погрешность. В 1970 году Ojalvo и Newman показали, как сделать метод численно стабильным и применили его для расчета крупных инженерных сооружений, подверженных динамическим нагрузкам. Кроме того, они показали способ выбора начального приближения (с использованием ГПСЧ), а также эмпирический способ для выбора числа [math]k[/math] (примерно в полтора раза больше искомого числа собственных векторов). В данный момент существует две основных модификации метода (с полной и выборочной переортогонализацией), а также большое количество модификаций, использующихся в различных технических областях. Алгоритм используется для больших [math]n[/math].

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

@@ Строка 1: / Строка 1: @@
 {{algorithm
 | name              = Алгоритм Ланцоша с полной переортогонализацией
-| serial_complexity = <math>O(n^2k + nk^2)</math>
+| serial_complexity = <math>O(n^2k)</math>
-| pf_height         = <math>O(nk + k^2)</math>
+| pf_height         = <math>O(k)</math>
-| pf_width          = <math>O(n)</math>
+| pf_width          = <math>O(n^2)</math>
-| input_data        = <math>n^2 + n</math>
+| input_data        = <math>\frac{n(n + 1)}{2}</math>
-| output_data       = <math>2k - 1 + nk</math>
+| output_data       = <math>k(n + 1)</math>
 }}
@@ Строка 14: / Строка 14: @@
 === Общее описание алгоритма ===
-'''Алгоритм Ланцоша''' - итерационный метод, используемый для вычисления части собственных значений и соответствующих им собственных векторов матрицы <math>A</math> размера <math>n*n</math>, изначально разработанный Корнелием Ланцошем. Преимуществами использования метода является относительно небольшое потребление памяти и вычислительных ресурсов, а также наличие параметра <math>k</math>, контролирующего количество итераций. Несмотря на то, что алгоритм является вычислительно эффективным, первоначально сформулированный метод был плохо применим из-за численной неустойчивости - метод хорошо работал на целочисленных значениях, однако в арифметике с плавающей точкой ошибки округления давали большую погрешность. В 1970 году Ojalvo и Newman показали, как сделать метод численно стабильным и применили его для расчета крупных инженерных сооружений, подверженных динамическим нагрузкам. Кроме того, они показали способ выбора начального приближения (с использованием ГПСЧ), а также эмпирический способ для выбора числа <math>k</math> (примерно в полтора раза больше искомого числа собственных векторов). В данный момент существует две основных модификации метода (с полной и выборочной переортогонализацией), а также большое количество модификаций, использующихся в различных технических областях.
+'''Алгоритм Ланцоша''' - итерационный метод, используемый для вычисления части собственных значений и соответствующих им собственных векторов матрицы <math>A</math> размера <math>n*n</math>, изначально разработанный Корнелием Ланцошем. Преимуществами использования метода является относительно небольшое потребление памяти и вычислительных ресурсов, а также наличие параметра <math>k</math>, <math>k << n</math>, контролирующего количество итераций. Несмотря на то, что алгоритм является вычислительно эффективным, первоначально сформулированный метод был плохо применим из-за численной неустойчивости - метод хорошо работал на целочисленных значениях, однако в арифметике с плавающей точкой ошибки округления давали большую погрешность. В 1970 году Ojalvo и Newman показали, как сделать метод численно стабильным и применили его для расчета крупных инженерных сооружений, подверженных динамическим нагрузкам. Кроме того, они показали способ выбора начального приближения (с использованием ГПСЧ), а также эмпирический способ для выбора числа <math>k</math> (примерно в полтора раза больше искомого числа собственных векторов). В данный момент существует две основных модификации метода (с полной и выборочной переортогонализацией), а также большое количество модификаций, использующихся в различных технических областях. Алгоритм используется для больших <math>n</math>.
 === Математическое описание алгоритма ===