Вложенное рассечение
В анализе численном вложенное рассечение представляет собой «разделяй и властвуй» эвристику для решения разреженных симметричных систем линейных уравнений, основанных на разбиении графа . Вложенное рассечение было предложено Джорджем (1973) ; название было предложено Гарретом Биркгофом . [1]
Вложенное рассечение состоит из следующих этапов:
- Сформируйте неориентированный граф , в котором вершины представляют строки и столбцы системы линейных уравнений, а ребро представляет собой ненулевой элемент в разреженной матрице, представляющей систему.
- Рекурсивно разделите граф на подграфы с помощью разделителей — небольших подмножеств вершин, удаление которых позволяет разбить граф на подграфы с не более чем постоянной долей числа вершин.
- Выполнить разложение Холецкого (вариант исключения Гаусса для симметричных матриц), упорядочив исключение переменных по рекурсивной структуре разбиения: сначала исключается каждый из двух подграфов, образованных удалением разделителя, а затем удаляются вершины разделителя.
В результате этого алгоритма заполнение (набор ненулевых элементов матрицы, созданных в результате разложения Холецкого, которые не являются частью входной матричной структуры) ограничивается не более чем квадратом размера разделителя на каждом уровне рекурсивного алгоритма. перегородка. В частности, для плоских графов (часто возникающих при решении разреженных линейных систем, полученных из двумерных сеток метода конечных элементов ) результирующая матрица имеет ненулевые значения O( n log n ) из-за теоремы о плоском сепараторе , гарантирующей сепараторы размера O( √ п ). [2] Для произвольных графов существует вложенное разделение, гарантирующее заполнение внутри коэффициент оптимальности, где d — максимальная степень, а m — количество ненулевых значений. [3]
См. также
[ редактировать ]- Ранг цикла графа или симметричная булева матрица измеряет минимальное параллельное время, необходимое для выполнения разложения Холецкого.
- Разделитель вершин
Примечания
[ редактировать ]Ссылки
[ редактировать ]- Джордж, Дж. Алан (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 .