Учacтник:Malikovmt/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией: различия между версиями
Malikovmt (обсуждение | вклад) |
Malikovmt (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{algorithm | {{algorithm | ||
| name = Алгоритм Ланцоша с полной переортогонализацией | | name = Алгоритм Ланцоша с полной переортогонализацией | ||
− | | serial_complexity = <math>O(n^2k | + | | serial_complexity = <math>O(n^2k)</math> |
− | | pf_height = <math>O( | + | | pf_height = <math>O(k)</math> |
− | | pf_width = <math>O(n)</math> | + | | pf_width = <math>O(n^2)</math> |
− | | input_data = <math>n | + | | input_data = <math>\frac{n(n + 1)}{2}</math> |
− | | output_data = <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>. |
=== Математическое описание алгоритма === | === Математическое описание алгоритма === |
Версия 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 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 1.11 Локальность данных и вычислений
- 1.12 Возможные способы и особенности параллельной реализации алгоритма
- 1.13 Масштабируемость алгоритма и его реализации
- 1.14 Динамические характеристики и эффективность реализации алгоритма
- 1.15 Выводы для классов архитектур
- 1.16 Существующие реализации алгоритма
- 2 Литература
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 Литература
<references \>