Вложенное рассечение - Nested dissection

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

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

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

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

Смотрите также

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

Примечания

Рекомендации

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