Метод Холецкого (нахождение симметричного треугольного разложения): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 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 Разложение Холецкого для эрмитовой матрицы

Эрмитовой (или комплексно-самосопряженной) матрицей называют такую квадратную комплексную матрицу [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 Разложение Холецкого, блочный вещественный вариант для разреженной симметричной положительно-определённой матрицы

(плотные блоки небольшого размера, равного количеству неизвестных функций на узел, или выбираемому искуственно)

6 Использование разложения Холецкого в итерационных методах

6.1 Ограничивание заполнения в разложении Холецкого

6.2 Неполное разложение Холецкого по позициям IC(k)

6.3 Приближенное разложение Холецкого по значениям IC(tau)

6.4 Приближенное разложение Холецкого второго порядка IC(tau1,tau2)

6.5 Комбинация разложений Холецкого IC(k,tau) и IC(tau,m)

7 Использование разложения Холецкого в параллельных итерационных алгоритмах

7.1 Переупорядочивания для выделения блочности

7.1.1 Метод минимальных сепараторов

7.1.2 Метод минимальной степени (Minimum Degree - MD)

7.1.3 Метод вложенных сечений (Nested Dissection - ND)

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 Решение систем с блочноокаймленными треугольными матрицами