Алговики - Вклад [ru]

Обсуждение участника:ASA

2021-04-07T11:55:01Z

AntonChupin:

== Запрос ==
Здравствуйте, можно мне повышенные права (хотя бы патрулирующего, но потяну и администратора)? Я редактирую Алговики давно и сам использую её в своей работе, хотел бы присматривать за качеством на более высоком уровне. --[[Участник:AntonChupin|AntonChupin]] ([[Обсуждение участника:AntonChupin|обсуждение]]) 14:55, 7 апреля 2021 (MSK)

Категория:Незаконченные статьи

2021-04-07T11:46:32Z

AntonChupin: Новая страница: «Категория:Статьи по готовности»

[[Категория:Статьи по готовности]]

Шаблон:Project internals nav

2021-04-07T11:46:06Z

AntonChupin: лучше так

{{blue box|{{PAGENAME}}|2=<nowiki/>
{{(}}{{!}} border=0 cellspacing=10em
{{!}} {{#switch: {{PAGENAME}} | Общий форум = [[File:Group font awesome.svg{{!}}48px]] | Технический форум = [[File:Wrench font awesome.svg{{!}}48px]] | Справка = [[File:Question sign font awesome.svg{{!}}48px]]}}
{{!}} width=100% align=center {{!}} {{#switch: {{PAGENAME}} | Общий форум = Обсуждение любых связанных с Алговики тем. | Технический форум = Обсуждение технических вопросов, связанных с работой Алговики. | Справка = Помощь в редактировании статей, а также правила и руководства проекта Алговики.}}
{{!}} {{#switch: {{PAGENAME}} | Общий форум = [[File:Group font awesome.svg{{!}}48px]] | Технический форум = [[File:Wrench font awesome.svg{{!}}48px]] | Справка = [[File:Question sign font awesome.svg{{!}}48px]]}}
{{!}}-
{{!}} colspan="3" style="font-size: 90%; text-align:center;" {{!}}
----
[[Алговики:Общий форум{{!}}Общий форум]] {{!}} [[Алговики:Технический форум{{!}}Технический форум]] {{!}} [[Алговики:Справка{{!}}Справка]]
{{!}}{{)}}
}}<includeonly>[[Категория:Algowiki:Служебные]]</includeonly><noinclude>[[Категория:Algowiki:Шаблоны]]</noinclude>

Алговики:Общий форум

2021-04-07T11:44:57Z

AntonChupin: пара вопросов

{{project internals nav}}
== Капча ==
При редактировании многих страниц появляется капча, иногда по несколько раз одновременно, что отнимает довольно много сил и времени. Можно с этим что-то сделать? Может, есть какой-то уровень участника, к которому не применяются данные меры (см. также заявку ниже)? [[Участник:AntonChupin|AntonChupin]] ([[Обсуждение участника:AntonChupin|обсуждение]]) 14:44, 7 апреля 2021 (MSK)

== Права ==
Где можно подать заявку на флаг патрулирующего? [[Участник:AntonChupin|AntonChupin]] ([[Обсуждение участника:AntonChupin|обсуждение]]) 14:44, 7 апреля 2021 (MSK)

== Обустраивание проекта ==
Админы, скопируйте пожалуйста [https://ru.wikipedia.org/wiki/MediaWiki:Edittools] в [[MediaWiki:Edittools]] - удобнее работать с текстом будет. [[Участник:AntonChupin|AntonChupin]] ([[Обсуждение участника:AntonChupin|обсуждение]]) 14:03, 8 июля 2016 (MSK)
: Сделано. — [[S:Contributions/Lineprinter|lineprinter]] 11:13, 1 ноября 2016 (MSK)

А можно подключить гаджеты? В частности, HotCat и CategoryTree для удобной работы с категориями. [[Участник:AntonChupin|AntonChupin]] ([[Обсуждение участника:AntonChupin|обсуждение]]) 12:28, 6 сентября 2019 (MSK)
: Вопрос повторяю. [[Участник:AntonChupin|AntonChupin]] ([[Обсуждение участника:AntonChupin|обсуждение]]) 14:44, 7 апреля 2021 (MSK)

== Список описаний алгоритмов ==

{{:Список описаний алгоритмов}}

== Словарик ==

{| class="wikitable"
!Русский
!English
|-
|алгоритм
|algorithm
|-
|вершина (графа)
|vertex
|-
|входные/выходные данные
|input/output data
|-
|вычислительная мощность
|computational power
|-
|вычислительное ядро (алгоритма)
|computational kernel
|-
|вычислительное ядро (процессора)
|computational core
|-
|вычислительный узел
|computational node
|-
|граф алгоритма
|algorithm graph
|-
|дуга (графа)
|edge
|-
|избыточные вычисления
|redundant computation
|-
|информационный граф
|information graph
|-
|каноническая ярусно-параллельная форма
|canonical parallel form
|-
|кэш-строка (строка кэш-памяти)
|cache line
|-
|локальность
|locality
|-
|макроструктура
|macro structure
|-
|масштабируемость
|scalability
|-
|метод сдваивания
|pairwise summation
|-
|накладные расходы
|overhead
|-
|параллельная сложность
|parallel complexity
|-
|последовательный (алгоритм, программа)
|serial (sequential)
|-
|последовательная сложность
|serial complexity
|-
|производительность
|performance
|-
|реализация
|implementation
|-
|ресурс параллелизма
|parallelism resource
|-
|сопроцессор
|co-processor
|-
|ускорение
|speedup
|-
|ускоритель
|accelerator
|-
|функциональное устройство
|functional unit
|-
|цикл (программы)
|loop
|-
|эффективность
|efficiency
|-
|ярус
|layer
|-
|ярусно-параллельная форма
|parallel form
|}

[[Категория:Всё]]

Категория:Криптографические алгоритмы

2021-04-07T11:40:37Z

AntonChupin: Новая страница: «Категория:Алгоритмы»

[[Категория:Алгоритмы]]

Категория:ЕМ-алгоритм

2021-04-07T11:40:25Z

AntonChupin: Новая страница: «Категория:Алгоритмы»

[[Категория:Алгоритмы]]

Категория:Assignments/Done/Преподаватель 2

2021-04-07T11:38:46Z

AntonChupin: Новая страница: «Категория:Assignments/Done»

[[Категория:Assignments/Done]]

QR-алгоритм, используемый в SCALAPACK

2021-04-07T11:37:34Z

AntonChupin:

{{level-a}}

'''QR-алгоритм, используемый в SCALAPACK''' - алгоритм, использующий все проверенные на настоящее время приёмы ускорения [[QR-алгоритм|QR-алгоритма]] для несимметричных ''вещественных'' матриц<ref>Алгоритм для неэрмитовых комплексных матриц в SCALAPACK отсутствует, есть только их приведение к хессенберговой форме</ref>. Включён своими частями в разные подпрограммы пакета SCALAPACK<ref name="SCALAEig">http://www.netlib.org/scalapack/slug/node63.html#SECTION04335100000000000000</ref>. Состоит из двух основных частей: [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме|ортогонально подобного приведения матрицы к хессенберговому виду]] и [[QR-алгоритм для хессенберговой матрицы, используемый в SCALAPACK|QR-итераций со сдвигами для хессенберговой матрицы]].

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

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

Суть базового QR-алгоритма заключается в итерационном приведении матрицы <math>A</math> к некоторой унитарно подобной ей матрице <math>A_N</math> при помощи QR-разложения. Матрица <math>A_N</math> является правой верхней треугольной (или блочно треугольной) матрицей, а значит ее диагональ содержит собственные значения (в блочном случае собственные значения матрицы являются собственными значениями диагональных блоков). В силу подобия матриц <math>A</math> и <math>A_N</math> их наборы собственных значений совпадают. Таким образом, задача поиска собственных значений матрицы <math>A</math> сводится к задаче выведения матрицы <math>A_N</math> и поиска собственных значений для нее.

== Математическое описание ==

Известно<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref>, что произвольная квадратная матрица может быть представлена в виде произведения унитарной (''в вещественном случае ортогональной'') и верхней треугольной матриц. Такое разложение называется [[QR-разложения плотных неособенных матриц|QR-разложением]].

Пусть <math>A_0 = A</math> — исходная матрица.
Для <math>k = 0, 1, 2, \ldots</math> выполняется QR-разложение:
* <math>A_{k} = Q_kR_k</math>, где <math>Q_k</math> — унитарная (''ортогональная'') матрица, <math>R_k</math> — верхняя треугольная матрица, и затем найденные матрицы перемножаются в обратном порядке:
* <math>A_{k+1} = R_kQ_k</math>.

Поскольку <math>A_{k+1} = R_kQ_k = Q_k^{*}A_{k}Q_k</math>, то матрицы <math>A_{k+1}</math> и <math>A_k</math> унитарно подобны для любого <math>k</math>. Поэтому матрицы <math>A_1, A_2, \ldots</math> унитарно подобны исходной матрице <math>A</math> и имеют те же собственные значения.

Существуют доказательства<ref name="VOLA" /> сходимости получающихся матриц к клеточной правой треугольной матрице с диагональными клетками, размеры которых зависят от размеров канонических ящиков Жордана исходной матрицы. Таким образом, проблема собственных значений матрицы сводится к проблемам собственных значений матриц меньшего размера.

=== Особенности вещественного варианта QR-алгоритма ===

Если вещественная матрица <math>A</math> имеет различные вещественные собственные значения, то QR-алгоритм сходится к матрице с верхней треугольной формой, на диагонали которой находятся собственные значения. Однако вещественная матрица может иметь комплексные собственные значения, и тогда алгоритм будет сходиться не к верхней треугольной матрице, а к блочной верхней треугольной матрице, которая на диагонали содержит блоки 1-го и 2-го порядка. Блоки 1-го порядка будут содержать различные вещественные собственные значения, блоки 2-го порядка соответствуют парам комплексных сопряженных собственных значений<ref name = "Dem"> Деммель Д. Вычислительная линейная алгебра. – 2001. - С.261-264. </ref><ref>R. Granat, Bo Kagstrom, D. Kressner "LAPACK Working Note #216: A novel parallel QR algorithm for hybrid distributed memory HPC systems".</ref>.

<math>A_N=
\begin{bmatrix}
\blacksquare& \bullet& \bullet& \cdots& \cdots& \cdots& \cdots& \cdots& \bullet\\
0& \blacksquare& \blacksquare& \bullet& \ddots& \ddots& \ddots& \ddots& \vdots\\
0& \blacksquare& \blacksquare& \bullet& \bullet& \ddots& \ddots& \ddots& \vdots\\
\vdots& 0& 0& \blacksquare& \bullet& \bullet& \ddots& \ddots& \vdots\\
\vdots& \ddots& 0& 0& \blacksquare& \bullet& \bullet& \ddots& \vdots\\
\vdots& \ddots& \ddots& 0& 0& \blacksquare& \blacksquare& \ddots& \vdots\\
\vdots& \ddots& \ddots& \ddots& 0& \blacksquare& \blacksquare& \ddots& \bullet\\
\vdots& \ddots& \ddots& \ddots& \ddots& \ddots& \ddots& \ddots& \bullet\\
0& \cdots& \cdots& \cdots& \cdots& \cdots& 0& 0& \blacksquare
\end{bmatrix}</math>.

=== Приёмы ускорения сходимости, используемые в алгоритме ===

Применение приёмов ускорения является существенной частью рассматриваемого здесь алгоритма. Приёмы делятся на две группы - приёмы ускорения одной итерации алгоритма и приёмы ускорения сходимости итерационного процесса, то есть уменьшения числа итераций.

==== Использование хессенберговой формы матрицы ====

Хессенбергова (почти треугольная) форма матрицы интересна в приложении к QR-алгоритму тем, что в случае, если <math>A_0 = A</math> имеет эту форму, то имеют её и все матрицы <math>A_k</math>. Если теперь посмотреть на методы [[QR-разложения плотных неособенных матриц]], то видно, что выполнение разложения <math>A_k = Q_kR_k</math> в случае плотной неособенной <math>A_k</math>требует (в последовательном варианте) <math>O(n^3)</math> операций, как и последующий процесс вычисления <math>A_{k+1} = R_kQ_k</math>. В случае же, если матрицы хессенберговы, то как [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме|QR-разложения плотных хессенберговых матриц]], так и вычисления <math>A_{k+1} = R_kQ_k</math> потребуют уже по <math>O(n^2)</math> операций. Это позволяет экономить довольно большие вычислительные ресурсы.

Кроме этого, известно, что в случае, если хессенбергова матрица содержит на нижней кодиагонали только ненулевые элементы, то все кратные собственные значения будут соответствовать одному ящику Жордана<ref name="VOLA" />. Это означает, что каждое собственное значение с геометрической кратностью выше 1 даст после точного приведения матрицы к хессенбергову виду нули на нижней кодиагонали, что сразу даёт возможность параллельно работать с несколькими диагональными блоками.

Поэтому начальное [[Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (почти треугольной) форме|ортогонально подобное приведение матрицы к хессенбергову виду]] является органически необходимой стартовой частью алгоритма<ref name="SCALAEig" />, несмотря на то, что оно выделено в пакете SCALAPACK в отдельную подпрограмму.

==== Сдвиги QR-алгоритма ====

QR-алгоритм со сдвигами позволяет сократить количество итераций, необходимых для сходимости<ref name="bahvalov">Бахвалов Н.С., Жидков Н.П., Кобельков. Г.М. "Численные методы"— 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.</ref>. Пусть у нас есть матрица <math>A_k</math>, тогда процесс перехода к матрице <math>A_{k+1}</math> выглядит следующим образом:

* На каждом шаге подбирается число <math>\nu_k</math> и ищется следующее QR-разложение: <math>A_k-\nu_kE=Q_kR_k</math>.
* Вычисляется матрица <math>A_{k+1}</math>: <math>A_{k+1} = R_kQ_k+\nu_kE</math>.

При этом сохраняется свойство подобия матриц <math>A_k</math> и <math>A_{k+1}</math>:

<math>A_{k+1} = R_kQ_k+\nu_kE=Q_{k}^{T}Q_kR_kQ_k+\nu_kE=Q_{k}^{T}(A_k-\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-Q_{k}^{T}(\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-\nu_kE+\nu_kE=Q_{k}^{T}A_kQ_k</math>.

Подбор параметра <math>\nu_k</math> в пакете SCALAPACK осуществляется в зависимости от элементов матрицы <math>A_k</math>. При алгоритме подбора параметров, известном, как ''правило Фрэнсиса''<ref name = "Dem" />, в качестве сдвигов выбираются для каждого из диагональных блоков собственные значения их нижних правых клеток размером 2х2, и среднее количество итераций для большинства матриц получается порядка 2 на одно собственное значение. Существуют, однако, матрицы, для которых правило Фрэнсиса не даёт сходимости, поэтому если по истечении 10 итераций с обычными сдвигами не получилось сходимости, применяют так называемые "особые сдвиги".

==== Неявное выполнение сдвигов ====

Чтобы не выполнять итерации в комплексной арифметике, выполняют т.н. неявный двойной сдвиг, давно описанный в литературе<ref name="VOLA" /><ref name = "Dem" />. При этом используются двусторонние подобные операции Хаусхолдера (отражения) 3го порядка. На первом шаге итерации формируют у хессенберговой формы выступ размера 2х2, а на последующих шагах с их же помощью выступ вытесняют вправо вниз.

==== Обнуление поддиагональных элементов (дефляция) и распараллеливание по блокам ====

После того, как под диагональю какой-либо элемент становится менее порогового значения, его можно считать равным нулю. Это даёт возможность применить разделение диагональных блоков матрицы, соседствующих с ним, и раздельное вычисление их собственных чисел. Этот приём называется '''дефляцией'''.
Благодаря обнулению поддиагональных элементов далее нахождение собственных чисел разделённых этими нулями хессенберговых блоков, расположенных на диагонали блочно-треугольной формы, можно производить раздельно. Если в библиотеке LAPACK, предшествующей библиотеке SCALAPACK, на каждой из итераций обрабатывался текущий диагональный блок максимальных размеров, то в алгоритме, используемом в SCALAPACK, все блоки размера больше, чем 3, обрабатываются на очередной итерации параллельно, что позволило ускорить процесс.

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

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

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

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

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

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

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

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

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

= Литература =
<references />

[[Категория:Статьи в работе]]
[[Категория:Алгоритмы для матриц]]
[[Категория:ScaLaPACK]]

[[en:QR algorithm as implemented in SCALAPACK]]

Категория:Нейронные сети

2021-04-07T11:36:42Z

AntonChupin: Новая страница: «Категория:Всё»

[[Категория:Всё]]

Категория:Комбинаторная геометрия

2021-04-07T11:36:22Z

AntonChupin: Новая страница: «Категория:Всё»

[[Категория:Всё]]

Категория:Геометрические алгоритмы

2021-04-07T11:35:51Z

AntonChupin: Новая страница: « Категория:Всё»

[[Категория:Всё]]

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

2021-04-07T11:35:02Z

AntonChupin: Новая страница: « Категория:Всё»

[[Категория:Всё]]

Категория:Assignments/Done/Chalker

2021-04-07T11:34:35Z

AntonChupin: Новая страница: «Категория:Assignments/Done»

[[Категория:Assignments/Done]]

Категория:Assignments/Done/Evgeny Mortikov

2021-04-07T11:33:48Z

AntonChupin: Новая страница: «Категория:Assignments/Done»

[[Категория:Assignments/Done]]

Категория:Assignments/Done/Kronberg

2021-04-07T11:33:15Z

AntonChupin: Новая страница: «Категория:Assignments/Done»

[[Категория:Assignments/Done]]

Категория:Assignments/Done/Konshin

2021-04-07T11:32:31Z

AntonChupin: Новая страница: «Категория:Assignments/Done»

[[Категория:Assignments/Done]]

Категория:Assignments/Done/Frolov

2021-04-07T11:32:08Z

AntonChupin: Новая страница: «Категория:Assignments/Done»

[[Категория:Assignments/Done]]

Категория:Assignments/Done/Dexter

2021-04-07T11:31:44Z

AntonChupin: Новая страница: «Категория:Assignments/Done»

[[Категория:Assignments/Done]]

Категория:Pages with syntax highlighting errors

2021-04-07T11:31:23Z

AntonChupin: Новая страница: «Категория:Algowiki:Служебные»

[[Категория:Algowiki:Служебные]]

Категория:Algowiki:Служебные

2021-04-07T11:30:00Z

AntonChupin: Новая страница: «Эта категория для страниц и категорий, предназначенных для технического обслуживания А...»

Эта категория для страниц и категорий, предназначенных для технического обслуживания Алговики (не для читателей).

[[Категория:Всё]]

Категория:Algowiki:Шаблоны

2021-04-07T11:29:07Z

AntonChupin: Новая страница: «Эта категория содержит все шаблоны (специальные страницы, которые можно включать в друг...»

Эта категория содержит все шаблоны (специальные страницы, которые можно включать в другие статьи) Алговики.

[https://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F%3A%D0%92%D1%81%D0%B5+%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B&from=&to=&namespace=10 Автоматический список]

[[Категория:Algowiki:Служебные]]

Шаблон:Project internals nav

2021-04-07T11:27:53Z

AntonChupin:

{{blue box|{{PAGENAME}}|2=<nowiki/>
{{(}}{{!}} border=0 cellspacing=10em
{{!}} {{#switch: {{PAGENAME}} | Общий форум = [[File:Group font awesome.svg{{!}}48px]] | Технический форум = [[File:Wrench font awesome.svg{{!}}48px]] | Справка = [[File:Question sign font awesome.svg{{!}}48px]]}}
{{!}} width=100% align=center {{!}} {{#switch: {{PAGENAME}} | Общий форум = Обсуждение любых связанных с Алговики тем. | Технический форум = Обсуждение технических вопросов, связанных с работой Алговики. | Справка = Помощь в редактировании статей, а также правила и руководства проекта Алговики.}}
{{!}} {{#switch: {{PAGENAME}} | Общий форум = [[File:Group font awesome.svg{{!}}48px]] | Технический форум = [[File:Wrench font awesome.svg{{!}}48px]] | Справка = [[File:Question sign font awesome.svg{{!}}48px]]}}
{{!}}-
{{!}} colspan="3" style="font-size: 90%; text-align:center;" {{!}}
----
[[Алговики:Общий форум{{!}}Общий форум]] {{!}} [[Алговики:Технический форум{{!}}Технический форум]] {{!}} [[Алговики:Справка{{!}}Справка]]
{{!}}{{)}}
}}<includeonly>[[Категория:Algowiki:Служебное]]</includeonly><noinclude>[[Категория:Algowiki:Шаблоны]]</noinclude>

Категория:Неустойчивые параллельные методы

2021-04-07T11:24:14Z

AntonChupin:

'''Неустойчивые параллельные методы''', как правило, получены из последовательных устойчивых вычислительных схем с использованием каких-либо свойств, которые выполняются для точной арифметики, но не выполняются в условиях реальных компьютерных ошибок округления, например, ассоциативности и дистрибутивности.

[[Категория:Методы]]

Категория:Методы

2021-04-07T11:23:47Z

AntonChupin: Новая страница: « Категория:Всё»

[[Категория:Всё]]

Категория:Методы конструирования параллельных алгоритмов

2021-04-07T11:23:28Z

AntonChupin:

'''Методы конструирования параллельных алгоритмов''' - общие приёмы, с помощью которых на основе одних алгоритмов конструируются другие, специально для параллельных вычислительных систем.

[[Категория:Методы]]

Категория:Уровень метода

2021-04-07T11:22:59Z

AntonChupin:

'''Уровень метода''' в категории статьи означает, что в статье описан математический метод решения некоторой задачи. Для этого метода вполне возможно существование разных алгоритмов, реализующих его.

[[Категория:Статьи по уровню|Метод]]
[[Категория:Методы]]

[[en:Category:Method level]]

Категория:Задачи

2021-04-07T11:22:08Z

AntonChupin: Новая страница: « Категория:Всё»

[[Категория:Всё]]

Категория:Уровень алгоритма

2021-04-07T11:21:40Z

AntonChupin:

'''Уровень алгоритма''' в категории страницы означает, что на ней описан конкретный алгоритм, реализующий решение задачи некоторым методом.

[[Категория:Статьи по уровню|Алгоритм]]
[[Категория:Алгоритмы]]

[[en:Category:Algorithm level]]

Категория:Уровень задачи

2021-04-07T11:21:14Z

AntonChupin:

'''Уровень задачи''' в категории означает, что в статье описана задача, которую, возможно, решают несколько методов.

[[Категория:Статьи по уровню|Задача]]
[[Категория:Задачи]]

[[en:Category:Problem level]]

Категория:Статьи по уровню

2021-04-07T11:20:46Z

AntonChupin: Новая страница: « Категория:Всё»

[[Категория:Всё]]

Шаблон:Project internals nav

2021-04-07T11:19:57Z

AntonChupin: автокатегоризация

Категория:Уровень алгоритма

2021-04-07T11:19:11Z

AntonChupin:

'''Уровень алгоритма''' в категории страницы означает, что на ней описан конкретный алгоритм, реализующий решение задачи некоторым методом.

[[Категория:Статьи по уровню]]
[[Категория:Алгоритмы]]

[[en:Category:Algorithm level]]

Категория:Статьи по готовности

2021-04-07T11:18:21Z

AntonChupin: Отмена правки 15576, сделанной Lineprinter (обсуждение)но почему?

Подкатегории данной категории используются в шаблоне [[Шаблон:Main page/Readiness|Main page/Readiness]].

[[Категория:Всё]]

[[en:Category:Articles by readiness]]

Категория:Методы конструирования параллельных алгоритмов

2021-04-07T11:17:47Z

AntonChupin:

Алговики:Общий форум

2021-04-07T11:15:09Z

AntonChupin:

{{project internals nav}}
== Обустраивание проекта ==
Админы, скопируйте пожалуйста [https://ru.wikipedia.org/wiki/MediaWiki:Edittools] в [[MediaWiki:Edittools]] - удобнее работать с текстом будет. [[Участник:AntonChupin|AntonChupin]] ([[Обсуждение участника:AntonChupin|обсуждение]]) 14:03, 8 июля 2016 (MSK)
: Сделано. — [[S:Contributions/Lineprinter|lineprinter]] 11:13, 1 ноября 2016 (MSK)

А можно подключить гаджеты? В частности, HotCat и CategoryTree для удобной работы с категориями. [[Участник:AntonChupin|AntonChupin]] ([[Обсуждение участника:AntonChupin|обсуждение]]) 12:28, 6 сентября 2019 (MSK)

== Список описаний алгоритмов ==

{{:Список описаний алгоритмов}}

== Словарик ==

{| class="wikitable"
!Русский
!English
|-
|алгоритм
|algorithm
|-
|вершина (графа)
|vertex
|-
|входные/выходные данные
|input/output data
|-
|вычислительная мощность
|computational power
|-
|вычислительное ядро (алгоритма)
|computational kernel
|-
|вычислительное ядро (процессора)
|computational core
|-
|вычислительный узел
|computational node
|-
|граф алгоритма
|algorithm graph
|-
|дуга (графа)
|edge
|-
|избыточные вычисления
|redundant computation
|-
|информационный граф
|information graph
|-
|каноническая ярусно-параллельная форма
|canonical parallel form
|-
|кэш-строка (строка кэш-памяти)
|cache line
|-
|локальность
|locality
|-
|макроструктура
|macro structure
|-
|масштабируемость
|scalability
|-
|метод сдваивания
|pairwise summation
|-
|накладные расходы
|overhead
|-
|параллельная сложность
|parallel complexity
|-
|последовательный (алгоритм, программа)
|serial (sequential)
|-
|последовательная сложность
|serial complexity
|-
|производительность
|performance
|-
|реализация
|implementation
|-
|ресурс параллелизма
|parallelism resource
|-
|сопроцессор
|co-processor
|-
|ускорение
|speedup
|-
|ускоритель
|accelerator
|-
|функциональное устройство
|functional unit
|-
|цикл (программы)
|loop
|-
|эффективность
|efficiency
|-
|ярус
|layer
|-
|ярусно-параллельная форма
|parallel form
|}

[[Категория:Всё]]

Категория:Законченные статьи без перевода на английский язык

2021-04-07T11:14:06Z

AntonChupin:

Рабочая категория для редакторов, объединяет статьи, которые готовы к переводу.

[[Категория:Всё]]

Категория:Алгоритмы

2021-04-07T11:13:51Z

AntonChupin: Отмена правки 15589, сделанной Lineprinter (обсуждение)нужно

[[Категория:Всё]]

Категория:Assignments/Formal

2021-04-07T11:13:26Z

AntonChupin:

Задания, прошедшие предварительную проверку

[[Категория:Assignments]]

Категория:Assignments/Done

2021-04-07T11:13:11Z

AntonChupin:

Готовые студенческие задания

[[Категория:Assignments]]

Категория:Assignments

2021-04-07T11:11:28Z

AntonChupin: Новая страница: «Категория:Всё»

[[Категория:Всё]]

Категория:Algowiki:Справка

2021-04-07T11:11:12Z

AntonChupin: Отмена правки 15588, сделанной Lineprinter (обсуждение)почему нет?

[[Категория:Всё]]

Категория:Assignments/Awaiting

2021-04-07T11:10:42Z

AntonChupin:

Задания, ожидающие проверки

[[Категория:Assignments]]

Категория:Всё

2021-04-07T11:10:18Z

AntonChupin: нужна какая-то всё равно

Эта категория служит как корневая для всех категорий и страниц.

QR-алгоритм

2021-04-07T08:55:16Z

AntonChupin:

{{level-m}}

Авторы описания: [[Участник:Смирнова_Александра|Смирнова А.С.]] ([[QR-алгоритм#Математическое описание|Раздел 2]]), [[Участник:Frolov|Фролов А.В.]] (общая редактура и правка)

[[Спектральное разложение (нахождение собственных значений и векторов)|Задача нахождения собственных значений и собственных векторов]] для матрицы <math>A</math> заключается в поиске таких соответствующих друг другу чисел <math>\lambda</math> и ''ненулевых'' векторов <math>x</math>, которые удовлетворяют уравнению <math style="vertical-align:0%">Ax=\lambda x</math>, при этом числа <math>\lambda</math> называются собственными значениями, а вектора <math>x</math> - собственными векторами<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>.

Данная задача является одной из самых сложных задач линейной алгебры<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref>. Собственные вектора и собственные значения применяются в различных областях науки: в аналитической геометрии, при решении систем интегральных уравнений, в математической физике. Однако не существует прямых методов вычисления собственных значений для матриц общего вида, поэтому данная задача на практике решается численными итерационными методами. Одним из них является '''QR-алгоритм'''.

== Общее описание метода ==

'''QR-алгоритм''' — это численный '''метод''' в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел матрицы. При этом QR-алгоритм позволяет найти сразу и собственные вектора матрицы. Он был разработан в конце 1950-х годов независимо В.Н. Кублановской(Россия)<ref>Кублановская В.Н. О некоторых алгоритмах для решения полной проблемы собственных значений // Ж. вычисл.
матем. и матем. физ. 1961. Т. 1. № 4. С. 555–570</ref> и Дж. Фрэнсисом(Англия)<ref>J.G.F. Francis, "The QR Transformation, I", ''The Computer Journal'', 1961, vol. 4, no. 3, pp. 265-271</ref>. Открытию QR-алгоритма предшествовал LR-алгоритм, который использовал LU-разложение вместо QR-разложения. В настоящее время LR-алгоритм используется очень редко ввиду своей меньшей эффективности, однако он был важным шагом на пути к открытию QR-алгоритма<ref>[https://en.wikipedia.org/wiki/QR_algorithm Wikipedia: QR-algorithm]</ref>. В настоящее время под QR-алгоритмом понимается не только исходно разработанный В.Н.Кублановской и Дж. Фрэнсисом алгоритм, но и всю совокупность более поздних приёмов его ускорения.

Суть базового QR-алгоритма заключается в итерационном приведении матрицы <math>A</math> к некоторой унитарно подобной ей матрице <math>A_N</math> при помощи QR-разложения. Матрица <math>A_N</math> является правой верхней треугольной матрицей, а значит ее диагональ содержит собственные значения. В силу подобия матриц <math>A</math> и <math>A_N</math> их наборы собственных значений совпадают. Таким образом задача поиска собственных значений матрицы <math>A</math> сводится к задаче выведения матрицы <math>A_N</math> и поиска собственных значений для нее, что является тривиальной задачей.

== Математическое описание базового метода ==

Известно, что произвольная квадратная матрица может быть представлена в виде произведения унитарной (''в вещественном случае ортогональной'') и верхней треугольной матриц. Такое разложение называется [[QR-разложения плотных неособенных матриц|QR-разложением]].

Пусть <math>A_0 = A</math> — исходная матрица.
Для <math>k = 0, 1, 2, \ldots</math> выполняется QR-разложение:
* <math>A_{k} = Q_kR_k</math>, где <math>Q_k</math> — унитарная (''ортогональная'') матрица, <math>R_k</math> — верхняя треугольная матрица, и затем найденные матрицы перемножаются в обратном порядке:
* <math>A_{k+1} = R_kQ_k</math>.

Поскольку <math>A_{k+1} = R_kQ_k = Q_k^{*}A_{k}Q_k</math>, то матрицы <math>A_{k+1}</math> и <math>A_k</math> унитарно подобны для любого <math>k</math>. Поэтому матрицы <math>A_1, A_2, \ldots</math> унитарно подобны исходной матрице <math>A</math> и имеют те же собственные значения.

В специальной литературе по численным методам приводится доказательство<ref name="VOLA" /> сходимости получающихся матриц к клеточной правой треугольной матрице с диагональными клетками, размеры которых зависят от размеров канонических ящиков Жордана исходной матрицы. Таким образом, проблема собственных значений матрицы сводится к проблемам собственных значений матриц меньшего размера. QR-алгоритм в узком смысле и есть эта процедура. Однако обычно к нему относят не только её, но и весь комплекс приёмов ускорения этого итерационного метода.

=== Особенности вещественного несимметричного варианта QR-алгоритма ===

Если вещественная матрица <math>A</math> имеет различные вещественные собственные значения, то, как было описано ранее, QR-алгоритм сходится к матрице с верхней треугольной формой, на диагонали которой находятся собственные значения. Однако вещественная матрица может иметь комплексные собственные значения. В данном случае алгоритм будет сходиться не к верхней треугольной матрице, а к блочной верхней треугольной матрице, которая на диагонали содержит блоки 1-го и 2-го порядка. Блоки 1-го порядка содержат различные вещественные собственные значения, блоки 2-го порядка соответствуют парам комплексных сопряженных собственных значений<ref name = "Dem"> Деммель Д. Вычислительная линейная алгебра. – 2001. - С.261-264. </ref>.

<math>A_N=
\begin{bmatrix}
\blacksquare& \bullet& \bullet& \cdots& \cdots& \cdots& \cdots& \cdots& \bullet\\
0& \blacksquare& \blacksquare& \bullet& \ddots& \ddots& \ddots& \ddots& \vdots\\
0& \blacksquare& \blacksquare& \bullet& \bullet& \ddots& \ddots& \ddots& \vdots\\
\vdots& 0& 0& \blacksquare& \bullet& \bullet& \ddots& \ddots& \vdots\\
\vdots& \ddots& 0& 0& \blacksquare& \bullet& \bullet& \ddots& \vdots\\
\vdots& \ddots& \ddots& 0& 0& \blacksquare& \blacksquare& \ddots& \vdots\\
\vdots& \ddots& \ddots& \ddots& 0& \blacksquare& \blacksquare& \ddots& \bullet\\
\vdots& \ddots& \ddots& \ddots& \ddots& \ddots& \ddots& \ddots& \bullet\\
0& \cdots& \cdots& \cdots& \cdots& \cdots& 0& 0& \blacksquare
\end{bmatrix}</math>.

Надо сказать, что при применении QR-алгоритма к симметричным матрицам такой проблемы не возникает, поскольку у них нет комплексных собственных значений. Кроме этого, приведение к хессенберговой форме в силу симметрии автоматически даст трёхдиагональную форму и, как следствие, линейную сложность одной итерации, что существенно ускоряет исполнение в сравнении с матрицами общего вида. В существующих пакетах программ для того, чтобы не выполнять итерации в комплексной арифметике, выполняют т.н. неявный двойной сдвиг<ref name = "Dem" />.

== Ускорение сходимости QR-алгоритма ==

Применение приёмов ускорения даёт QR-алгоритму существенные преимущества перед альтернативными методами решения проблемы собственных значений. Приёмы делятся по своей сути на две группы - приёмы ускорения одной итерации алгоритма и приёмы ускорения сходимости итерационного процесса, то есть уменьшения числа итераций.

=== Использование хессенберговой формы матрицы ===

Хессенбергова (почти треугольная) форма матрицы интересна в приложении к QR-алгоритму тем, что в случае, если <math>A_0 = A</math> имеет эту форму, то имеют её и все матрицы <math>A_k</math>. Если теперь посмотреть на методы [[QR-разложения плотных неособенных матриц]], то видно, что выполнение разложения <math>A_k = Q_kR_k</math> в случае плотной неособенной <math>A_k</math>требует (в последовательном варианте) <math>O(n^3)</math> операций, как и последующий процесс вычисления <math>A_{k+1} = R_kQ_k</math>. В случае же, если матрицы хессенберговы, то как [[Методы QR-разложения плотных хессенберговых матриц|QR-разложения плотных хессенберговых матриц]], так и вычисления <math>A_{k+1} = R_kQ_k</math> потребуют уже по <math>O(n^2)</math> операций. Это позволяет экономить если не время (критические пути графа алгоритма линейны для лучших методов QR-разложения и для плотной матрицы, и для хессенберговой), то довольно большие вычислительные ресурсы.

Поэтому естественным приёмом ускорения итераций QR-алгоритма является начальное [[Разложения, содержащие хессенбергову матрицу, унитарно подобную исходной|унитарно подобное приведение матрицы к хессенбергову виду]]. После этого все процедуры QR-алгоритма следует проводить уже с матрицами хессенберговой формы.

В случае, если исходная матрица эрмитова (в вещественном случае - симметричная), то унитарно подобное приведение к хессенберговому виду становится [[Разложения, содержащие трёхдиагональную матрицу, унитарно подобную исходной|приведением к трёхдиагональному симметричному виду]]. В этом случае QR-алгоритм становится ещё
быстрее, благодаря существенно большему количеству нулей в структурах образующихся матриц..

=== Сдвиги QR-алгоритма ===

QR-алгоритм со сдвигами позволяет сократить количество итераций, необходимых для сходимости<ref name="bahvalov">Бахвалов Н.С., Жидков Н.П., Кобельков. Г.М. "Численные методы"— 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.</ref>. Пусть у нас есть матрица <math>A_k</math>, тогда процесс перехода к матрице <math>A_{k+1}</math> выглядит следующим образом:

* На каждом шаге подбирается число <math>\nu_k</math> и ищется следующее QR-разложение: <math>A_k-\nu_kE=Q_kR_k</math>.
* Вычисляется матрица <math>A_{k+1}</math>: <math>A_{k+1} = R_kQ_k+\nu_kE</math>.

При этом сохраняется свойство подобия матриц <math>A_k</math> и <math>A_{k+1}</math>:

<math>A_{k+1} = R_kQ_k+\nu_kE=Q_{k}^{T}Q_kR_kQ_k+\nu_kE=Q_{k}^{T}(A_k-\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-Q_{k}^{T}(\nu_kE)Q_k+\nu_kE=Q_{k}^{T}A_kQ_k-\nu_kE+\nu_kE=Q_{k}^{T}A_kQ_k</math>.

Подбор параметра <math>\nu_k</math> осуществляется в зависимости от элементов матрицы <math>A_k</math>. При алгоритме подбора параметров, известном, как ''правило Фрэнсиса'', среднее количество итераций для большинства матриц получается порядка 2 на одно собственное значение. Существуют, однако, матрицы, для которых правило Фрэнсиса не даёт сходимости, поэтому если по истечении 10 итераций с обычным сдвигом не получилось сходимости, применяют так называемые "особые сдвиги". Для симметрического же случая используется стратегия Уилкинсона<ref name = "Dem" />.

Указанные стратегии выбора сдвигов используется в программах библиотек LAPACK и SCALAPACK. Но они не являются наилучшими, поскольку для выбора новых сдвигов нужно провести предшествующие итерации до конца. Поэтому в публикациях XXI века уже появились описания т.н. многосдвиговых итераций. В этой стратегии выбор сдвигов также выполняется с помощью собственных чисел подматриц из нижнего правого угла обрабатываемых блоков, но их размерность уже берётся больше, чем 2<ref>R. Granat, Bo Kagstrom, D. Kressner "LAPACK Working Note #216: A novel parallel QR algorithm for hybrid distributed memory HPC systems".</ref>.

=== Неявное проведение итераций ===

Q-теорема<ref name = "Dem" /> помогает не вычислять в явном виде требуемые матрицы с их последующим перемножением, а выполнять эти операции неявно. При этом в соответствии с [[QR-алгоритм#Особенности вещественного несимметричного варианта QR-алгоритма|особенностями вещественного случая несимметричных матриц]] удаётся выполнять т.н. неявный двойной сдвиг с использованием двух комплексно сопряжённых сдвигов (например, из правила Фрэнсиса), оставаясь в рамках вещественной арифметрики, с помощью выполнения двусторонними преобразованиями Хаусхолдера т.н. вытеснения выступа. В вещественном случае аналогично (но с преимуществами симметрии) выполняется неявный одинарный сдвиг, вытеснением выступа двусторонними преобразованиями вращения (Гивенса).

=== Обнуление поддиагональных элементов (дефляция) ===

После того, как под диагональю какой-либо элемент становится менее порогового значения, его считают равным нулю. Это даёт возможность применить разделение диагональных блоков матрицы, соседствующих с ним, и раздельное вычисление их собственных чисел. Приём называется '''дефляцией'''.

== QR-алгоритм в различных вариантах ==

В классическом (без приёмов ускорения) виде QR-алгоритм не применяется из-за медленности. Варианты метода, в основном, используются для матриц разного вида:

=== Метод для матриц общего вида ===

[[QR-алгоритм, используемый в SCALAPACK]] для решения проблемы собственных значений у матриц общего вида в настоящее время использует тот подход к выбору сдвигов, который не подтверждён теоретически, но имел лучшие практические показатели на момент создания библиотеки LAPACK. Это выполнение процедуры "двойного сдвига" с величинами, равными собственным значениям последней диагональной клетки размера 2х2 у всех диагональных блоков, больших размером.
Поскольку существуют матрицы, для которых этот выбор сдвигов не даёт сходимости, то после 10й итерации при отсутствии уменьшения поддиагональных элементов выполняется некий "особый" сдвиг.

=== Метод для симметричных и эрмитовых матриц ===

В случае симметрии (для вещественных матриц) или эрмитовости (для комплексных) применяемый для решения проблемы собственных значений QR-алгоритм использует особенности как самой задачи (собственные числа таких матриц вещественны), так и получаемых промежуточных результатов (хессенберговы матрицы оказываются трёхдиагональными симметричными), что сокращает расчёты.
[[QR-алгоритм для симметричных матриц, используемый в SCALAPACK]] для решения проблемы собственных значений у симметричных матриц в настоящее время использует подход к выбору сдвигов, разработанный в начале 90-х гг. XX века<ref>G. HENRY, Improving Data Re-Use in Eigenvalue-Related Computations, PhD thesis, Cornell University, Ithaca, NY, January 1994</ref>.

=== Использование QR-алгоритма для нахождения сингулярных чисел ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Алгоритмы для матриц]]

[[en:QR algorithm]]

Спектральное разложение (нахождение собственных значений и векторов)

2021-04-07T08:14:30Z

AntonChupin:

{{level-p}}

== Математическая формулировка задачи ==

'''Задача нахождения собственных значений и собственных векторов''' для матрицы <math>A</math> заключается в поиске таких соответствующих друг другу чисел <math>\lambda</math> и ''ненулевых'' векторов <math>x</math>, которые удовлетворяют уравнению <math style="vertical-align:0%">Ax=\lambda x</math>. Числа <math>\lambda</math> называются собственными значениями, а вектора <math>x</math> - соответствующими им собственными векторами<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. Данная задача является одной из самых сложных задач линейной алгебры<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref>.

=== Истоки задачи ===

Собственные вектора и собственные значения применяются в различных областях науки: в аналитической геометрии, при решении систем интегральных уравнений, в математической физике. В частности, в случае приближения линейных операторов в конечных подпространствах собственные числа получаемых матриц могут приближать спектр таких операторов. Естественно, степень приближения в таких случаях должна быть исследована и обоснована.

=== Общие теоретические выкладки ===

Из <math style="vertical-align:0%">Ax=\lambda x</math> при ненулевом <math>x</math> следует вырожденность <math>A-\lambda E</math>. Поэтому, если для задачи нужны только собственные числа, то их можно найти как корни многочлена <math>det(A-\lambda E)</math>, называемого ''характеристическим многочленом'' матрицы <math>A</math>. Из невозможности выразить корни таких многочленов общего вида из его коэффициентов с помощью конечного числа арифметических операций следует, что не существует прямых методов вычисления собственных значений для матриц общего вида (кроме матриц размером менее 5). Поэтому проблема собственных значений на практике решается только итерационными методами.

=== Возможные вариации постановки задачи ===

В зависимости, от требований исходной задачи постановка может быть упрощена до нахождения всех или части собственных чисел с нахождением или без нахождения соответствующих им собственных векторов.

== Основные методы решения задачи ==

== Литература ==

[[Категория:Статьи в работе]]
[[Категория:Алгоритмы для матриц]]

[[en:Eigenvalue decomposition (finding eigenvalues and eigenvectors)]]

Алговики:Общий форум

2019-09-06T09:28:51Z

AntonChupin: /* Обустраивание проекта */

Быстрое дискретное преобразование Фурье (БПФ)

2016-11-21T08:33:35Z

AntonChupin:

{{Assignment|IgorS}}
Авторы: [[Участник:Chachba.A|Чачба А.Н.]], [[Участник:Weasel|Костоев Р.С.]]

[[Участник:Chachba.A|Чачба А.Н.]] заполнил половину всех заполненных пунктов (а именно 1.1, 1.2, 1.6, 1.8, 1.9) и построил информационный граф алгоритма, [[Участник:Weasel|Костоев Р.С.]] написал программу и провел серию запусков на суперкомпьютере и заполнил вторую половину пунктов. Оба после заполнения исправляли найденные ошибки во всех пунктах.

{{algorithm
| name = Быстрое преобразование Фурье (БПФ)
| serial_complexity = <math>O(N \log N)</math>
| pf_height = <math>O(\log N)</math>
| pf_width = <math>O(N)</math>
| input_data = <math>N</math>
| output_data = <math>N</math>
}}

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Преобразование Фурье - взаимно однозначное отображение одной функции <math>f</math> вещественной переменной, называемой таргетным сигналом, с другой функцией <math>\hat{f}</math> вещественной переменной, называемой образом Фурье, или спектром исходной функции, по формуле:

:<math>
\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx
</math>
Дискретное преобразование Фурье, в свою очередь, есть аналог непрерывного преобразования Фурье, но для дискретного сигнала, содержащего <math>N</math> отсчетов.
Широко применяется в цифровой обработке сигналов, теории вероятностей, криптографии и акустике.
Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое.
Преобразование Фурье имеет сложность <math>O(N^2)</math>, но существует быстрый вариант преобразование Фурье со сложностью <math>O(N\log{N})</math>.
Такая скорость достигается благодаря применению схемы «разделяй и властвуй». Общий вид преобразования позволяет разделить массив на несколько частей таким образом, что, применяя преобразование Фурье к отдельным его частям и объединяя специальным образом результаты (при помощи поворотных множителей и повторного применения преобразования), получать на выходе образ исходного вектора. Но благодаря разделению массива исходного размера на части суммарная асимптотическая сложность алгоритма уменьшается.

== Математическое описание алгоритма ==
Пусть исходный сигнал имеет значения <math>x_n,\quad n = 0,\dots,N-1</math>, тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:
:<math>
X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1
</math>
Обозначим <math> \varepsilon_{N} = e^{-\frac{2\pi i}{N}}</math>, тогда ДПФ можно перезаписать в матричной форме:
:<math>
\bar X = A\bar x
</math>
где матрица <math>A = \{\varepsilon_{N}^{(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>{k}</math> рекурсий на первом этапе и <math>m</math> на последнем этапе, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.

В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.

В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>. Так как рекурсия применяется каждый раз при отщеплении одного множителя, то можно заключить, что глубина рекурсии алгоритма составляет <math>O(n)</math>, где <math>n</math> — число множителей в факторизации <math>N</math>.

В свою очередь, если число <math>N</math> не факторизуется в произведение простых множителей (то есть <math>N</math> — простое число), то данный алгоритм напрямую не применим. На замену ему приходит алгоритм Радера, который в некотором смысле сводит задачу размерности <math>N</math> к подзадаче задаче размерности <math>N\pm 1</math> вычисления свертки, в которой допустимо и увеличение размерности до составных в том числе.

== Макроструктура алгоритма ==
Макроструктура БПФ для случая <math>N = km</math> описывается рекурсивно:
# <math>k</math> независимых преобразований векторов меньшей размерности <math>m</math>
#Умножение элементов на поворотные коэффициенты (<math>N</math> умножений)
# <math>m</math> обратных преобразований векторов размерностей <math>k</math>

== Схема реализации последовательного алгоритма ==
Рекурсивный метод для случая <math>N = 2^k</math>, без оптимизации на C++:
<nowiki>#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) {
int n = as.size();
if (n == 1) return vcd(1, as[0]);

vcd w(n); // Calculate roots
for (int i = 0; i < n; i++) {
double alpha = 2 * M_PI * i / n;
w[i] = cd(cos(alpha), sin(alpha));
}

vcd A(n / 2), B(n / 2);
for (int i = 0; i < n / 2; i++) {
A[i] = as[i * 2];
B[i] = as[i * 2 + 1];
}
vcd Av = fft(A);
vcd Bv = fft(B);
vcd res(n);
for (int i = 0; i < n; i++)
res[i] = Av[i % (n / 2)] +
w[i] * Bv[i % (n / 2)];
return res;
}
</nowiki>
В последовательном варианте можно бороться за улучшение константы сложности, предподсчитав значения соответствующих коэффициентов.

== Последовательная сложность алгоритма ==
Алгоритм состоит из трех этапов, следовательно если <math>N = \prod_{i = 1}^np_i</math>, то общая сложность составляет порядка <math>O(N\sum_{i=1}^np_i)</math> операций.

Пусть существует некоторое фиксированное число <math>P</math>, такое что:
:<math>
p_i \leq P \quad \forall i = 1...n,
</math>
тогда, учитывая, что <math>n \leq \log_{P}{N}</math>, сложность алгоритма можно записать в виде <math>O(N\log{N})</math>.

== Информационный граф ==
[[Файл:FourierGraph2.png|center|thumb|640px|'''Рисунок 1.''' Информационный граф преобразования Кули-Тьюки для <math>N = km = 25, k = 5, m = 5</math>. Желтые вершины - умножение на поворотные множители.]]

== Ресурс параллелизма алгоритма ==
В силу независимости всех рекурсивных вызовов и того факта, что путь максимальной длины в графе (так называемый критический путь) имеет порядок <math>O(\log{N})</math>, можно утверждать, что параллельная сложность алгоритма составит <math>O(\log{N})</math>.

''Замечание'': формально основание логарифма на каждом рекурсивном шаге зависит от множителя в факторизации <math>N</math>, потому использована О-символика.

При условии ограниченности количества доступных вычислительных узлов рекомендуется выбирать множители в разложении числа <math>N</math> близкими к числу доступных узлов, таким образом доступные ресурсы будут использованы максимально эффективно.

Итого алгоритм относится к логарифмическому классу алгоритмов по параллельной сложности.

== Входные и выходные данные алгоритма ==
'''Входные данные''':
Чаще всего для обработки сигналов в качестве входных данных для БПФ подается вектор размерности <math>N</math> вещественных элементов. Но БПФ работает и для случая элементов над комплексным полем. Таким образом, например, можно экономить на количестве применений БПФ в некоторой конкретной задаче путем приведения двух векторов вещественных чисел к одному вектору комплексных чисел с вещественной частью равной первому вектору и комплексной частью равной второму вектору:
<math>x, y</math> - исходные сигналы. Обозначим <math>z = x + iy</math>, а <math>F(k, x)</math> - это <math>k</math>-ый коэффициент образа Фурье вектора <math>x</math>. Тогда:

:<math>F(k, x) = \frac{F(k, z) + F(k, \bar z)}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - F(k, \bar z)}{2}</math>

Учитывая, что <math>F(k, \bar z) = \overline{F(N - k, z)}</math>, получаем:

:<math>F(k, x) = \frac{F(k, z) + \overline{F(N-k, z)}}{2}</math>
:<math>F(k, y) = -i\frac{F(k, z) - \overline{F(N-k,z)}}{2}</math>

Такой способ позволяет приблизительно в два раза уменьшить количество вычислений.

'''Выходные данные''':
Вектор размерности <math>N</math> комплексных чисел - спектр исходного сигнала.

== Свойства алгоритма ==
Матрица Вандермонда преобразования <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math> такая, что:
:<math>
A^{-1} = \frac{1}{N}A^*
</math>
Таким образом обратное преобразование Фурье с точностью до нормирующего множителя и сопряжения элементов матрицы совпадает с прямым.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

== Масштабируемость алгоритма и его реализации ==
Все запуски программы[http://pastebin.com/raw/xajKb9JN] проводились на с/к Blue Gene/P с использованием библиотеки Intel MKL.

IBM Blue Gene/P — массивно-параллельная вычислительная система, которая состоит из двух стоек, включающих 2048 четырехъядерных вычислительных узлов, с пиковой производительностью 27,9 терафлопс.

Характеристики системы:
* две стойки с вычислительными узлами и узлами ввода-вывода
* 1024 четырехъядерных вычислительных узла в каждой из стоек
* 16 узлов ввода-вывода в стойке (в текущей конфигурации активны 8, т.е. одна I/O-карта на 128 вычислительных узлов)
* программирование с использованием MPI, OpenMP/pthreads, POSIX I/O
* высокая энергоэффективность: ∼ 372 MFlops/W

Вычислительный узел включает в себя четырехъядерный процессор, 2 ГБ общей памяти и сетевые интерфейсы.

Вычислительной узел:
* четыре микропроцессорных ядра PowerPC 450 (4-way SMP)
* пиковая производительность: 4 ядра x 3,4 GFlop/sec на ядро = 13,6 GFlop/sec
* пропускная способность памяти: 13,6 GB/sec
* 2 ГБ общей памяти
* 2 x 4 МБ кэш-памяти 2-го уровня (в документации по BG/P носит название L3)
* легковесное ядро (compute node kernel, CNK), представляющее собой Linux-подобную операционную систему, поддерживающую значительное подмножество Linux-совместимых системных вызовов
* асинхронные операции межпроцессорных обменов (выполняются параллельно с вычислениями)
* операции ввода-вывода перенаправляются I/O-картам через сеть коллективных операций

[[Файл:Time.PNG|center|thumb|640px|'''Рисунок 2.''' Время выполнения параллельной реализации БПФ в секундах. Size - число элементов массива. Р - число использованных процессоров.]]

[[Файл:Efff.PNG|center|thumb|640px|'''Рисунок 3.''' Эффективность параллельной реализации БПФ. Size - число элементов массива. Р - число использованных процессоров. Эффективность в пределах от 0 до 1.]]

Как видно из графика, эффективность параллельной реализации резко падает с ростом количества используемых процессоров, связано это с увеличением количества накладных расходов.

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

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

== Существующие реализации алгоритма ==
* Самая популярная библиотека для работы с преобразованиями Фурье это [http://www.fftw.org FFTW]
* Реализация от Intel в рамках [//software.intel.com/en-us/intel-mkl Math Kernel Library]
* Реализация ДПФ на графических картах от NVidia - [//developer.nvidia.com/cufft cuFFT]

= Литература =
* Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
* Описание алгоритма на Википедии: [https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Быстрое преобразование Фурье]
* Материалы лекций по "Алгоритмам и структурам данных" Школы Анализа Данных Яндекса

Категория:Решение систем линейных уравнений

2016-07-08T13:31:29Z

AntonChupin:

[[Категория:Алгоритмы]]
[[Категория:Алгоритмы для матриц]]

Linpack benchmark

2016-07-08T13:31:09Z

AntonChupin:

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|2.4]])

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

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

'''Linpack benchmark''' является тестом, разработанным как приложение к библиотеке Linpack для тестирования производительности компьютерных систем. По сути это генерирование некоторой системы линейных алгебраических уравнений (СЛАУ) <math>A \vec{x} = \vec{b}</math> со случайной плотной квадратной матрицей <math>A</math> и вектором <math>\vec{b}</math> таким, чтобы решением был вектор <math>\vec{x}</math>, у которого все элементы равны 1, с последующим решением этой СЛАУ. Решение в силу неспецифичности (с рядом оговорок) матрицы делается в два этапа. Сначала для матрицы системы выполняется <math>PLU</math>-разложение (<math>P</math> — матрица перестановок, <math>L</math> — левая треугольная с единичными диагональными элементами, <math>U</math> — правая треугольная матрица) методом Гаусса с выбором ведущего элемента по столбцу. На втором этапе с помощью полученного разложения последовательно решается СЛАУ вида <math>P L U \vec{x} = \vec{b}</math>. На третьем этапе вычисляется невязка <math>\vec{r} = A \vec{x} - \vec{b}</math> и её характеристики, после чего выводятся данные о полученных точности и производительности вычислений. Интересно, что производительность вычисляется только для основной части алгоритма, т. е. туда не включены ни вычисление невязки, ни вычисление норм.

Не следует путать Linpack benchmark, разработанный для тестирования компьютеров традиционной архитектуры, и High Performance Linpack benchmark, который разработан для тестирования компьютерных систем с параллельной архитектурой и в основе которого лежит хоть и сходный, но другой алгоритм.

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

Исходные данные: невырожденная (ГСЧ подобран так, чтобы это обеспечивалось, в версии от 1992 г.) квадратная матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор правой части <math>\vec{b}</math> (элементы <math>b_i</math>). В реальности они не вполне входные (элементы матрицы генерирует псевдослучайно сама программа, все они находятся в диапазоне (-1/2, +1/2), <math>b_i = \sum\limits_{j = 1}^i a_{ij}</math>), но для разбора общей схемы алгоритма удобно считать их входными данными.

Вычисляемые данные: левая треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), правая треугольная матрица <math>U</math> (элементы <math>u_{ij}</math>), матрица перестановок <math>P</math> (вычисляется не в развёрнутом виде, а как набор номеров ведущих элементов), вектор решения <math>x</math> (элементы <math>x_i</math>).

Детальные формулы отдельных частей алгоритма здесь описывать не будем, поскольку они являются самостоятельными алгоритмами и их детальные описания должны быть выполнены раздельно. Поэтому здесь будет приведена только общая схема алгоритма.

Первая часть — разложение матрицы в произведение двух треугольных и матрицы перестановок: <math>A = P L U</math> — выполняется методом Гаусса с выбором ведущего элемента по столбцу. При этом матрица перестановок хранится с помощью вектора, характеризующего выполненные перестановки. Матрица <math>L</math> левая треугольная с единичными диагональными элементами, матрица <math>U</math> — правая треугольная.

Вторая часть состоит из двух решений треугольных СЛАУ. Сначала c помощью «прямой-обратной» подстановки решается система <math>L \vec{y} = P T \vec{b}</math>, затем с помощью обратной подстановки — система <math>U \vec{x} = \vec{y}</math>. При этом в тесте треугольные матрицы хранятся в соответствующих местах матрицы <math>A</math>. Поэтому перед началом третьей части её генерируют заново (с теми же стартовыми параметрами для ГСЧ).

Третья часть (для которой не измеряется скорость работы) состоит в вычислении сначала невязки решения <math>\vec{r} = A \vec{x} - \vec{b}</math> и затем её равномерной нормы, а также нормы решения. По окончании этой части алгоритм выдаёт данные по точности полученного решения, а также вычисляет производительность системы.

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

Основная часть алгоритма — разложение матрицы методом Гаусса с выбором ведущих элементов по столбцу — определяет основную часть операций. Следующая по значимости часть — вычисление невязки и её нормы — реализовано подпрограммой вычисления суммы вектора и произведения матрицы на другой вектор и функцией вычисления равномерной нормы. Третьи по значимости части — обратный ход метода Гаусса и «прямой-обратный» ход метода Гаусса.

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

Как уже записано в описании ядра алгоритма, разложение матрицы методом Гаусса с выбором ведущих элементов по столбцу — определяет основную часть операций и при этом является первой макрооперацией. После неё идёт «прямой-обратный» ход метода Гаусса и сразу за ним — обратный ход метода Гаусса. После повторного заполнения матрицы следующей макрооперацией является вычисление невязки решения СЛАУ, а затем — вычисление её и вектора решения равномерных норм.

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

Математическое описание алгоритма описано выше. При этом в стандартном тесте из-за того, что разложение Гаусса вычисляется на месте исходной матрицы, а также из-за того, что при прямом-обратном и обратном ходе решение заанимает место правой части, после вычисления решения приходится заново перевычислять как матрицу системы, так и правую часть — для последующего вычисления невязки. После вычисления невязки её норма в принципе может быть вычислена в любом порядке с нормой решения, это не влияет на алгоритм и его результаты.

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

Поскольку основной частью алгоритма является разложение Гаусса с выбором ведущего элемента по столбцу, то он, как и эта часть, относится к алгоритмам с ''кубической'' сложностью. Остальные части квадратичны по сложности и потому не дают сравнимого вклада в сложность алгоритма.

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

Граф состоит из информационных графов своих основных частей. Первая часть (метод Гаусса с выбором ведущего элемента по столбцу) имеет самый сложный из графов. На рис.1 отражён упрощённый граф этой части, post factum по результатам выборов ведущих элементов. Зеленым отображены операции определения максимумов, с запоминанием позиций. Желтым цветом выделено обращение очередного ведущего элемента, коричневым – умножения в текущем столбце, фиолетовым – операции <math>a b + c</math> в других столбцах. На рис.2 приведён граф одного из слоёв (одного шага метода). Обозначения – те же самые, что в полном графе. Пунктир означает рассылку данных из ведущей строки.

{| align="center"
|- valign="top"
| [[File:Gaussian elimination.png|700px|thumb|Рисунок 1. Упрощённый граф метода Гаусса с выбором ведущего элемента по столбцу]]
| [[File:Gaussian elimination step.png|500px|Рисунок 2. Граф одного шага метода Гаусса|thumb]]
|}

Вторая часть состоит из почти аналогичных фрагментов. Первый из них – «прямой ход», а именно решение СЛАУ с левой треугольной матрицей <math>L \vec{y} = \vec{b}</math> (рис.3). Диагональные элементы матрицы единичны, поэтому в этом куске нет операций деления. Все зелёные вершины отвечают операциям <math>a b + c</math>. Второй – «обратный ход», а именно решение СЛАУ с правой (верхней) треугольной матрицей <math>U \vec{x} = \vec{y}</math> (рис.4). Для её матрицы нет информации о специфичности, и потому в графе появляются также операции деления , они обозначены желтым цветом.

{| align="center"
|- valign="top"
| [[File:DirectL.png|500px|thumb|Рисунок 3. Граф решения СЛАУ с левой треугольной матрицей]]
| [[File:DirectU.png|450px|thumb|Рисунок 4. Граф решения СЛАУ с правой треугольной матрицей]]
|}

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

При изучении ресурса параллелизма теста видно, что основная сложность (''квадратичная'') будет у разложения Гаусса с выбором ведущего элемента по столбцу (именно из-за наличия выбора элемента по столбцу). Остальные части алгоритма имеют не более линейной сложности. Поэтому для оптимизации вычислений возможному исследователю нужно заняться именно оптимизацией разложения Гаусса с выбором ведущего элемента по столбцу. Кроме этого, первый кусок второй части (решение первой из треугольных СЛАУ) может быть пристыкован к первой части исполнен почти полностью «на её фоне», ибо направление перевычисления данных у них совпадают. Однако второй кусок второй части, несмотря на его схожесть с первым, может быть вычислен не ранее, чем будет выполнен весь первый кусок, поскольку у них направления перевычисления данных противоположны.

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

По сути теста у него всегда одни и те же данные, причём вычисляемые в самом же тесте. Поэтому в строгом смысле у алгоритма нет входных данных.

Выходными данными являются вычисляемые и выдаваемые тестом нормы невязки, решения, матрицы и их отношения, а также вычисляемая мощность вычислений целевой вычислительной системы.

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

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

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

Строго говоря, при реализации теста испытывающий компьютерную систему испытывает и версии Линпака или другого пакета, откуда он должен вставлять вызовы разложения Гаусса и решения СЛАУ с помощью полученного разложения. Поэтому находящиеся в сети версии теста не являются догмой, поскольку с их помощью можно тестировать и другие версии реализации метода Гаусса. Как уже отмечено выше, из-за того, что разложение Гаусса вычисляется на месте исходной матрицы, а также из-за того, что при прямом-обратном и обратном ходе решение занимает место правой части, после вычисления решения приходится заново перевычислять как матрицу системы, так и правую часть — для последующего вычисления невязки. Это решение вполне можно поменять с целью оптимизации теста.

=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====

[[file:linpack 1.PNG|thumb|center|700px|Рисунок 5. Тест Linpack. Общий профиль обращений в память]]

На рис.5 представлен общий профиль обращений в память для теста Linpack. В данном тесте задействовано 3 массива. Обращения к первым двум выделены на рис.5 зеленым цветом (фрагменты 1 и 2), остальные обращения выполняются к элементам третьего массива – матрицы, содержащей коэффициенты СЛАУ. Данный тест состоит из двух этапов – факторизации матрицы и собственно решения СЛАУ. Разделение между этапами отмечено на рисунке оранжевой линией. Видно, что первый этап обладает итерационной структурой, при этом на каждой следующей итерации отбрасываются из рассмотрения несколько элементов матрицы с наименьшими индексами. Также можно заметить, что на втором этапе выполняется два прохода по элементам матрицы с возрастающим шагом, сначала последовательный, затем обратный. Однако в целом профиль устроен достаточно сложно, и для понимания свойств локальности необходимо детальное рассмотрение.

Фрагмент 1 показан отдельно на рис.6. При подобном приближении хорошо видно, что данный фрагмент состоит из двух последовательных переборов всех элементов массива, при этом размер фрагмент очень мал по сравнению с общим профилем. Такой последовательный перебор характеризуется высокой пространственной и достаточно низкой временной локальностью, поскольку к каждому элементу обращение выполняется всего дважды.

[[file:linpack 2.PNG|thumb|center|400px|Рисунок 6. Фрагмент 1 (профиль обращений к первому массиву)]]

Далее перейдем к рассмотрению фрагмента 2, представленного на рис.7. Данный профиль состоит из двух похожих этапов, состоящих из набора итераций. На каждой итерации выполняется последовательный перебор элементов массива, при этом на следующей итерации отбрасывается их рассмотрения один из элементов: на первом этапе – элемент с минимальным индексом, на втором – с максимальным индексом.

Подобный профиль обладает очень высокой как пространственной, так и временной локальностью, поскольку почти всегда обращения выполняются к соседним элементам, причем элементы достаточно часто используются повторно. Однако заметим, что данный фрагмент состоит всего из около 2000 элементов, что значительно меньше общего числа обращений в программе. Значит, большая часть (и, скорее всего, основное влияние) приходится на последний массив.

[[file:linpack 3.PNG|thumb|center|400px|Рисунок 7. Фрагмент 2 (профиль обращений к второму массиву)]]

На рис.8 представлен фрагмент 3, выделенный на рис.5, соответствующий одной итерации цикла, в котором выполняются обращения к данному массиву. Из данного рисунка хорошо видно, что итерация состоит из двух частей, соответствующих двум внутренним циклам. В обоих случаях число обращений на любой итерации внутреннего цикла примерно равно, однако в первом внутреннем цикле на следующей итерации перебирается следующая часть элементов массива, в то время как во втором цикле перебираются одни и те же элементы.

[[file:linpack 4.PNG|thumb|center|700px|Рисунок 8. Фрагмент 3 (профиль обращений к третьему массиву, одна итерация)]]

Остается выяснить структуру обращений в память на итерациях данных двух циклов. Рассмотрим более подробно часть фрагмента, выделенную на рис.8 зеленым (рис.9).

[[file:linpack 5.PNG|thumb|center|700px|Рисунок 9. Одна итерация фрагмент 3, небольшая часть]]

Видно, что первые два этапа отличаются от остальных – на них выполняются некоторые начальные действия. Затем начинаются подобные итерации внутренних циклов, причем в обоих случаях (выделенные зеленым части 1 и 2) выполняется последовательный перебор элементов. Основная разница заключается лишь в том, что в первом цикле обращения к каждому элементу выполняются дважды.

Обращения к данному массиву в рамках внутренних циклов характеризуются высокой пространственной локальностью. При этом во втором цикле используются одни и те же элементы, что приводит также и к достаточно высокой временной локальности. Таким образом, в рамках одной итерации (рис. 4) локальность обращений высока. А при условии, что на разных итерациях происходят обращения к одним и тем же элементам (и число обращений на каждой итерации не так уж велико), это приводит к дальнейшему повышению локальности.

===== Количественная оценка локальности =====

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/linpack/linpack_np.cpp здесь] (оригинал исходного кода взят [http://people.sc.fsu.edu/~%20jburkardt/cpp_src/linpack_bench/linpack_bench_s.cpp отсюда]). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].

Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

На рис.10 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что данный показатель у теста Linpack один из самых высоких, что говорит об эффективном взаимодействии с памятью.

[[file:linpack daps ru.PNG|thumb|center|700px|Рисунок 10. Сравнение значений оценки daps]]

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.11 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность обращений в память теста Linpack очень высока, что соответствует полученным ранее оценкам и выводам.

[[file:linpack cvg.PNG|thumb|center|700px|Рисунок 11. Сравнение значений оценки cvg]]

=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
Проведём исследование масштабируемости реализации HPL теста Linpack согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:

* число процессоров [8 : 128] с шагом 8;
* размер матрицы [1000 : 100000] c шагом 1000.

В результате проведённых экспериментов был получен следующий диапазон [[Глоссарий#Эффективность реализации|эффективности реализации]] алгоритма:

* минимальная эффективность реализации 0.039%;
* максимальная эффективность реализации 86,7%.

На следующих рисунках приведены графики [[Глоссарий#Производительность|производительности]] и эффективности теста HPL в зависимости от изменяемых параметров запуска.

[[file:Масштабируемость Linpack performance.png|thumb|center|700px|Рисунок 12. Тест HPL. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
[[file:Linpack масштабируемость эффективность.png|thumb|center|700px|Рисунок 13. Тест HPL. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]

Построим оценки масштабируемости теста Linpack:
* По числу процессов: -0.061256. При увеличении числа процессов эффективность на рассмотренной области изменений параметров запуска уменьшается, однако в целом уменьшение не очень быстрое. Малая интенсивность изменения объясняется высокой общей эффективностью работы при больших размерах задачи, однако при росте числа процессов эффективность равномерно уменьшается. Это объясняется также тем, что с ростом [[Глоссарий#Вычислительная сложность|вычислительной сложности]] падение эффективности становится не таким быстрым. Уменьшение эффективности на рассмотренной области работы параллельной программы объясняется быстрым ростом накладных расходов на организацию параллельного выполнения. С ростом вычислительной сложности задачи эффективность снижается так же быстро, но при больших значениях числа процессов. Это подтверждает предположение о том, что накладные расходы начинают сильно превалировать над вычислениями.
* По размеру задачи: 0.010134. При увеличении размера задачи эффективность возрастает. Эффективность возрастает тем быстрее, чем большее число процессов используется для выполнения. Это подтверждает предположение о том, что размер задачи сильно влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска сильно увеличивается. Также, учитывая разницу максимальной и минимальной эффективности почти в 80%, можно сделать вывод, что рост эффективности при увеличении размера задачи наблюдается на большей части рассмотренной области значений.
* По двум направлениям: 0.0000284 При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности не очень большая.

[http://git.algowiki-project.org/Teplov/Scalability/tree/master/HPL Исследованная реализация теста]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Решение систем линейных уравнений]]

LU-разложение методом Гаусса

2016-07-08T13:30:55Z

AntonChupin:

Основные авторы описания: [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|2.4]])

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

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

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

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

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

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

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

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

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

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

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

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

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

=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====

[[file:gauss forward 1.PNG|thumb|center|700px|Рисунок 2. Прямой ход метода Гаусса решения СЛАУ. Общий профиль обращений в память]]

На рис.2 представлен профиль обращений в память для прямого хода метода Гаусса решения СЛАУ. Из исходного кода, как и из рисунка, видно, что в программе задействовано 2 основных массива: профиль обращений к элементам первого выделен зеленым (фрагмент 1); все остальные обращения происходят к элементам второго массива. Видно, что общий профиль всей программы устроен достаточно сложно. Основное, что можно заметить из данного рисунка, – это итерационная природа профиля, причем каждая следующая итерация содержит меньше обращений. Это особенно хорошо видно по фрагменту 1.

Далее, как известно, в прямом ходе Гаусса на каждой итерации отбрасывается из рассмотрения одна из строк СЛАУ. Это отчетливо видно и на рис.2: на каждой итерации (одна из них выделена как фрагмент 2) выполняется серия обращений, связанных с отбрасываемой строкой (фрагмент 3), после чего обращения к этим элементам больше не выполняются. Также можно заметить, что фрагменты, подобные фрагменту 3, на каждой последующей итерации становятся все меньше, как по числу обращений, так и по числу элементов, к которым происходят обращения.

Однако на основе подобной общей картины очень сложно дать даже качественные оценки локальности. Перейдем к более подробному рассмотрению фрагмента 1, соответствующего обращениям к одному из двух массивов.

[[file:gauss forward 2.PNG|thumb|center|500px|Рисунок 3. Фрагмент 1 (профиль обращений к первому массиву)]]

На рис.3 показан отдельно фрагмент 1, выделенный на рис.2 зеленым. Наблюдается довольно интересная картина: исходя из рис.2, складывалось впечатление, что данный профиль образуется чередованием итераций двух разных циклов, причем итерация первого цикла заметно короче итераций второго цикла. На самом же деле, из рис.3 можно увидеть, что профиль состоит из однотипных итераций, в рамках которых производится последовательный перебор элементов массива. При этом на каждой следующей итерации отбрасывается элемент с минимальным индексом. Иллюзия наличия двух разных циклов обусловлена исключительно числом обращений к другому массиву – когда число таких обращений велико, итерация данного фрагмента кажется длиннее. При этом во фрагменте 1 (как видно на рис.3) число обращений всего лишь около 1200, тогда как весь профиль обращений состоит из 34 тысяч. То есть на долю обращений к первому массиву приходится всего 3.5% всех обращений в программе.

Поскольку основа данного профиля – последовательный перебор элементов массива, можно сказать, что данный фрагмент обладает высокой пространственной локальностью. А поскольку итераций с перебором элементов достаточно много, также видно, что и временна́я локальность достаточно высока.

Теперь перейдем к рассмотрению профиля обращений ко второму массиву, который значительно больше и сложнее первого профиля. На рис.4 отдельно представлен фрагмент 2, выделенный на рис.2. Такой фрагмент устроен из четырех частей, отмеченных на рисунке оранжевым.

[[file:gauss forward 3.PNG|thumb|center|700px|Рисунок 4. Фрагмент 2 (итерация профиля обращений ко второму массиву)]]

Часть 1 очень похожа на повторяющийся последовательный перебор одного и того же небольшого числа элементов в цикле. При более близком рассмотрении можно убедиться, что это действительно так. На рис.5 показано приближение фрагмента 2, выделенное на рис.4 синим цветом. Также на этом рисунке видно, что часть 2 представляет собой практически полное подобие последовательного перебора всех элементов данного массива. Таким образом, обе эти части обладают высокой пространственной локальностью (из-за последовательного перебора). При этом часть 1 обладает также высокой временной локальностью, поскольку перебор повторяется в цикле, в отличие от части 2, где к каждому элементу выполняется только одно обращение.

Часть 3 состоит всего из нескольких обращений и представляет собой перебор всех элементов массива, выполненных с достаточно большим шагом, гораздо большим, чем в части 2. В данном случае, из-за достаточно большого шага, наблюдается невысокая пространственная локальность и отсутствие временно́й локальности, так как перебор выполняется единожды.

Часть 4 представляет собой последовательный перебор части массива, по размеру соответствующей числу отброшенных из рассмотрения элементов; чем ближе к концу профиля, тем больше обращений расположено в части 4. Эта часть обладает теми же свойствами локальности, что и часть 2. Отличие заключается в числе обращений, однако в данном случае это не оказывает сильное влияние на локальность.

При рассмотрении фрагмента 2 в целом основное влияние оказывают части 1 и 2, поэтому можно утверждать, что это фрагмент обладает достаточно высокой и пространственной, и временно́й локальностью. Однако на последующих итерациях (см. рис.2) локальность в целом будет постепенно снижаться, поскольку на каждой итерации отбрасывается из рассмотрения некоторая часть элементов.

[[file:gauss forward 4.PNG|thumb|center|500px|Рисунок 5. Приближение фрагмента 2]]

===== Количественная оценка локальности =====

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/gauss_forward/gauss_forward.h здесь] (функция Kernel1). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].

Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

На рис.6 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что отмеченный синий столбец, соответствующий прямому ходу метода Гаусса, расположен в правой части и показывает достаточно высокую производительность, немного ниже производительности теста Линпак. Также отметим, что значение daps для данной задачи практически совпадает со значением daps для всего метода Гаусса (столбец «gauss»), объединяющего как прямой, так и обратный ход. Это связано с тем, что обратный ход состоит из гораздо меньшего числа обращений, нежели прямой ход, поэтому оказывает меньшее влияние.

[[file:gauss forward daps ru.PNG|thumb|center|700px|Рисунок 6. Сравнение значений оценки daps]]

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.7 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, как и в случае с оценкой daps, прямой ход метода Гаусса обладает высокой локальностью. Причем согласно данной оценке тест Линпак показывает практически те же результаты. Отметим, что снова значение оценки для отдельно прямого хода и совокупности прямого и обратного ходов (столбец «gauss») совпадают.

[[file:gauss forward cvg.PNG|thumb|center|700px|Рисунок 7. Сравнение значений оценки cvg]]

=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость параллельной реализации метода Гаусса Производительность.png|thumb|center|700px|Рисунок 8. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная производительность. ]]
[[file:Масштабируемость метод Гаусса.png|thumb|center|700px|Рисунок 9. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размер матрицы [1024 : 5120]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,11 %
* Максимальная эффективность 6.65%
Оценка масштабируемости
* По числу процессов: -0.000101 – при увеличении числа процессов эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении размера задачи. Учитывая разницу между максимальным и минимальным значением эффективности в 6,5% можно сделать вывод, что на рассмотренной области снижение эффективности, скорее всего, достаточно равномерное. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Могут присутствовать области возрастания эффективности, на всех рассмотренных размерах матрицы. Это может объясняться увеличением вычислительной сложности задачи, что при постоянных накладных расходах на организацию параллельного взаимодействия приводит к общему увеличению эффективности работы.
* По размеру задачи:-0.00674– при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области. Это может свидетельствовать о том, что при увеличении размера задачи возрастают и накладные расходы на организацию параллельного взаимодействия. Так как интенсивность снижения эффективности по этому направлению выше, чем по направлению числа процессов, скорее всего падение интенсивности значительно при малом числе процессов более интенсивное, чем в присутствующих областях возрастания эффективности при большом числе процессов.
* По двум направлениям: -6.621e-05 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности очень мала. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 6,5 % говорит о том, что если на поверхности присутствуют области с очень интенсивным изменением эффективности, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/Gauss_elimination/Gauss_ACES.c Исследованная параллельная реализация на языке C]

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

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

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

== Литература ==

[[En:Gaussian elimination]]

[[Категория:Начатые статьи]]
[[Категория:Разложения матриц]]
[[Категория:Решение систем линейных уравнений]]