Jump to content

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

В анализе численном вложенное рассечение представляет собой «разделяй и властвуй» эвристику для решения разреженных симметричных систем линейных уравнений, основанных на разбиении графа . Вложенное рассечение было предложено Джорджем (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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 0520edc64c8a6cefeff25a543b0241d2__1587166500
URL1:https://arc.ask3.ru/arc/aa/05/d2/0520edc64c8a6cefeff25a543b0241d2.html
Заголовок, (Title) документа по адресу, URL1:
Nested dissection - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)