Метод Холецкого (нахождение симметричного треугольного разложения): различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Konshin (обсуждение | вклад) |
Konshin (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
== Разложение Холецкого для эрмитовой матрицы == | == Разложение Холецкого для эрмитовой матрицы == | ||
| + | |||
| + | Эрмитовой (или комплексно-самосопряженной) матрицей называют такую квадратную комплексную матрицу <math>A</math>, для элементов которой выполняется соотношение | ||
| + | <math>a_{ij}=\overline{a_{ji}}</math>. В матричном виде это можно записать как <math>A=\overline{A_T}</math> или <math>A=A^Н</math>. | ||
=== Точечный вариант === | === Точечный вариант === | ||
| + | |||
| + | Как естественное обобщение разложения Холецкого для точечной симметричной положительно-определеной матрицы может быть рассмотрено разложение Холецкого для эрмитовой матрицы. Все формулы для вычисления разложения остаются прежними, только теперь вместо операций над вещественными числами выполняются аналогичные комплексные операции. | ||
| + | |||
| + | В отличие от вещественного варианта, для выполнении комплексных операций потребуется считывать из памяти вдвое больше данных и производить над ними примерно вчетверо больше арифметических операций, что должно не только несколько улучшыть локальность вычислений, но и повысить их эффективность. | ||
=== Блочный вариант === | === Блочный вариант === | ||
| + | |||
| + | Реализация блочного варианта разложения Холецкого для эрмитовых матриц будет аналогична рассмотрему выше блочному варианту для вещественных матриц. | ||
== Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно-определённой матрицы == | == Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно-определённой матрицы == | ||
Версия 17:59, 17 марта 2015
Содержание
- 1 Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
- 2 Разложение Холецкого, блочный вещественный вариант для плотной симметричной положительно-определённой матрицы
- 3 Разложение Холецкого для эрмитовой матрицы
- 4 Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно-определённой матрицы
- 5 Разложение Холецкого, блочный вещественный вариант для разреженной симметричной положительно-определённой матрицы
- 6 Использование разложения Холецкого в итерационных методах
- 7 Использование разложения Холецкого в параллельных итерационных алгоритмах
- 7.1 Переупорядочивания для выделения блочности
- 7.2 Разложение в независимых блоках
- 7.3 Разложение в сепараторах
- 7.4 Иерархические и вложенные алгоритмы
- 7.5 Блочный метод Якоби (без перекрытия блоков, Block Jacobi - BJ)
- 7.6 Адитивный метод Шварца (Additive Schwarz - AS)
- 7.7 Блочный метод неполного обратного разложения Холецкого (BIIC)
- 8 Решение линейной системы с треугольной матрицей
- 8.1 Решение системы с плотной верхнетреугольной матрицей
- 8.2 Решение системы с плотной нижнетреугольной матрицей
- 8.3 Решение системы с разреженной верхнетреугольной матрицей
- 8.4 Решение системы с разреженной нижнетреугольной матрицей
- 8.5 Решение системы с комплексной треугольной матрицей
- 8.6 Решение систем с блочноокаймленными треугольными матрицами
1 Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы.
2 Разложение Холецкого, блочный вещественный вариант для плотной симметричной положительно-определённой матрицы
3 Разложение Холецкого для эрмитовой матрицы
Эрмитовой (или комплексно-самосопряженной) матрицей называют такую квадратную комплексную матрицу [math]A[/math], для элементов которой выполняется соотношение [math]a_{ij}=\overline{a_{ji}}[/math]. В матричном виде это можно записать как [math]A=\overline{A_T}[/math] или [math]A=A^Н[/math].
3.1 Точечный вариант
Как естественное обобщение разложения Холецкого для точечной симметричной положительно-определеной матрицы может быть рассмотрено разложение Холецкого для эрмитовой матрицы. Все формулы для вычисления разложения остаются прежними, только теперь вместо операций над вещественными числами выполняются аналогичные комплексные операции.
В отличие от вещественного варианта, для выполнении комплексных операций потребуется считывать из памяти вдвое больше данных и производить над ними примерно вчетверо больше арифметических операций, что должно не только несколько улучшыть локальность вычислений, но и повысить их эффективность.
3.2 Блочный вариант
Реализация блочного варианта разложения Холецкого для эрмитовых матриц будет аналогична рассмотрему выше блочному варианту для вещественных матриц.
4 Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно-определённой матрицы
4.1 Основные отличия от случая плотной матрицы
4.2 Переупорядочивания для уменьшения количества новых ненулевых элементов
5 Разложение Холецкого, блочный вещественный вариант для разреженной симметричной положительно-определённой матрицы
(плотные блоки небольшого размера, равного количеству неизвестных функций на узел, или выбираемому искуственно)
