Шаблон:Main page/Featured

Разложение_Холецкого_(метод_квадратного_корня)

Свойства алгоритма: Последовательная сложность алгоритма: [math]\displaystyle{ O(n^3) }[/math] Высота ярусно-параллельной формы: [math]\displaystyle{ O(n) }[/math] Ширина ярусно-параллельной формы: [math]\displaystyle{ O(n^2) }[/math] Объём входных данных: [math]\displaystyle{ \frac{n (n + 1)}{2} }[/math] Объём выходных данных: [math]\displaystyle{ \frac{n (n + 1)}{2} }[/math]

Описание свойств и структуры алгоритма

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

Разложение Холецкого впервые предложено французским офицером и математиком Андре-Луи Холецким в конце Первой Мировой войны, незадолго до его гибели в бою в августе 1918 г. Идея этого разложения была опубликована в 1924 г. его сослуживцем. Потом оно было использовано поляком Т. Банашевичем в 1938 г. В советской математической литературе называется также методом квадратного корня [1-3]; название связано с характерными операциями, отсутствующими в родственном разложении Гаусса.

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

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

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

Исходные данные: положительно определённая симметрическая матрица [math]\displaystyle{ A }[/math] (элементы [math]\displaystyle{ a_{ij} }[/math]).

Вычисляемые данные: нижняя треугольная матрица [math]\displaystyle{ L }[/math] (элементы [math]\displaystyle{ l_{ij} }[/math]).

Формулы метода:

[math]\displaystyle{ \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]\displaystyle{ 1/l_{ii} }[/math] и затем умножение на него всех (видоизменённых) [math]\displaystyle{ a_{ji} }[/math] . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.

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

Для разложения матрицы порядка n методом Холецкого в последовательном (наиболее быстром) варианте требуется:

• [math]\displaystyle{ n }[/math] вычислений квадратного корня,
• [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] делений,
• [math]\displaystyle{ \frac{n^3-n}{6} }[/math] сложений (вычитаний),
• [math]\displaystyle{ \frac{n^3-n}{6} }[/math] умножений.

Умножения и сложения (вычитания) составляют основную часть алгоритма.

При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения метода Холецкого.

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

(Читать полностью…)