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

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

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

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

Как следствие этого алгоритма, заполнение (набор ненулевых матричных элементов, созданных в разложении Холецкого, которые не являются частью структуры входной матрицы) ограничивается не более чем квадратом размера разделителя на каждом уровне рекурсивной раздел. В частности, для плоских графов (часто возникающих при решении разреженных линейных систем, полученных из двумерных метод конечных элементов сетки) итоговая матрица имеет O (п бревноп) ненулевые из-за теорема о плоском сепараторе гарантирующие разделители размера O (√п).[2] Для произвольных графов существует вложенное рассечение, которое гарантирует заполнение внутри коэффициент оптимальности, где d это максимальная степень и м - количество ненулевых. [3]

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

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

Примечания

  1. ^ Джордж (1973).
  2. ^ Липтон, Роуз и Тарджан (1979); Гилберт и Тарджан (1986).
  3. ^ Агравал, Кляйн и Рави (1993).

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

  • Джордж, Дж. Алан (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.