Участник:Илья Карандеев(ВТМ, 403)/QR-Факторизация методом Хаусхолдера

Материал из Алговики
< Участник:Илья Карандеев(ВТМ, 403)
Версия от 01:42, 17 ноября 2021; Илья Карандеев(ВТМ, 403) (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску


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

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

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

2.1.1 Реализация без распараллеливания

Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Она написана с помощью библиотеки cblas - оболочки замечательной фортрановской библиотеки BLAS для си. Это для одного процесса, нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции из cblas на 52-58 строке. После факторизации производится проверка ||Q * R - A|| / ||A||. Q - ортогональная матрица, R - верхняя треугольная. Их вычисление цель реализации алгоритма. Ну и Q * R должно примерно равняться A, это следует из теории. Вернее, без погрешности вычисления, в точности Q * R = A. Вычисленный порядок погрешности на персональном компьютере примерно 10^(-14), что есть довольно хорошо.


Code1.png
Code2.png













































































































2.1.2 Распараллеленная реализация

А это распараллеленная реализация. Распараллеливание осуществляется при помощи библиотекки open MPI. Данные у каждого процесса свои. Они пересылаются друг другу, что и следует из названия библиотеки: "Message passing interface". В этой реализации проверка ||Q*R - A|| / ||A|| выполняется только при условии, что размер матрицы кратен числу процессов. Написать проверку в этом случае сложнее из-за того, что нужно пересылать размер отдела матрицы, которую обрабатывает процесс (а он, вообще говоря, может отличаться у разных процессво, пусть и не более чем на единицу).

В изначальной версии программы ядром (тем, что занимает бОльшую часть времени при исполнении) являлась, как ни странно, пересылка между процессами. Это узкое место было исправлено: рассылка одного процесса всем остальным стала исполняться не при помощи функции MPI_Isend, а при помощи специальной функции - MPI_Bcast. Начальная версия программы, хоть и работала, но не только не приносила выигрыша в скорости, но даже замедляла распараллеленную версию относительно исходной, однопроцессной.

Слева Слева Слева Слева


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

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

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



Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. Оно проводилось на суперкомпьютере "Ломоносов-2" суперкомпьютерного комплекса МГУ. В первом эксперименте, эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем, что в одном узле на суперкомпьютере "Ломоносов-2" 14 ядер, а доступное количество узлов автору было равным 50. То есть максимум можно было задействовать 700 ядер.


Обычная шкала
Логарифмическая шкала





























Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментальных запусков программы на суперкомпьютере "Ломоносов-2".

My.3.png
My4.png
Figure 3.png

















































































































































В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.





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

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

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

Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям.

Можно найти и много пользовательских реализаций:

На языке Python: https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/
https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e

На языке R: https://rpubs.com/aaronsc32/qr-decomposition-householder - R

Для MatLab: https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations

3 Литература

В. Б. Андреев: "Численные методы"