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

Файл:Symbol wait.svg

Эта работа ждет рассмотрения преподавателем Дата последней правки страницы: 19.01.2017 Авторы этой статьи считают, что задание выполнено.

Авторы: Хакимов А. С.

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

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

Алгоритм Ланцоша служит для нахождения собственных значений и собственных векторов для больших разреженных матриц, к которым нельзя применить прямые методы из-за больших требований к памяти и времени. Он был опубликован Корнелием Ланцошем в 1950 году. Его эффективность обусловлена экономией памяти для хранения матриц и экономией вычислительных ресурсов. Алгоритм итерационный и использует степенной метод для поиска наибольших собственных значений и векторов матриц. Основной недостаток алгоритма заключается в накоплении ошибок округления, для решения которых появились методы поддержания ортогонализации т.н. векторов Ланцоша. Здесь мы рассмотрим выборочный метод поддержания ортогонализации, который существенно экономит процессорное время.

На вход алгоритма подаётся [math]\displaystyle{ A = A^T }[/math],

[math]\displaystyle{ 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]\displaystyle{ ,\, \; }[/math]

случайный вектор [math]\displaystyle{ b }[/math], как первое приближение собственного вектора матрицы и [math]\displaystyle{ k }[/math] - количество собственных значений и собственных векторов, которые требуется найти.

Матрица [math]\displaystyle{ Q_j = [q_1, q_2, \dots, q_j] }[/math] размерности [math]\displaystyle{ n \times j }[/math] строится на каждой итерации и состоит из ортонормированных векторов Ланцоша. А в качестве приближенных собственных значений берутся числа Ритца [math]\displaystyle{ \theta_i }[/math], - собственные значения симметричной трехдиагональной матрицы [math]\displaystyle{ T_j = Q^T_j A Q_j }[/math] размерности [math]\displaystyle{ j \times j }[/math].

[math]\displaystyle{ T_j = \begin{pmatrix} \alpha_1 & \beta_1 \\ \beta_1 & \alpha_2 & \beta_2 \\ & \beta_2 & \ddots & \ddots \\ & & \ddots & \ddots & \beta_{j-1} \\ & & & \beta_{j-1} & \alpha_j \end{pmatrix}\; (2). }[/math]

Однако, векторы [math]\displaystyle{ q_j }[/math] теряют ортогональность вследствие приобретения больших компонент в направлениях векторов Ритца [math]\displaystyle{ y_{i,j} = Q_j v_i }[/math], отвечающих сошедшимся числам Ритца [math]\displaystyle{ \theta_i }[/math]. Поэтому чтобы построить [math]\displaystyle{ q_j }[/math], предлагается на каждом шаге следить за оценками погрешностей [math]\displaystyle{ \beta_{t}|v_i(t)|, i = 1 \dots t, t = j - 1 }[/math], где [math]\displaystyle{ v_i(t) }[/math] - [math]\displaystyle{ t }[/math]-я компонента собственного вектора [math]\displaystyle{ v_i }[/math]. И когда какая-то оценка становится слишком малой, проводить ортогонализацию вектора Ланцоша [math]\displaystyle{ z }[/math]. Величина [math]\displaystyle{ \beta_{t}|v_i(t)| }[/math] считается малой, если она меньше, чем [math]\displaystyle{ \sqrt{\varepsilon}||T_{t}|| }[/math], где [math]\displaystyle{ \varepsilon }[/math] - доступная машинная точность чисел.

После следует вычисление собственных значений [math]\displaystyle{ \theta_j }[/math] и собственных векторов [math]\displaystyle{ v_j }[/math] полученной трехдиагональной матрицы [math]\displaystyle{ T_j }[/math], например, с помощью метода "разделяй и властвуй"

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

[math]\displaystyle{  q_{1} = b_{j}/\|b\|_2, \beta_0=0, q_0=0 }[/math]
[math]\displaystyle{  for\, j=1\,\, to\, \, k }[/math]
    [math]\displaystyle{ z=Aq_j, }[/math]
    [math]\displaystyle{ \alpha_j=q_j^Tz, }[/math]
    [math]\displaystyle{ z=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, }[/math]
    [math]\displaystyle{ \text{/* Провести выборочную ортогонализацию по отношению},   }[/math]
    [math]\displaystyle{ \text{   к сошедшимся векторам Ритца */} }[/math]
    [math]\displaystyle{ for\, i \leqslant k, \text{таких, что} \, \beta_{t}|v_i(t)| \leqslant \sqrt{\varepsilon}\|T_{k}\| \,  }[/math]
    [math]\displaystyle{ z = z-(y^T_{i,k},z)y_{i,k} }[/math]
    [math]\displaystyle{ end \, for }[/math]
    [math]\displaystyle{ \beta_{j}=\|z\|_2 }[/math]
    [math]\displaystyle{ q_{j+1}=z/\beta_{j},  }[/math]
    [math]\displaystyle{ \text{Вычислить собственные значения и собственные векторы} }[/math]
    [math]\displaystyle{ \text{матрицы} \, \, T_{j} \, \text{и оценки погрешности в них} }[/math]
[math]\displaystyle{ end \, for }[/math]

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

• Умножение матрицы на вектор, [math]\displaystyle{ z=Aq_j, }[/math].

• Ортогонализация по отношению к сошедшимся векторам [math]\displaystyle{ z = z-(y^T_{i,k},z)y_{i,k} }[/math] для [math]\displaystyle{ i = 1 \dots t }[/math]

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

Для алгоритма Ланцоша можно выделить следующие макрооперации:

• Умножение матрицы на вектор. Состоит из операций умножения вектора на число и сложения векторов.

[math]\displaystyle{ z=Aq_j, }[/math].

• Вычисление вектора [math]\displaystyle{ q_{j+1} }[/math] как скалярное произведение двух других векторов.

[math]\displaystyle{ \alpha_j=q_j^Tz, }[/math]

[math]\displaystyle{ z=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, }[/math]

[math]\displaystyle{ q_{j+1}=z/\|z\|_2 }[/math]

• Ортогонализация вектора Ланцоша с помощью скалярного произведения:

[math]\displaystyle{ z = z-(y^T_{i,t},z)y_{i,t} }[/math]

• Алгоритм "разделяй и властвуй" для вычисления собственных значений матрицы.

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

Алгоритм выполняется в следующей последовательности:

[math]\displaystyle{ 1.\, \, \beta_0 = 0,\; q_0 = 0 }[/math] #Инициализируем векторы

[math]\displaystyle{ 2.\, \, \|b\|_2 = \sqrt{\sum\limits_{j=1}^{n} b_j^2} }[/math] #Вычисляем норму вектора начального приближения.

[math]\displaystyle{ 3.\, \, q_{1_{j}} = \frac{b_{j}}{\|b\|_2}, \; j = 1,\, \dots\,, n }[/math] #Нормализуем вектор начального приближения.

[math]\displaystyle{ 4.\, \, }[/math] Начинается цикл, в котором не более чем [math]\displaystyle{ k }[/math]. На [math]\displaystyle{ i }[/math]-й итерации производятся следующие вычисления:

[math]\displaystyle{ 4.1.\, \, z_j = \sum\limits_{m=1}^{n} a_{jm} q_{i_m}, \; j = 1,\,\dots\,, n }[/math] #Считаем результат применения линейного оператора [math]\displaystyle{ A }[/math] к вектору [math]\displaystyle{ q_i }[/math].

[math]\displaystyle{ 4.2.\, \, \alpha_i = \sum\limits_{j=1}^{n}q_{i_j} z_j }[/math] #Получаем результат скалярного произведения векторов [math]\displaystyle{ q_i }[/math] и [math]\displaystyle{ z }[/math].

[math]\displaystyle{ 4.3.\, \, z_j = z_j - \alpha_i q_{i_j} - \beta_{i-1}q_{i-1_j}, \, j = 1,\,\dots\,, n }[/math] #Вычисляем линейную комбинацию векторов.

[math]\displaystyle{ 4.4.\, \, }[/math] Начинается цикл, в котором производится выборочная ортогонализация векторов Ланцоша

[math]\displaystyle{ 4.4.1.\, \, }[/math] Вычисляется вектор Ритца [math]\displaystyle{ y_{i,k_d} = \sum\limits_{x=1}^{k} q_{x_d} v_{i_x}, \; d = 1,\,\dots\,, n, }[/math], где  [math]\displaystyle{ y_{i,k_d} }[/math] -  [math]\displaystyle{ d }[/math]-я компонента вектора Ритца [math]\displaystyle{ y, }[/math]
[math]\displaystyle{ 4.4.2.\, \, }[/math] Производится скалярное умножение [math]\displaystyle{ y_{i,k}^T }[/math]  и [math]\displaystyle{  z: \; \; \gamma = \sum\limits_{d=1}^{n}y_{i,k_d} z_d, }[/math]
[math]\displaystyle{ 4.4.3.\, \, }[/math] Ищется новое собственное значение [math]\displaystyle{  \theta_j  }[/math] и собственный вектор [math]\displaystyle{  v_j  }[/math] для полученной матрицы [math]\displaystyle{  T_j, }[/math]

[math]\displaystyle{ 4.5.\, \, \beta_i = \|z\|_2 = \sqrt{\sum\limits_{j=1}^{n} z_j^2} }[/math] #Считаем норму вектора [math]\displaystyle{ z }[/math].

[math]\displaystyle{ 4.6. }[/math] Проверка равенства [math]\displaystyle{ \beta_i == 0 }[/math] # Если норма оказалась равной нулю, то завершаем итерации и переходим к вычислению собственных векторов и собственных значений полученной матрицы. В обратном случае, продолжаем выполнения итераций.

[math]\displaystyle{ 4.7.\, \, q_{i+1_j} = \frac{z_j}{\beta_i}, \; j = 1,\, \dots \,, n }[/math] #Нормируем вектор [math]\displaystyle{ z }[/math].

[math]\displaystyle{ 4.8.\, }[/math] Если выполнили [math]\displaystyle{ k }[/math] итераций, то завершаем выполнение итераций, переходим к следующему шагу. Иначе начинаем последующую итерацию цикла.

[math]\displaystyle{ 5. }[/math] Вычисляем собственные значения и собственные вектора полученной матрицы [math]\displaystyle{ T_k }[/math].

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

• Вычисление вектора [math]\displaystyle{ z }[/math] - [math]\displaystyle{ n^2 }[/math] операций умножения и [math]\displaystyle{ n(n-1) }[/math] операций сложения
• Вычисление скалярного произведения векторов - [math]\displaystyle{ n }[/math] операций умножения и [math]\displaystyle{ (n-1) }[/math] сложений
• Вычисление вектора [math]\displaystyle{ z }[/math] - [math]\displaystyle{ 2n }[/math] умножений и [math]\displaystyle{ 2n }[/math] сложений
• Оценка погрешностей - [math]\displaystyle{ kn }[/math] операций умножения
• Выборочная переортогонализация - [math]\displaystyle{ O(2nj) }[/math] умножений и [math]\displaystyle{ O(2j(n-1) + n) }[/math] сложений
• Вычисление нормы вектора - [math]\displaystyle{ n }[/math] операций умножения и [math]\displaystyle{ (n-1) }[/math] сложений
• Вычисление нового столбца матрицы [math]\displaystyle{ Q }[/math] - [math]\displaystyle{ n }[/math] операций умножения

Итого на каждой итерации:

• Умножений: [math]\displaystyle{ n^2 + n + 2n + kn + O(2nj) + n + n = n^2 + 5n + kn + O(2nj) }[/math]
• Сложений: [math]\displaystyle{ n(n-1) + n-1 + 2n + O(2j(n-1) + n) + n-1 = n^2 + 3n + O(2j(n-1) + n) -2 }[/math]

Итого за все время выполнения алгоритма:

• Умножений: [math]\displaystyle{ kn^2 + 5kn + k^2n + O(k^2n + kn) }[/math]
• Сложений: [math]\displaystyle{ kn^2 + 3kn + O((k^2+k)(n-1)+kn) = kn^2 + 3kn + O(k^2(n-1)+2kn-k) }[/math]

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

рис. 1: Информационный граф

Здесь:
[math]\displaystyle{ Ax }[/math]  — перемножение матрицы и вектора,
[math]\displaystyle{ \|x\| }[/math]  — макрооперация взятия нормы,
[math]\displaystyle{ \alpha x }[/math]  — умножение скаляра на вектор,
[math]\displaystyle{ \cdot  }[/math]  — операция скалярного умножения векторов,
[math]\displaystyle{ \mathsf{F} }[/math]  — операция [math]\displaystyle{ z-\sum\nolimits_{i=1}^{j-1}(z^Tq_i)q_i }[/math],
[math]\displaystyle{ \mathsf{f} }[/math]  — вычисление линейной комбинации векторов

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

На каждой из итераций алгоритма можно получить выигрыш за счет распараллеливания следующих шагов:

• Вычисление вектора [math]\displaystyle{ z }[/math] - умножение матрицы размера [math]\displaystyle{ n \times n }[/math] на вектор длины [math]\displaystyle{ n }[/math] - [math]\displaystyle{ n }[/math] ярусов сложений, [math]\displaystyle{ n }[/math] операций умножений в каждом
• Вычисление коэффициента [math]\displaystyle{ \alpha_j }[/math] - скалярное произведение векторов - [math]\displaystyle{ n }[/math] ярусов сложений, 1 операция умножения в каждом
• Вычисление нового значения вектора [math]\displaystyle{ z }[/math]: 2 яруса умножений длины [math]\displaystyle{ n }[/math] (умножение вектора на число), 2 яруса вычитаний длины [math]\displaystyle{ n }[/math]
• Выборочная переортогонализация: последовательно для всех [math]\displaystyle{ i \le k }[/math] выполняется [math]\displaystyle{ j }[/math] ярусов сложений, [math]\displaystyle{ n }[/math] операций умножений в каждом, [math]\displaystyle{ n }[/math] ярусов сложений, [math]\displaystyle{ j }[/math] операций умножений в каждом, один ярус вычитаний размера [math]\displaystyle{ n }[/math]
• Вычисление [math]\displaystyle{ \beta_j }[/math] - скалярное произведение векторов - [math]\displaystyle{ n }[/math] ярусов сложений, 1 операция умножения в каждом
• Вычисление [math]\displaystyle{ q_j }[/math] - деление вектора на число - один ярус делений размера [math]\displaystyle{ n }[/math]

Сложность алгоритма по ширине ЯПФ - [math]\displaystyle{ O(n) }[/math].

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

Входные данные: вещественная матрица [math]\displaystyle{ A }[/math] размера [math]\displaystyle{ n \times n }[/math], вектор [math]\displaystyle{ b }[/math] длины [math]\displaystyle{ n }[/math], число [math]\displaystyle{ k }[/math]

Объем входных данных: [math]\displaystyle{ n^2 + n + 1 }[/math]

Выходные данные: матрица [math]\displaystyle{ Q }[/math] размера [math]\displaystyle{ n \times k }[/math]

Объем выходных данных: [math]\displaystyle{ nk }[/math]

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

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

Исследование алгоритма на масштабируемость производилось на суперкомпьютере "Ломоносов" с использованием технологии MPI. Для тестирования была выбрана вот эта реализация алгоритма.

Набор параметров, которые изменялись при тестировании:

• Число процессоров от 16 до 128.
• Размерность матрицы от 5000 до 50000 с шагом 5000.

Табл. 1. Результаты тестирования. В ячейках таблицы -- время работы алгоритма в секундах.

		Число процессоров
		16	32	64	128
Размер матрицы	5000	1,07	0,71	0,62	0,54
	10000	2,39	1,94	1,17	0,79
	15000	4,35	3,38	1,89	1,59
	20000	7,63	5,19	3,78	2,35
	15000	12,41	7,33	4,32	3,44
	30000	16,68	9,36	5,02	4,68
	35000	22,58	11,92	8,04	6,20
	40000	29,31	15,90	8,47	7,43
	45000	37,04	19,42	10,55	9,04
	50000	45,64	23,39	16,09	10,25

рис. 1: Информационный граф

рис. 1: Информационный граф

Существующие реализации

Реализация в проекте Vienna VL

Реализация в проекте IETL

Реализация в проекте ARPACK

Lanczos Plus Plus

ED Lanczos

Paralleles Rechnen 2

Cuda-Arnoldi