Участник:Илья Карандеев(ВТМ, 403)/QR-Факторизация методом Хаусхолдера: различия между версиями
| Строка 19: | Строка 19: | ||
[[Файл:My2.png.png|справа|Обычная шкала]] | [[Файл:My2.png.png|справа|Обычная шкала]] | ||
[[Файл:My1.png|слева|Логарифмическая шкала]] | [[Файл:My1.png|слева|Логарифмическая шкала]] | ||
| − | <br><br><br><br><br><br><br><br><br><br><br> | + | |
| − | <br><br><br><br><br><br><br><br><br><br><br> | + | <br><br><br><br><br><br><br><br><br> |
| + | <br><br><br><br><br><br><br><br><br> | ||
| + | <br><br><br><br><br><br><br><br><br> | ||
| + | <br><br><br><br><br><br><br><br><br> | ||
| Строка 29: | Строка 32: | ||
[[Файл:My4.png|слева]] | [[Файл:My4.png|слева]] | ||
[[Файл:Figure_3.png|слева]] | [[Файл:Figure_3.png|слева]] | ||
| − | + | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. | В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. | ||
| Строка 50: | Строка 41: | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
| + | Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях, часто с использованием BLAS. | ||
| + | |||
| + | В интернете можно найти и частные реализации на разных языках программирования, например: | ||
| + | |||
| + | Есть реализация алгоритма, выложенная на Питоне: | ||
| + | https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e | ||
| + | |||
| + | Есть реализация под MatLab: | ||
| + | https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations | ||
| + | |||
| + | Вот реализация под язык R: | ||
| + | https://rpubs.com/aaronsc32/qr-decomposition-householder | ||
| + | |||
== Литература == | == Литература == | ||
Версия 23:51, 16 ноября 2021
Содержание
- 1 Свойства и структура алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
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.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях, часто с использованием BLAS.
В интернете можно найти и частные реализации на разных языках программирования, например:
Есть реализация алгоритма, выложенная на Питоне: https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e
Есть реализация под MatLab: https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations
Вот реализация под язык R: https://rpubs.com/aaronsc32/qr-decomposition-householder
