Шаблон:Main page/Featured: различия между версиями
| [выверенная версия] | [непроверенная версия] |
Algoman (обсуждение | вклад) |
Algoman (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
---- | ---- | ||
<br /> | <br /> | ||
| − | Читать полностью [[Разложение_Холецкого_(метод_квадратного_корня)]]<br /> | + | Читать полностью: [[Разложение_Холецкого_(метод_квадратного_корня)]]<br /> |
<br /> | <br /> | ||
---- | ---- | ||
| − | {{: | + | {| style="float:{{{float|right}}}; clear:right;margin-left: 1em; width:{{{width|30%}}};" cellpadding=8 cellspacing=1 border=0 |
| + | |- | ||
| + | |align=left width=100% style="background-color:#f3f3ff; border:1px solid"| | ||
| + | '''Свойства алгоритма:''' | ||
| + | * Последовательная сложность алгоритма:<nowiki/> <math>O(n^3)</math> | ||
| + | * Высота ярусно-параллельной формы:<nowiki/> <math>O(n)</math> | ||
| + | * Ширина ярусно-параллельной формы:<nowiki/> <math>O(n^2)</math> | ||
| + | * Объём входных данных:<nowiki/> <math>\frac{n (n + 1)}{2}</math> | ||
| + | * Объём выходных данных:<nowiki/> <math>\frac{n (n + 1)}{2}</math> | ||
| + | |} | ||
| + | |||
| + | == Описание свойств и структуры алгоритма == | ||
| + | |||
| + | === Общее описание алгоритма === | ||
| + | |||
| + | '''Разложение Холецкого''' впервые предложено французским офицером и математиком Андре-Луи Холецким в конце Первой Мировой войны, незадолго до его гибели в бою в августе 1918 г. Идея этого разложения была опубликована в 1924 г. его сослуживцем. Потом оно было использовано поляком Т. Банашевичем в 1938 г. В советской математической литературе называется также методом квадратного корня [1-3]; название связано с характерными операциями, отсутствующими в родственном разложении Гаусса. | ||
| + | |||
| + | Первоначально разложение Холецкого использовалось исключительно для плотных симметричных положительно определенных матриц. В настоящее время его использование гораздо шире. Оно может быть применено также, например, к эрмитовым матрицам. Для повышения производительности вычислений часто применяется блочная версия разложения. | ||
| + | |||
| + | Для разреженных матриц разложение Холецкого также широко применяется в качестве основного этапа прямого метода решения линейных систем. В этом случае используют специальные упорядочивания для уменьшения ширины профиля исключения, а следовательно и уменьшения количества арифметических операций. Другие упорядочивания используются для выделения независимых блоков вычислений при работе на системах с параллельной организацией. | ||
| + | |||
| + | === Математическое описание === | ||
| + | |||
| + | Исходные данные: положительно определённая симметрическая матрица <math>A</math> (элементы <math>a_{ij}</math>). | ||
| + | |||
| + | Вычисляемые данные: нижняя треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>). | ||
| + | |||
| + | Формулы метода: | ||
| + | :<math> | ||
| + | \begin{align} | ||
| + | l_{11} & = \sqrt{a_{11}}, \\ | ||
| + | l_{j1} & = \frac{a_{j1}}{l_{11}}, \quad j \in [2, n], \\ | ||
| + | l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}, \quad i \in [2, n], \\ | ||
| + | l_{ji} & = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}, \quad i \in [2, n - 1], j \in [i + 1, n]. | ||
| + | \end{align} | ||
| + | </math> | ||
| + | |||
| + | Существует также блочная версия метода, однако в данном описании разобран только точечный метод. | ||
| + | |||
| + | В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление <math>1/l_{ii}</math> и затем умножение на него всех (видоизменённых) <math>a_{ji}</math> . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный. | ||
| + | |||
| + | === Последовательная сложность алгоритма === | ||
| + | |||
| + | Для разложения матрицы порядка n методом Холецкого в последовательном (наиболее быстром) варианте требуется: | ||
| + | |||
| + | * <math>n</math> вычислений квадратного корня, | ||
| + | * <math>\frac{n(n-1)}{2}</math> делений, | ||
| + | * <math>\frac{n^3-n}{6}</math> сложений (вычитаний), | ||
| + | * <math>\frac{n^3-n}{6}</math> умножений. | ||
| + | |||
| + | Умножения и сложения (вычитания) составляют ''основную часть алгоритма''. | ||
| + | |||
| + | При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения метода Холецкого. | ||
| + | |||
| + | При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам ''с кубической сложностью''. | ||
Версия 19:05, 26 марта 2015
Читать полностью: Разложение_Холецкого_(метод_квадратного_корня)
|
Свойства алгоритма:
|
Содержание
1 Описание свойств и структуры алгоритма
1.1 Общее описание алгоритма
Разложение Холецкого впервые предложено французским офицером и математиком Андре-Луи Холецким в конце Первой Мировой войны, незадолго до его гибели в бою в августе 1918 г. Идея этого разложения была опубликована в 1924 г. его сослуживцем. Потом оно было использовано поляком Т. Банашевичем в 1938 г. В советской математической литературе называется также методом квадратного корня [1-3]; название связано с характерными операциями, отсутствующими в родственном разложении Гаусса.
Первоначально разложение Холецкого использовалось исключительно для плотных симметричных положительно определенных матриц. В настоящее время его использование гораздо шире. Оно может быть применено также, например, к эрмитовым матрицам. Для повышения производительности вычислений часто применяется блочная версия разложения.
Для разреженных матриц разложение Холецкого также широко применяется в качестве основного этапа прямого метода решения линейных систем. В этом случае используют специальные упорядочивания для уменьшения ширины профиля исключения, а следовательно и уменьшения количества арифметических операций. Другие упорядочивания используются для выделения независимых блоков вычислений при работе на системах с параллельной организацией.
1.2 Математическое описание
Исходные данные: положительно определённая симметрическая матрица [math]A[/math] (элементы [math]a_{ij}[/math]).
Вычисляемые данные: нижняя треугольная матрица [math]L[/math] (элементы [math]l_{ij}[/math]).
Формулы метода:
- [math] \begin{align} l_{11} & = \sqrt{a_{11}}, \\ l_{j1} & = \frac{a_{j1}}{l_{11}}, \quad j \in [2, n], \\ l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}, \quad i \in [2, n], \\ l_{ji} & = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}, \quad i \in [2, n - 1], j \in [i + 1, n]. \end{align} [/math]
Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление [math]1/l_{ii}[/math] и затем умножение на него всех (видоизменённых) [math]a_{ji}[/math] . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.
1.3 Последовательная сложность алгоритма
Для разложения матрицы порядка n методом Холецкого в последовательном (наиболее быстром) варианте требуется:
- [math]n[/math] вычислений квадратного корня,
- [math]\frac{n(n-1)}{2}[/math] делений,
- [math]\frac{n^3-n}{6}[/math] сложений (вычитаний),
- [math]\frac{n^3-n}{6}[/math] умножений.
Умножения и сложения (вычитания) составляют основную часть алгоритма.
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения метода Холецкого.
При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам с кубической сложностью.
