В каких случаях применения схемы аддитивного прекондиционирования превосходят мультипликативные?

12

Как в методах декомпозиции доменов (DD), так и в многосеточных (MG) можно применять применение блочных обновлений или грубых исправлений как аддитивное или мультипликативное . Для точечных решателей это различие между итерациями Якоби и Гаусса-Зейделя. Мультипликативный сглаживатель для действующий как , применяется как $Ax = b$ $S(x^{old}, b) = x^{new}$

$x_{i+1} = S_n(S_{n-1}( ..., S_1(x_i, b) ..., b), b)$

и добавка разглаживающая применяется как

$x_{i+1} = x_{i} + \displaystyle\sum_{\ell = 0}^{n}\lambda_\ell(S_\ell(x_i, b) - x_i)$

для некоторого демпфирования . Похоже, что общее мнение заключается в том, что мультипликативные сглаживатели обладают гораздо более быстрыми свойствами сходимости, но мне было интересно: при каких ситуациях производительность аддитивных вариантов этих алгоритмов лучше? $\lambda_i$

Более конкретно, есть ли у кого-либо случаи использования, когда аддитивный вариант должен и / или действительно работает значительно лучше, чем мультипликативный вариант? Есть ли теоретические причины для этого? Большая часть литературы по многосеточным сетям довольно пессимистична в отношении аддитивного метода, но в контексте DD он используется так часто, как аддитивный Шварц. Это также распространяется на гораздо более общую проблему составления линейных и нелинейных решателей, а также на то, какой тип конструкций будет работать хорошо и работать параллельно.

linear-algebra performance multigrid domain-decomposition Питер Брюн
источник

6

Аддитивные методы предоставляют больше параллелизма. Обычно они работают быстрее, чем мультипликативные методы, если вы можете использовать этот параллелизм. Например, грубые уровни многосетки обычно ограничены по времени ожидания. Если вы переместите грубые уровни в меньшие подкоммуникаторы, то они могут быть решены независимо от более тонких уровней. С мультипликативной схемой, все процессы должны ждать, пока грубые уровни решены.

Кроме того, если алгоритм требует сокращений на каждом уровне, аддитивный вариант может быть в состоянии объединить их, когда мультипликативный метод вынужден выполнять их последовательно.

Джед браун
источник

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

Питер Брюн

1

Мультипликативные версии многих алгоритмов должны хранить больше информации, но иногда сходятся примерно так же быстро. Иногда аддитивные варианты симметричны, но сделать мультипликативную симметричность может быть гораздо больше работы. С помощью fieldsplit предобусловливатель может стать более приближенным, когда вы добавите эти дополнительные решения. Мы можем продемонстрировать это на примере PETSc Stokes, если хотите. Аддитив всегда проще векторизовать / сделать более параллельным, но любой выигрыш в производительности зависит от конкретной проблемы и архитектуры.

Джед Браун

5

Для задач SPD аддитивные методы лучше для сглаживания MG по нескольким причинам, как уже упоминалось, и еще несколько:

@Article{Adams-02, 
author = {Adams, M.~F. and Brezina, M. and Hu, J. J. and Tuminaro, R. S.}, 
title = {Parallel multigrid smoothing: polynomial versus {G}auss-{S}eidel}, 
journal = {J. Comp. Phys.}, 
year = {2003}, 
volume = {188}, 
number = {2}, 
pages = {593-610} }

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

Адамс
источник

0

Я еще раз повторю сказанное @Jed: метод Multiplicative всегда сходится как минимум так же, как и метод Additive (асимптотически), поэтому вы выигрываете только на основе параллелизма, но это зависит от архитектуры.

Мэтт Кнепли
источник

Не является технически правильным, спектры итерационной матрицы, скажем, для Гаусса-Зейделя не превосходят Якоби равномерно (например, одно собственное значение убивается за одну итерацию Якоби). Марк (как мне выйти как Джед ...)

Джед Браун

В каких случаях применения схемы аддитивного прекондиционирования превосходят мультипликативные?

Ответы: