В чем преимущество мультисетки по сравнению с прекондиционерами декомпозиции доменов и наоборот?

Это в основном предназначено для эллиптических PDE над выпуклыми областями, так что я могу получить хороший обзор этих двух методов.

Многосеточные и многоуровневые методы разложения доменов имеют так много общего, что каждый из них обычно можно записать как частный случай другого. Основы анализа несколько иные, как следствие разных философий каждой области. Вообще говоря, многосеточные методы используют умеренные скорости укрупнения и простые сглаживатели, в то время как методы разложения доменов используют чрезвычайно быстрое укрупнение и сильные сглаживатели .

Мультисетка (MG)

Multigrid использует умеренные коэффициенты укрупнения и обеспечивает устойчивость благодаря модификации интерполяции и сглаживания. Для эллиптических задач операторы интерполяции должны быть "с низкой энергией", чтобы они сохраняли почти нулевое пространство оператора (например, моды твердого тела). Пример геометрического подхода к этим низкоэнергетическим интерполяторам - это Wan, Chan, Smith (2000) , сравнение с алгебраической конструкцией сглаженной агрегации Vaněk, Mandel, Brezina (1996) (параллельные реализации в ML и PETSc через PCGAMG, замена для Prometheus ) , Книга Троттенберга, Оостерли и Шуллера является хорошим общим справочником по многосеточным методам.

Большинство многосеточных сглаживателей включают точечную релаксацию, либо аддитивно (Якоби), либо мультипликативно (Гаусс Зейдель). Они соответствуют крошечным (одноузловым или одноэлементным) задачам Дирихле. Некоторая спектральная адаптивность, робастность и векторизация могут быть достигнуты с использованием сглаживателей Чебышева, см. Adams, Brezina, Hu, Tuminaro (2003) . Для несимметричных (например, транспортных) задач обычно необходимы мультипликативные сглаживатели, такие как Гаусс-Зейдель, и могут использоваться перевернутые интерполанты. В качестве альтернативы, сглаживатели для задач седловой точки и жестких волн могут быть сконструированы путем преобразования через «блочные предварительные кондиционеры», вдохновленные Шуром, или с помощью соответствующей «распределенной релаксации», в системы, в которых эффективны простые сглаживатели.

Многосеточная эффективность учебника относится к решению ошибки дискретизации в небольшом кратном стоимости нескольких остаточных оценок, всего лишь четыре, в точной сетке. Это подразумевает, что число итераций с фиксированным алгебраическим допуском уменьшается по мере увеличения количества уровней. Параллельно оценка времени включает логарифмический термин, возникающий из-за синхронизации, подразумеваемой многосеточной иерархией.

Декомпозиция домена (DD)

Первые методы декомпозиции доменов имели только один уровень. При отсутствии грубого уровня, номер условия предобусловленного оператора не может быть меньше гдеL- диаметр домена, аH- номинальный размер субдомена. На практике номера условий для одноуровневого DD лежат между этой границей иO(L$\mathcal O\big( \frac{L^2}{H^2}\big)$$L$$H$гдеh- размер элемента. Обратите внимание, что количество итераций, необходимых для метода Крылова, масштабируется как квадратный корень из числа условия. Оптимизированные методы Шварца(Gander 2006)улучшают константы и зависимость отH/hотносительно методов Дирихле и Неймана, но, как правило, не включают грубые уровни и, таким образом, ухудшаются в случае многих поддоменов. См. КнигиСмита, Бьёрстада и Гроппа (1996)илиТозелли и Видлунда (2005)для общей ссылки на методы декомпозиции области.$\mathcal O\big( \frac{L^2}{hH} \big)$$h$$H/h$

Для оптимальной или квазиоптимальной скорости сходимости необходимы несколько уровней. Большинство методов DD представляют собой двухуровневые методы, а некоторые очень сложно распространить на несколько уровней. Методы DD могут быть классифицированы как перекрывающиеся или не перекрывающиеся.

Перекрытие

Эти методы Шварца используют перекрытие и, как правило, основаны на решении задач Дирихле. Сила методов может быть увеличена путем увеличения перекрытия. Этот класс методов обычно надежен, не требует локальной идентификации пустого пространства или технических модификаций для проблем с локальными ограничениями (обычно в механике твердого тела), но требует дополнительной работы (особенно в 3D) из-за перекрытия. Кроме того, для ограниченных задач, таких как несжимаемость, обычно появляется постоянная inf-sup перекрывающейся полосы, что приводит к неоптимальным скоростям сходимости. Современные методы перекрытия, использующие грубые пространства, аналогичные BDDC / FETI-DP (обсуждаются ниже), разработаны Dorhmann, Klawonn, Widlund (2008) и Dohrmann and Widlund (2010) .

Неперекрывающиеся

Эти методы обычно решают какие-то задачи Неймана, что означает, что в отличие от методов Дирихле, они не могут работать с глобально собранной матрицей, а вместо этого требуют неубранных или частично собранных матриц. Самые популярные методы Неймана либо обеспечивают непрерывность между поддоменами путем балансировки на каждой итерации, либо с помощью множителей Лагранжа, которые обеспечивают непрерывность только после достижения сходимости. Ранние методы такого рода (Balancing Neumann-Neumann и FETI) требуют точной характеристики нулевого пространства каждого субдомена, как для построения грубого уровня, так и для того, чтобы проблемы субдомена были неособыми. Более поздние методы (BDDC и FETI-DP) выбирают углы поддоменов и / или моменты ребер / граней в качестве степеней свободы грубого уровня. См. Клавонн и Райнбах (2007)для углубленного обсуждения грубого выбора пространства для 3D-упругости. Mandel, Dohrmann и Tazaur (2005) показали, что BDDC и FETI-DP имеют все одинаковые собственные значения, за исключением возможных 0 и 1.

Более двух уровней

Большинство методов DD представлены только как двухуровневые, а некоторые выбирают грубые пробелы, которые неудобны для использования с более чем двумя уровнями. К сожалению, особенно в 3D, проблемы грубого уровня быстро становятся узким местом, ограничивая размеры проблем, которые могут быть решены. Кроме того, числа условий предобусловленных операторов, особенно для методов DD, основанных на задачах Неймана, имеют тенденцию масштабироваться как

$L$$L \le 4$$10^{12}$

Это отличная рецензия, но я думаю, что говорить о том, что (многоуровневые) DD и MG имеют много общего, неточно или, по крайней мере, бесполезно. Методы очень разные, и я не думаю, что опыт в одном очень полезен в другом.

Во-первых, два сообщества используют разные определения сложности: DD оптимизирует число условий предварительно подготовленных систем, а MG оптимизирует сложность работы / памяти. Это большая принципиальная разница - «оптимальность» имеет совершенно другое значение в этих двух контекстах. Ситуация не меняется, когда вы добавляете параллельную сложность (хотя вы получаете лог-термин, добавленный в MG). Два сообщества почти говорят на разных языках.

Во-вторых, в MG встроен многоуровневый метод, и многоуровневые методы DD были разработаны с использованием двухуровневой теории и реализаций. Это ограничивает пространство грубых пространств сетки, которые вы можете использовать в MG - они должны быть рекурсивными. Например, вы не можете реализовать FETI в структуре MG. Люди делают несколько многоуровневых методов DD, как упоминал Джед, но, по крайней мере, некоторые из популярных популярных методов DD не кажутся рекурсивно реализуемыми.

В-третьих, я вижу, что сами алгоритмы, как это практикуется, очень разные. Говоря качественно, я бы сказал, что методы DD проецируют на границы домена и решают эту проблему интерфейса. MG работает напрямую с нативными уравнениями. Избежание этой проекции позволяет легко применять MG к нелинейным и несимметричным задачам. Хотя теория почти уходит от нелинейных и несимметричных задач, они работали для многих людей. MG также явно разделяет задачу на две части: грубое пространство сетки для масштабирования и итерационный решатель (более гладкий) для решения физики. Это очень важно для понимания и работы с MG и является привлекательным свойством для меня.

Хотя теоретически сглаживатели и грубые пространства сетки тесно связаны, на практике вы часто можете менять и использовать разные сглаживатели как параметр оптимизации. Как упоминал Джед, точечные или вершинные сглаживатели популярны и обычно быстрее, но для сложных задач могут быть полезны более тяжелые сглаживатели. Этот график из моей диссертации показывает время решения как функцию коэффициента Пуассона для Якоби, блока Якоби и «аддитивного Шварца» (с перекрытием). Его немного трудно читать, но при самом высоком коэффициенте Пуассона (0,499) перекрывающийся Шварц примерно в 2 раза быстрее, чем (вершина) Джокоби, тогда как при пешеходных коэффициентах Пуассона он примерно в 3 раза медленнее.

Согласно ответу Джеда, MG использует умеренное огрубление, а DD - быстрое огрубление. Я думаю, что это имеет значение, когда они распараллелены. MG будет иметь множество связей и синхронизаций для прохождения многих уровней огрубления, которые эквивалентны однократному огрублению DD. Еще один момент из ответа Джеда: MG использует дешевый сглаживатель, а DD использует сильный сглаживатель. Учитывая эти два момента, сообщалось, что MG на грубых уровнях будет иметь плохие отношения коммуникации / вычисления. Таким образом, согласно закону Амдала , параллельное ускорение не хорошо. Решение проблемы - это коррекция параллельных грубых сеток, таких как предварительный кондиционер BPX., Кроме того, MG может использовать DD так же плавно, как указал Адамс, и MG также можно использовать в поддоменах DD. Исходя из соображений, на которые указал Баркер, я полагаю, что лучше использовать MG внутри DD, который использует параллелизм DD и оптимальную сложность MG.

Я хочу сделать одно небольшое дополнение к превосходному ответу Джеда, а именно, что мотивы двух подходов (или, по крайней мере, были) разные.

Декомпозиция домена мотивируется как метод параллельных вычислений. Специально для одноуровневых методов DD очень естественно реализовать на параллельной машине - вы разделяете домен на части и отдаете каждый кусок другому процессору. В некотором смысле мотивация DD заключается в разделении арифметических операций между процессорами.

Существуют хорошие параллельные многосеточные реализации, но это часто менее естественно делать параллельно. Вместо этого, мотивация мультисетки заключается в том, чтобы в первую очередь выполнять меньше арифметических операций.

$H$$h$$\mathcal{O}(\frac{1}{Hh})$

$h$$H$