Участник:Danyanya/Алгоритм Ланцоша для точной арифметики (без переортогонализации): различия между версиями
Danyanya (обсуждение | вклад) |
Danyanya (обсуждение | вклад) |
||
Строка 35: | Строка 35: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
+ | Описание алгоритма на псевдокоде: | ||
+ | |||
+ | {{algorithm-begin|name=Lanczos}} | ||
+ | |||
+ | <math>v_1 \leftarrow \, </math> ортонормированный случайный вектор . | ||
+ | <math>v_0 \leftarrow 0 \, </math> | ||
+ | <math>\beta_1 \leftarrow 0 \, </math> | ||
+ | |||
+ | '''for''' <math>j = 1,2,\cdots,m-1\, </math> | ||
+ | <math> w_j \leftarrow A v_j \, </math> | ||
+ | <math> \alpha_j \leftarrow w_j' \cdot v_j \, </math> | ||
+ | <math> w_j \leftarrow w_j' - \alpha_j v_j - \beta_j v_{j-1} \, </math> | ||
+ | <math> \beta_{j+1} \leftarrow \left\| w_j \right\| \, </math> | ||
+ | <math> v_{j+1} \leftarrow w_j / \beta_{j+1} \, </math> | ||
+ | '''endfor''' | ||
+ | |||
+ | <math> w_m \leftarrow A v_m \, </math> | ||
+ | <math> \alpha_m \leftarrow w_m \cdot v_m \, </math> | ||
+ | '''return''' | ||
+ | {{algorithm-end}} | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === |
Версия 17:38, 15 октября 2016
Алгоритм Ланцоша для точной арифметики (без переортогонализации) |
Основные авторы описания: Д.Р.Слюсарь
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 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 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм Ланцоша поиска собственных значений был опубликован Корнелием Ланцошем в 1950 году [1]. Этот итерационный алгоритм применим только к эрмитовым матрицам [math]A[/math]. Метод позволяет за [math]k[/math] итераций вычислять [math]k[/math]-ое приближение собственных значений и собственных векторов исходной матрицы [math]A[/math].
На вход алгоритма подается вещественная эрмитова матрица [math]A = A^{T}[/math],
- [math] A = \begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1\ n-1} & a_{1\ n} \\ a_{12} & a_{22} & a_{23} & \cdots & a_{2\ n-1} & a_{2\ n} \\ a_{13} & a_{23} & a_{33} & \cdots & a_{3\ n-1} & a_{3\ n} \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ a_{1\ n-1} & \cdots & \cdots & a_{n-2\ n-1} & a_{n-1\ n-1} & a_{n-1\ n} \\ a_{1\ n} & \cdots & \cdots & a_{n-2\ n} & a_{n-1\ n} & a_{n\ n} \\ \end{pmatrix} [/math]
Алгоритм Ланцоша соединяет в себя метод Ланцоша построения крыловского подпространства с процедурой Релея-Ритца. Иными словами, из оргонормированных векторов Ланцоша [??] на каждой итерации строится матрица [math]Q_k = [q_1, q_2, \dots, q_k][/math] размерности [math]n \times k[/math]. В качестве приближенных собственных значений матрицы [math]A[/math] берутся числа Ритца, т.е. собственные значения симметричной трехдиагональной матрицы [math]T_k = Q^T_k A Q[/math].
[math] T_k = \begin{pmatrix} \alpha_1 & \beta_1 & 0 & \dots & 0 \\ \beta_1 & \alpha_2 & \beta_2 & \dots & 0 \\ 0 & \beta_2 & \ddots & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & \beta_{k-1} \\ 0 & \dots & \dots & \beta_{k-1} & \alpha_k \end{pmatrix} [/math]
1.2 Математическое описание алгоритма
Описание алгоритма на псевдокоде:
[math]v_1 \leftarrow \, [/math] ортонормированный случайный вектор . [math]v_0 \leftarrow 0 \, [/math] [math]\beta_1 \leftarrow 0 \, [/math] for [math]j = 1,2,\cdots,m-1\, [/math] [math] w_j \leftarrow A v_j \, [/math] [math] \alpha_j \leftarrow w_j' \cdot v_j \, [/math] [math] w_j \leftarrow w_j' - \alpha_j v_j - \beta_j v_{j-1} \, [/math] [math] \beta_{j+1} \leftarrow \left\| w_j \right\| \, [/math] [math] v_{j+1} \leftarrow w_j / \beta_{j+1} \, [/math] endfor [math] w_m \leftarrow A v_m \, [/math] [math] \alpha_m \leftarrow w_m \cdot v_m \, [/math] return
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 Существующие реализации алгоритма
1. The IETL Project [2]
2. MatLab
3 Литература
1. Алгоритм Ланцоша (Википедия) [3]
2. Деммель Д. Вычислительная линейная алгебра/Пер. с англ. ХД Икрамова. – 2001.