https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/api.php?action=feedcontributions&feedformat=atom&user=%D0%98%D0%BB%D1%8C%D1%8F+%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2%28%D0%92%D0%A2%D0%9C%2C+403%29 2026-10-23T01:33:41Z Вклад MediaWiki 1.43.5 https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28720 2021-11-16T22:42:57Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> <br /> <br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> <br /> ==== Реализация без распараллеливания ====<br /> Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Она написана с помощью библиотеки cblas - <br /> оболочки замечательной фортрановской библиотеки BLAS для си. Это для одного процесса,<br /> нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции<br /> из cblas на 52-58 строке. После факторизации производится проверка ||Q * R - A|| / ||A||. Q - ортогональная матрица, R -<br /> верхняя треугольная. Их вычисление цель реализации алгоритма. Ну и Q * R должно примерно равняться A, это следует из теории.<br /> Вернее, без погрешности вычисления, в точности Q * R = A. Вычисленный порядок погрешности на персональном компьютере<br /> примерно 10^(-14), что есть довольно хорошо.<br /> <br /> <br /> [[Файл:Code1.png|слева]]<br /> [[Файл:Code2.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> ==== Распараллеленная реализация ====<br /> А это распараллеленная реализация. Распараллеливание осуществляется при помощи библиотекки open MPI. Данные у каждого процесса <br /> свои. Они пересылаются друг другу, что и следует из названия библиотеки: &quot;Message passing interface&quot;. В этой реализации проверка<br /> ||Q*R - A|| / ||A|| выполняется только при условии, что размер матрицы кратен числу процессов. Написать проверку в этом случае<br /> сложнее из-за того, что нужно пересылать размер отдела матрицы, которую обрабатывает процесс (а он, вообще говоря, может отличаться<br /> у разных процессво, пусть и не более чем на единицу).<br /> &lt;br&gt;&lt;br&gt;<br /> В изначальной версии программы ядром (тем, что занимает бОльшую часть времени при исполнении) являлась, как ни странно,<br /> пересылка между процессами. Это узкое место было исправлено: рассылка одного процесса всем остальным стала исполняться<br /> не при помощи функции MPI_Isend, а при помощи специальной функции - MPI_Bcast. Начальная версия программы, хоть и работала,<br /> но не только не приносила выигрыша в скорости, но даже замедляла распараллеленную версию относительно исходной, однопроцессной. <br /> <br /> [[Файл:Code3.png|Слева]]<br /> [[Файл:Code4.png|Слева]]<br /> [[Файл:Code5.png|Слева]]<br /> [[Файл:Code6.png|Слева]]<br /> <br /> <br /> <br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментальных<br /> запусков программы на суперкомпьютере &quot;Ломоносов-2&quot;.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям. <br /> <br /> Можно найти и много пользовательских реализаций:<br /> <br /> На языке Python:<br /> https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/<br /> &lt;br&gt;<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> На языке R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder - R<br /> <br /> Для MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> == Литература ==<br /> В. Б. Андреев: &quot;Численные методы&quot;</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28719 2021-11-16T22:33:17Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> <br /> <br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> <br /> ==== Реализация без распараллеливания ====<br /> Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Она написана с помощью библиотеки cblas - <br /> оболочки замечательной фортрановской библиотеки под си. Это для одного процесса,<br /> нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции<br /> из cblas на 52-58 строке. После факторизации производится проверка - подсчет погрешности отношения нормы<br /> разности произведения вычисленных Q и R матриц и изначальной A-матрицы к норме матрицы A. Вычисленный <br /> порядок погрешности на персональном компьютере примерно 10^(-14), что есть довольно хорошо.<br /> <br /> <br /> [[Файл:Code1.png|слева]]<br /> [[Файл:Code2.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> ==== Распараллеленная реализация ====<br /> А это распараллеленная реализация. Распараллеливание осуществляется при помощи библиотекки open MPI. Данные у каждого процесса процесса<br /> свои. Они пересылаются друг другу, что и следует из названия библиотеки: &quot;Message passing interface&quot;. В этой реализации проверка<br /> ||Q*R - A|| / ||A|| выполняется только при условии, что размер матрицы кратен числу процессов. Написать проверку в этом случае<br /> сложнее из-за того, что нужно пересылать размер отдела матрицы, которую обрабатывает процесс (а он, вообще говоря, может быть разным по размеру,<br /> пусть и отличается не более чем на единицу).<br /> &lt;br&gt;&lt;br&gt;<br /> В изначальной версии программы ядром (тем, что занимает бОльшую часть времени при исполнении) являлась, как ни странно,<br /> пересылка между процессами. Это узкое место было исправлено: рассылка одного процесса всем остальным стала исполняться<br /> не при помощи функции MPI_Isend, а при помощи специальной функции - MPI_Bcast. Начальная версия программы, хоть и работала,<br /> но не только не приносила выигрыша в скорости, но даже замедляла распараллеленную версию относительно исходной, однопроцессной. <br /> <br /> [[Файл:Code3.png|Слева]]<br /> [[Файл:Code4.png|Слева]]<br /> [[Файл:Code5.png|Слева]]<br /> [[Файл:Code6.png|Слева]]<br /> <br /> <br /> <br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям. <br /> <br /> Можно найти и много пользовательских реализаций:<br /> <br /> На языке Python:<br /> https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/<br /> &lt;br&gt;<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> На языке R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder - R<br /> <br /> Для MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> == Литература ==<br /> В. Б. Андреев: &quot;Численные методы&quot;</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28718 2021-11-16T22:19:23Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> <br /> <br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Она написана с помощью библиотеки cblas - <br /> оболочки замечательной фортрановской библиотеки под си. Это для одного процесса,<br /> нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции<br /> из cblas на 52-58 строке. После факторизации производится проверка - подсчет погрешности отношения нормы<br /> разности произведения вычисленных Q и R матриц и изначальной A-матрицы к норме матрицы A. Вычисленный <br /> порядок погрешности на персональном компьютере примерно 10^(-14), что есть довольно хорошо.<br /> <br /> <br /> [[Файл:Code1.png|слева]]<br /> [[Файл:Code2.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> А это распараллеленная реализация. Распараллеливание осуществляется при помощи библиотекки open MPI. Данные у каждого процесса процесса<br /> свои. Они пересылаются друг другу, что и следует из названия библиотеки: &quot;Message passing interface&quot;. В этой реализации проверка<br /> ||Q*R - A|| / ||A|| выполняется только при условии, что размер матрицы кратен числу процессов. Написать проверку и в этом случае<br /> сложнее из-за того, что нужно пересылать размер отдела матрицы, которую обрабатывает процесс (а он, вообще говоря, может быть разным по размеру,<br /> пусть и отличается не более чем на единицу).<br /> <br /> [[Файл:Code3.png|Слева]]<br /> [[Файл:Code4.png|Слева]]<br /> [[Файл:Code5.png|Слева]]<br /> [[Файл:Code6.png|Слева]]<br /> <br /> <br /> <br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям. <br /> <br /> Можно найти и много пользовательских реализаций:<br /> <br /> На языке Python:<br /> https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/<br /> &lt;br&gt;<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> На языке R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder - R<br /> <br /> Для MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> == Литература ==<br /> В. Б. Андреев: &quot;Численные методы&quot;</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28717 2021-11-16T22:15:00Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> <br /> <br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Это для одного процесса,<br /> нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции<br /> из cblas на 52-58 строке. После факторизации производится проверка - подсчет погрешности отношения нормы<br /> разности произведения вычисленных Q и R матриц и изначальной A-матрицы к норме матрицы A. Вычисленный <br /> порядок погрешности на персональном компьютере примерно 10^(-14), что есть довольно хорошо.<br /> <br /> <br /> [[Файл:Code1.png|слева]]<br /> [[Файл:Code2.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> А это распараллеленная реализация. В ней проверка ||Q*R - A|| / ||A|| выполняется только при условии, что размер<br /> матрицы кратен числу процессов. Написать проверку и в этом случае сложнее из-за того, что нужно пересылать размер<br /> отдела матрицы, которую обрабатывает процесс (а она, вообще говоря, может быть разной, пусть и отличается не более чем на<br /> единицу)<br /> <br /> [[Файл:Code3.png|Слева]]<br /> [[Файл:Code4.png|Слева]]<br /> [[Файл:Code5.png|Слева]]<br /> [[Файл:Code6.png|Слева]]<br /> <br /> <br /> <br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям. <br /> <br /> Можно найти и много пользовательских реализаций:<br /> <br /> На языке Python:<br /> https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/<br /> &lt;br&gt;<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> На языке R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder - R<br /> <br /> Для MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> == Литература ==<br /> В. Б. Андреев: &quot;Численные методы&quot;</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Code6.png&diff=28716 2021-11-16T22:08:48Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>код</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Code5.png&diff=28715 2021-11-16T22:08:14Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>код</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Code4.png&diff=28714 2021-11-16T22:07:40Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>код</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Code3.png&diff=28713 2021-11-16T22:07:00Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>код</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Code1.png&diff=28712 2021-11-16T21:56:42Z

<p>Илья Карандеев(ВТМ, 403): Илья Карандеев(ВТМ, 403) загрузил новую версию Файл:Code1.png</p> <hr /> <div>код</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28711 2021-11-16T21:45:42Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>== Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Это для одного процесса,<br /> нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции<br /> из cblas на 52-58 строке. После факторизации производится проверка - подсчет погрешности отношения нормы<br /> разности произведения вычисленных Q и R матриц и изначальной A-матрицы к норме матрицы A. Вычисленный <br /> порядок погрешности на персональном компьютере примерно 10^(-14), что есть довольно хорошо.<br /> <br /> <br /> [[Файл:Code1.png|слева]]<br /> [[Файл:Code2.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> <br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям. <br /> <br /> Можно найти и много пользовательских реализаций:<br /> <br /> На языке Python:<br /> https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/<br /> &lt;br&gt;<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> На языке R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder - R<br /> <br /> Для MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> == Литература ==<br /> В. Б. Андреев: &quot;Численные методы&quot;</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28710 2021-11-16T21:36:52Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>== Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Это для одного процесса,<br /> нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции<br /> из Blas на 52-58 строке.<br /> <br /> [[Файл:Code1.png|слева]]<br /> [[Файл:Code2.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> <br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям. <br /> <br /> Можно найти и много пользовательских реализаций:<br /> <br /> На языке Python:<br /> https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/<br /> &lt;br&gt;<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> На языке R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder - R<br /> <br /> Для MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> == Литература ==<br /> В. Б. Андреев: &quot;Численные методы&quot;</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Code2.png&diff=28709 2021-11-16T21:35:55Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>код</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28708 2021-11-16T21:29:17Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Это для одного процесса,<br /> нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции<br /> из Blas на 52-58 строке.<br /> <br /> [[Файл:Code1.png|слева]]<br /> [[Файл:Fig2.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> <br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям. <br /> <br /> Можно найти и много пользовательских реализаций:<br /> <br /> На языке Python:<br /> https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/<br /> &lt;br&gt;<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> На языке R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder - R<br /> <br /> Для MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> == Литература ==<br /> В. Б. Андреев: &quot;Численные методы&quot;</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Fig2.png&diff=28707 2021-11-16T21:17:05Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>код</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Code1.png&diff=28706 2021-11-16T21:15:15Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>код</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28705 2021-11-16T21:03:14Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>== Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям. <br /> <br /> Можно найти и много пользовательских реализаций:<br /> <br /> На языке Python:<br /> https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/<br /> &lt;br&gt;<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> На языке R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder - R<br /> <br /> Для MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> == Литература ==<br /> В. Б. Андреев: &quot;Численные методы&quot;</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28704 2021-11-16T20:59:27Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>== Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям. <br /> <br /> Можно найти и много пользовательских реализаций:<br /> <br /> На языке Python:<br /> https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> На языке R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder - R<br /> <br /> Для MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28703 2021-11-16T20:51:52Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>== Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> <br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях, часто с использованием BLAS.<br /> <br /> В интернете можно найти и частные реализации на разных языках программирования, например: <br /> <br /> Есть реализация алгоритма, выложенная на Питоне:<br /> https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e<br /> <br /> Есть реализация под MatLab:<br /> https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations<br /> <br /> Вот реализация под язык R:<br /> https://rpubs.com/aaronsc32/qr-decomposition-householder<br /> <br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28702 2021-11-16T20:19:24Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>== Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> [[Файл:Figure_3.png|слева]]<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. <br /> Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.<br /> <br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Figure_3.png&diff=28701 2021-11-16T20:15:47Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>Проекция графика</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28700 2021-11-16T20:03:39Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;<br /> <br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот графики полученные по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My4.png|слева]]<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> <br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28699 2021-11-16T19:51:43Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50. То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц<br /> от 200 до 8500, выбранных более-менее произвольно. Вот графики полученные по результатам экспериментов.<br /> <br /> [[Файл:My.3.png|слева]]<br /> [[Файл:My.3.png|центр]]<br /> [[Файл:My4.png|центр]]<br /> <br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:My4.png&diff=28698 2021-11-16T19:51:06Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>Проекция графика</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:My.3.png&diff=28697 2021-11-16T19:49:36Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>Проекция графика</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28696 2021-11-16T19:45:59Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ. В первом эксперименте,<br /> эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в<br /> эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем,<br /> что в одном узле на суперкомпьютере &quot;Ломоносов-2&quot; 14 ядер, а доступное количество узлов автору было равным<br /> 50 То есть максимум можно было задействовать 700 ядер.<br /> <br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28695 2021-11-16T17:46:35Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. <br /> Оно проводилось на суперкомпьютере &quot;Ломоносов-2&quot; суперкомпьютерного комплекса МГУ.<br /> <br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> &lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;&lt;br&gt;<br /> <br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28694 2021-11-16T17:39:48Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> <br /> [[Файл:My1.png|мини]]<br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> [[Файл:Scale.png|мини|Масштабируемость]]<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28693 2021-11-16T17:39:09Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> <br /> [[Файл:My1.png|мини]]<br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> [[Файл:Scale.png|мини|Масштабируемость]]<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> [[Файл:My2.png.png|справа|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> <br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28692 2021-11-16T17:38:27Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> <br /> [[Файл:My1.png|мини]]<br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> [[Файл:Scale.png|мини|Масштабируемость]]<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> [[Файл:My2.png.png|центр|Обычная шкала]]<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> <br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28691 2021-11-16T17:37:28Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> <br /> [[Файл:My1.png|мини]]<br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> [[Файл:Scale.png|мини|Масштабируемость]]<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> [[Файл:My1.png|слева|Логарифмическая шкала]]<br /> [[Файл:My2.png.png|центр|Логарифмическая шкала]]<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> <br /> <br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:My2.png.png&diff=28690 2021-11-16T16:28:02Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>Обычная шкала</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28689 2021-11-16T16:24:40Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> <br /> [[Файл:My1.png|мини]]<br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> [[Файл:Scale.png|мини|Масштабируемость]]<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> [[Файл:My1|мини|слева|Логарифмическая шкала]]<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> <br /> <br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28688 2021-11-16T16:19:22Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div><br /> [[Файл:My1.png|мини]]<br /> == Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> [[Файл:Scale.png|мини|Масштабируемость]]<br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> [[Файл:My1|мини|слева|Логарифмическая шкала]]<br /> <br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:My1.png&diff=28687 2021-11-16T16:16:26Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>Логарифмическая шкала</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28686 2021-11-16T16:08:04Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>== Свойства и структура алгоритма ==<br /> == Программная реализация алгоритма ==<br /> <br /> <br /> <br /> <br /> === Особенности реализации последовательного алгоритма ===<br /> === Локальность данных и вычислений ===<br /> === Возможные способы и особенности параллельной реализации алгоритма ===<br /> === Масштабируемость алгоритма и его реализации ===<br /> === Динамические характеристики и эффективность реализации алгоритма ===<br /> === Выводы для классов архитектур ===<br /> === Существующие реализации алгоритма ===<br /> == Литература ==</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28685 2021-11-16T15:31:46Z

<p>Илья Карандеев(ВТМ, 403): </p> <hr /> <div>https://algowiki-project.org/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&amp;action=edit#</div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)/QR-%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%A5%D0%B0%D1%83%D1%81%D1%85%D0%BE%D0%BB%D0%B4%D0%B5%D1%80%D0%B0&diff=28668 2021-11-07T12:12:30Z

<p>Илья Карандеев(ВТМ, 403): Создана пустая страница</p> <hr /> <div></div>

Илья Карандеев(ВТМ, 403) https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%98%D0%BB%D1%8C%D1%8F_%D0%9A%D0%B0%D1%80%D0%B0%D0%BD%D0%B4%D0%B5%D0%B5%D0%B2(%D0%92%D0%A2%D0%9C,_403)&diff=28601 2021-10-20T14:21:53Z

<p>Илья Карандеев(ВТМ, 403): Новая страница: «QR-разложение методом Хаусхолдера»</p> <hr /> <div>QR-разложение методом Хаусхолдера</div>

Илья Карандеев(ВТМ, 403)