|
|
| Строка 1: |
Строка 1: |
| − | {{algorithm
| + | [[Участник:Danyanya/Алгоритм_Ланцоша_для_точной_арифметики_(без_переортогонализации)]] |
| − | | name = Алгоритм Ланцоша без переортогонализации
| |
| − | | serial_complexity =
| |
| − | | pf_height =
| |
| − | | pf_width =
| |
| − | | input_data =
| |
| − | | output_data =
| |
| − | }}
| |
| − | | |
| − | Основные авторы описания: [[Участник:m.grigoriev|Григорьев М.А.]]
| |
| − | | |
| − | == Свойства и структура алгоритма ==
| |
| − | | |
| − | === Общее описание алгоритма ===
| |
| − | '''Алгоритм Ланцоша''' был опубликовн физиком и математиком Корнелием Ланцошем<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>.
| |
| − | | |
| − | === Математическое описание алгоритма ===
| |
| − | | |
| − | === Вычислительное ядро алгоритма ===
| |
| − | | |
| − | === Макроструктура алгоритма ===
| |
| − | | |
| − | === Схема реализации последовательного алгоритма ===
| |
| − | | |
| − | === Последовательная сложность алгоритма ===
| |
| − | | |
| − | === Информационный граф ===
| |
| − | | |
| − | === Ресурс параллелизма алгоритма ===
| |
| − | | |
| − | === Входные и выходные данные алгоритма ===
| |
| − | | |
| − | === Свойства алгоритма ===
| |
| − | | |
| − | == Программная реализация алгоритма ==
| |
| − | | |
| − | === Особенности реализации последовательного алгоритма ===
| |
| − | | |
| − | === Локальность данных и вычислений ===
| |
| − | | |
| − | === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| − | | |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − | | |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | | |
| − | === Выводы для классов архитектур ===
| |
| − | | |
| − | === Существующие реализации алгоритма ===
| |
| − | | |
| − | == Литература ==
| |
