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

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

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

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

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

См. также

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

Ссылки

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