Вложенное рассечение

В численном анализе , вложенная диссекции является деление и захват эвристической для решения разреженных симметричных систем линейных уравнений на основе разделения графов . Вложенное рассечение было введено Джорджем (1973) ; название было предложено Гарретом Биркгофом . ^[1]

Вложенное вскрытие состоит из следующих этапов:

• Сформируйте неориентированный граф, в котором вершины представляют строки и столбцы системы линейных уравнений, а ребро представляет собой ненулевой элемент разреженной матрицы, представляющей систему.
• Рекурсивно разделите граф на подграфы с помощью разделителей , небольших подмножеств вершин, удаление которых позволяет разбить граф на подграфы с не более чем постоянной долей числа вершин.
• Выполните разложение Холецкого (вариант исключения Гаусса для симметричных матриц), упорядочив исключение переменных с помощью рекурсивной структуры разбиения: сначала удаляется каждый из двух подграфов, образованных удалением разделителя, а затем удаляются вершины разделителя.

Как следствие этого алгоритма, заполнение (набор ненулевых матричных элементов, созданных в разложении Холецкого, которые не являются частью структуры входной матрицы) ограничивается не более чем квадратом размера разделителя на каждом уровне рекурсивной раздел. В частности, для плоских графов (часто возникающих при решении разреженных линейных систем, полученных из двумерных сеток методом конечных элементов ) результирующая матрица имеет O ( n  log  n ) ненулевых значений из-за теоремы о плоском разделителе, гарантирующей разделители размера O ( √ п ). ^[2] Для произвольных графов существует вложенное рассечение, которое гарантирует заполнение с коэффициентом оптимальности, где${\ Displaystyle О (\ мин \ {{\ sqrt {d}} \ log ^ {4} n, m ^ {1/4} \ log ^ {3.5} n \})}$d - максимальная степень, m - количество ненулевых символов. ^[3]

См. Также [ править ]

• Циклический ранг графа или симметричная логическая матрица измеряет минимальное параллельное время, необходимое для выполнения разложения Холецкого.
• Разделитель вершин

Заметки [ править ]

Ссылки [ править ]

• Джордж, Дж Алан (1973), "Уплотненное рассечение регулярных сетки конечных элементов", SIAM журнал по численному анализу , 10 (2): 345-363, DOI : 10,1137 / 0710032 , JSTOR  2156361 CS1 maint: обескураженный параметр ( ссылка ).
• Гилберт, Джон Р. (1988), "Некоторые вложенная порядок рассечение почти оптимален" , Information Processing Letters , 26 (6): 325-328, DOI : 10,1016 / 0020-0190 (88) 90191-3 , ЛВП : 1813 / 6607.
• Гилберт, Джон Р .; Тарьян, Роберт Е. (1986), "Анализ алгоритма вложенного рассечения", Numerische Mathematik , 50 (4): 377-404, DOI : 10.1007 / BF01396660.
• Липтон, Ричард Дж .; Роуз, Дональд Дж .; Тарьян, Роберт Е. (1979), "Обобщенный вложенное рассечение", SIAM журнал по численному анализу , 16 (2): 346-358, DOI : 10,1137 / 0716027 , JSTOR  2156840.
• Агравал, Аджит; Кляйн, Филипп; Рави, R. (1993), «Вырубка на Заливка с помощью вложенной Взрезывание: доказуемо Хорошо Устранение Упорядочения», Теория графов и разреженных матриц вычислений , Springer Нью - Йорк, стр 31-55,. Дои : 10.1007 / 978-1-4613- 8369-7_2 , ISBN 978-1-4613-8371-0.