Какие рекомендации я должен использовать при поиске хороших методов предварительной обработки для конкретной проблемы?

Для решения больших линейных систем с использованием итерационных методов часто представляет интерес введение предобусловливания, например, вместо решения вместо решения , где здесь используется для предобусловливания системы влево. Как правило, мы должны иметь это и обеспечивать основу для (гораздо более) эффективного решения или сокращения вычислительных ресурсов (например, памяти) по сравнению с решением исходной системы (то есть, когда $Ax=b$ $M^{-1}(Ax=b)$ $M$ $M^{-1}\approx A^{-1}$ $M=A$ ). Однако, какие рекомендации мы должны использовать, чтобы выбрать предварительный кондиционер? Как практикующие делают это для своей конкретной проблемы?

linear-algebra iterative-method preconditioning Аллан П. Энгсиг-Каруп
источник

Даже для одного конкретного класса уравнений это потребует очень длинного и подробного ответа ...

Джек Полсон,

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

A

$A$

Аллан П. Энгсиг-Каруп

Я собираюсь направить канал @MattKnepley и сказать, что соответствующее действие - поиск литературы. Если это не помогло, попробуйте все доступные варианты для решения достаточно большой проблемы. Если это не поможет, подумайте о физике и о том, как вы можете найти приблизительное решение проблемы дешево, и используйте это в качестве предварительного условия.

Джек Полсон

@JackPoulson: Поскольку этот вопрос аналогичен тому, какой использовать разреженный линейный решатель системы? и Как выбрать масштабируемый линейный решатель , мне кажется по теме (хотя и широкий). Поскольку ваш комментарий в основном является ответом, не могли бы вы преобразовать его в ответ?

Джефф Оксберри

Я получил награду за этот вопрос, но мне также интересно видеть больше вопросов в этом ключе, которые могут быть лучше поставлены или ограничены определенным классом проблем.

Арон Ахмадиа

Ответы:

Изначально я не хотел давать ответ, потому что это заслуживает очень долгого обращения, и, надеюсь, кто-то еще даст его. Тем не менее, я могу дать очень краткий обзор рекомендуемого подхода:

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

Примерами 3 являются смещенные лапласовы версии Гельмгольца и недавняя работа Цзиньчао Сюй по предварительному условию бигармонического оператора лапласианами.

Джек Полсон
источник

Благодарность! Остальная часть этого комментария соответствует минимальному количеству символов.

Джефф Оксберри

Другие уже прокомментировали проблему предобусловливания того, что я буду называть «монолитными» матрицами, то есть, например, дискретизированной формы скалярного уравнения, такого как уравнение Лапласа, уравнение Гельмгольца или, если вы хотите обобщить, вектор-значение уравнение упругости. Для этих вещей ясно, что многосетка (алгебраическая или геометрическая) является победителем, если уравнение является эллиптическим, а для других уравнений это не совсем понятно - но что-то вроде SSOR часто работает достаточно хорошо (для некоторого значения "разумный").

Для меня большое открытие было то, что делать с задачами, которые не являются монолитными, например, для оператора Стокса Когда я начал численный анализ около 15 лет назад, я думаю, что у людей была надежда, что к таким матрицам могут быть применены те же методы, что и выше, и направление исследований заключалось в том, чтобы либо попробовать многосеточный метод напрямую, либо использовать обобщения SSOR (используя " точки сглаживают "как у Ваньки" и аналогичные методы. Но это исчезло, так как это не очень хорошо работает.

(\begin{matrix} A & В \\ В^{T} & 0 \end{matrix}),

$\begin{pmatrix} A & B \\ B^T & 0 \end{pmatrix}.$

То, что пришло на смену этому, было то, что первоначально называлось «основанными на физике предобработчиками», а позже просто (и, может быть, более точно) «блочными предобработчиками», такими как Сильвестр и Ватен. Они часто основаны на исключениях блоков или дополнениях Шура, и идея состоит в том, чтобы создать предварительный кондиционер таким образом, чтобы можно было повторно использовать предварительные кондиционеры для отдельных блоков, которые, как известно, работают хорошо. Например, в случае уравнения Стокса предварительный кондиционер Сильвестра / Ватена использует эту матрицу

{(\begin{matrix} A & В \\ 0 & В^{T} A^{- 1} В \end{matrix})}^{- 1}

$\begin{pmatrix} A & B \\ 0 & B^T A^{-1} B \end{pmatrix}^{-1}$ при использовании в качестве предварительного кондиционера с GMRES приведет к сходимости ровно за две итерации. Поскольку он треугольный, инверсия также намного проще, но у нас все еще остается проблема того, что делать с диагональными блоками, и там используются аппроксимации:

где тильда означает заменить точное обратное приближением. Это часто намного проще: посколькублок

является эллиптическим оператором,

(\begin{matrix} \tilde{A^{- 1}} & В \\ 0 & \tilde{(В^{T} A^{- 1} В)^{- 1}} \end{matrix})

$\begin{pmatrix} \widetilde{A^{-1}} & B \\ 0 & \widetilde{(B^T A^{-1} B)^{-1}} \end{pmatrix}$

A

$A$

\tilde{A^{- 1}}

$\widetilde{A^{-1}}$ например, хорошо аппроксимируется многосеточным V-циклом, и получается, что здесь

хорошо аппроксимируется ILU матрицы масс.

\tilde{(B^{T} A^{- 1} B)^{- 1}}

$\widetilde{(B^T A^{-1} B)^{-1}}$

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

Вольфганг Бангерт
источник

Человек, да, я так хотел щедрость! ;-)

Вольфганг Бангерт

Во втором абзаце: «Но это исчезло, потому что это не очень хорошо работает». Можете ли вы дать некоторое представление о том, почему это не очень хорошо работает? Есть ли обстоятельства, при которых это может работать?

Эндрю Т. Баркер

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

Вольфганг Бангерт

Что касается обобщения таких вещей, как Jacobi / SSOR / etc, на системы: большинство этих методов требуют, чтобы диагональные элементы матрицы были ненулевыми. Это явно не тот случай со Стоуксом. Таким образом, следующий простейший метод состоит в том, чтобы смотреть не на отдельные строки матрицы, а на блоки строк, например, на все строки для DoF, связанных с одной вершиной. Их называют «точечными сглаживателями» (точки, как в вершине), и они работают до некоторой степени, но они страдают от такого же снижения производительности, что и Jacobi / SSOR, когда проблемы становятся большими. Чтобы избежать этого, прекондиционеру необходимо глобально обмениваться информацией как мультисетка.

Вольфганг Бангерт

Multigrid, как известно, неэффективен при решении Гельмгольца, потому что, главным образом, из-за того, что колебательные моды низкой энергии трудно сгладить или представить в грубом пространстве. Была проделана некоторая работа над многосеточными волнами, но формулировка очень техническая, и на данный момент это не зрелая методология. Обратите внимание, что несимметричные системы также могут быть решены с помощью этого вида разложения блоков. В зависимости от выбора переменных (например, примитивных или консервативных), в предварительном кондиционере может потребоваться изменение базы для раскрытия заблокированной структуры.

Джед Браун

Джек дал хорошую процедуру для поиска предварительного кондиционера. Я попробую ответить на вопрос «Что делает хорошего предобусловливателя?». Оперативное определение:

$A x = b$ $M^{-1}$ $A^{-1}$

однако это не дает нам никакого представления о разработке предварительного кондиционера. Большинство предварительных кондиционеров основаны на манипулировании операторским спектром. Как правило, методы Крылова сходятся быстрее, когда собственные значения кластеризованы, см. Матричные итерации или Мероморфные функции и Линейная алгебра . Иногда мы можем доказать, что результаты предобусловливания - это всего лишь несколько уникальных собственных значений, например, Замечание о предобусловливании для неопределенных линейных систем .

Примером общей стратегии является Multigrid. Релаксационные предварительные кондиционеры (здесь сглаживающие), такие как SOR, удаляют высокочастотные компоненты в ошибке. Когда остаток проецируется на грубую сетку, компоненты погрешности более низкой частоты становятся более высокой частотой и могут снова подвергаться атаке SOR. Эта базовая стратегия лежит в основе более сложных версий MG, таких как AMG. Обратите внимание, что в нижней части решатель должен точно разрешить самые низкие частоты ошибки.

Другая стратегия заключается в решении уравнения в малых подпространствах, что и делают решатели Крылова. В простейшей форме это метод Качмарца или Аддитивный метод Шварца . Продвинутая деформация теории здесь, Разложение Домена , концентрируется на спектральной аппроксимации ошибки на границе раздела, поскольку предполагается, что домены решаются довольно точно.

$A$

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

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

Аллан П. Энгсиг-Каруп,

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

Мэтт Кнепли