Участник:M.grigoriev/Алгоритм Ланцоша для точной арифметики (без переортогонализации): различия между версиями

Версия 18:08, 15 октября 2016

Алгоритм Ланцоша без переортогонализации

Основные авторы описания: Григорьев М.А.

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

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

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

Алгоритм Ланцоша был опубликовн физиком и математиком Корнелием Ланцошем^[1] в 1950 году. Этот метод является частным случаем алгоритма Арнольда в случае, если исходная матрица [math]A[/math] - симметрична, и был представлен как итерационный метод вычисления собственных значений симметричной матрицы. Этот метод позволяет за [math]k[/math] итераций вычислять [math]k[/math] приближений собственных значений и собственных векторов исходной матрицы. Хотя алгоритм и был эффективным в вычислительном смысле, но он на некоторое время был предан забвению из-за численной неустойчивости. Только в 1970 Ojalvo и Newman^[2] модифицировали алгоритм для использования в арифметике с плавающей точкой. Новый метод получил название алгоритма Ланцоша с полной переортогонализацией.

Алгоритм соединяет в себя метод Ланцоша построения крыловского подпространства с процедурой Релея-Ритца. Из ортонормированных векторов Ланцоша строится матрица [math]Q_k = [q_1, q_2, \dots, q_k][/math] размерности [math]n \times k[/math] и в качестве приближенных собственных значений принимаются числа Ритца, т.е. собственные значения симметричной трехдиагональной матрицы [math]T_k = Q^T_k A Q[/math] размерности [math]k \times k[/math].

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

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

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

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

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

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

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

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

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

2 Программная реализация алгоритма

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

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

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

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

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

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

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

3 Литература

↑ Lanczos, C. "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators", J. Res. Nat’l Bur. Std. 45, 255-282 (1950).
↑ Ojalvo, I.U. and Newman, M., "Vibration modes of large structures by an automatic matrix-reduction method", AIAA J., 8 (7), 1234–1239 (1970).

[1] Lanczos, C. "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators", J. Res. Nat’l Bur. Std. 45, 255-282 (1950).

[2] Ojalvo, I.U. and Newman, M., "Vibration modes of large structures by an automatic matrix-reduction method", AIAA J., 8 (7), 1234–1239 (1970).

[1]

[2]

@@ Строка 13: / Строка 13: @@
 === Общее описание алгоритма ===
+'''Алгоритм Ланцоша''' был опубликовн физиком и математиком Корнелием Ланцошем<ref>Lanczos, C. "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators", J. Res. Nat’l Bur. Std. 45, 255-282 (1950).</ref> в 1950 году. Этот метод является частным случаем алгоритма Арнольда в случае, если исходная матрица <math>A</math> - симметрична, и был представлен как итерационный метод вычисления собственных значений симметричной матрицы. Этот метод позволяет за <math>k</math> итераций вычислять <math>k</math> приближений собственных значений и собственных векторов исходной матрицы. Хотя алгоритм и был эффективным в вычислительном смысле, но он на некоторое время был предан забвению из-за численной неустойчивости. Только в 1970 Ojalvo и Newman<ref>Ojalvo, I.U. and Newman, M., "Vibration modes of large structures by an automatic matrix-reduction method", AIAA J., 8 (7), 1234–1239 (1970).</ref> модифицировали алгоритм для использования в арифметике с плавающей точкой. Новый метод получил название [[Алгоритм Ланцоша с полной переортогонализацией | алгоритма Ланцоша с полной переортогонализацией]].
+Алгоритм соединяет в себя метод Ланцоша построения крыловского подпространства с процедурой Релея-Ритца. Из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1, q_2, \dots, q_k]</math> размерности <math>n \times k</math> и в качестве приближенных собственных значений принимаются числа Ритца, т.е. собственные значения симметричной трехдиагональной матрицы <math>T_k = Q^T_k A Q</math> размерности <math>k \times k</math>.
 === Математическое описание алгоритма ===