Почему мой итерационный линейный решатель не сходится?

26

Что может пойти не так, если использовать методы Крылова из KSP ( пакет линейного решателя PETSc ) с предварительными именами для решения разреженной линейной системы, например, полученной путем дискретизации и линеаризации уравнений в частных производных?

Какие шаги я могу предпринять, чтобы определить, что идет не так для моей проблемы?

Какие изменения я могу внести, чтобы успешно и эффективно решить мою линейную систему?

Джед браун
источник
Предполагаете ли вы, что этот вопрос будет вопросом об итерационных линейных решателях, в частности, в PETSc (что я и собирал из основного текста вопроса), или вопросом о потенциальных алгоритмических сбоях итерационных линейных решателей в основном программно агностический контекст (что я бы собрал, взглянув только на заголовок)?
Джефф Оксберри
4
У него есть petscтег. Методология общая, но я думаю, что ответ был бы менее полезным, если бы каждое «попробуй это» также не включало «как». Альтернативно, «как» должно быть намного более длинным (и более подверженным ошибкам для зрителя), если бы его нужно было объяснить программно-независимым способом. Если кто-то захочет объяснить, как делать все эти вещи, используя другой пакет, я с радостью сделаю вопрос независимым от программного обеспечения и поменяю свой ответ, заявив, что он описывает, что делать в PETSc. Примечание: я добавил это, что является расширенной версией часто задаваемых вопросов, поэтому я мог бы понравиться людям на этом сайте.
Джед Браун

Ответы:

26

Первоначальный совет

  • Всегда пытайтесь -ksp_converged_reason -ksp_monitor_true_residualпонять, почему метод не сходится.
  • Сделайте размер проблемы и количество процессов как можно меньше, чтобы продемонстрировать сбой. Вы часто получаете понимание, определяя, какие мелкие проблемы демонстрируют поведение, которое приводит к поломке вашего метода и сокращению времени оборота. Кроме того, существуют некоторые методы исследования, которые можно использовать только для небольших систем.
  • Если проблема возникает только после большого количества временных шагов, шагов продолжения или нелинейных шагов решения, рассмотрите возможность записи состояния модели при сбое, чтобы вы могли быстро экспериментировать.
  • В качестве альтернативы, особенно если ваше программное обеспечение не имеет возможности контрольных точек, используйте -ksp_view_binaryили MatView()для сохранения линейной системы, а затем используйте код $PETSC_DIR/src/ksp/ksp/examples/tutorials/ex10.cдля чтения в матрице и ее решения (возможно, с другим числом процессов). Для этого требуется собранная матрица, поэтому ее полезность может быть несколько ограничена.
  • Существует много возможных вариантов решателя (например, бесконечное число, доступное в командной строке в PETSc из-за произвольного числа уровней композиции), см. Этот вопрос для общего совета по выбору линейных решателей.

Общие причины, по которым KSP не сходится

  • Уравнения являются сингулярными случайно (например, забыли наложить граничные условия). Проверьте это для небольшой проблемы с использованием -pc_type svd -pc_svd_monitor. Также попробуйте прямой решатель с -pc_type lu(например, через сторонний пакет параллельно -pc_type lu -pc_factor_mat_solver_package superlu_dist).
  • Уравнения намеренно сингулярны (например, постоянное нулевое пространство), но метод Крылова не был информирован, см KSPSetNullSpace().
  • Уравнения намеренно сингулярны и KSPSetNullSpace()использовались, но правая часть не согласована. Возможно, вам придется позвонить MatNullSpaceRemove()с правой стороны, прежде чем звонить KSPSolve().
  • Уравнения неопределенны, так что стандартные предварительные кондиционеры не работают. Обычно вы узнаете это по физике, но вы можете проверить это с помощью -ksp_compute_eigenvalues -ksp_gmres_restart 1000 -pc_type none. Для простых проблем седловой точки, попробуйте -pc_type fieldsplit -pc_fieldsplit_type schur -pc_fieldsplit_detect_saddle_point. См. Руководство пользователя и справочную страницу PCFIELDSPLIT для получения более подробной информации. Для более сложных проблем прочитайте литературу, чтобы найти надежные методы и спросите здесь (или petsc-users@mcs.anl.govили petsc-maint@mcs.anl.gov), если вам нужен совет о том, как их реализовать. Например, посмотрите этот вопрос для высокой частоты Гельмгольца. Для скромных размеров проблемы, посмотрите, можете ли вы жить с помощью прямого решателя.
  • Если метод сходится в предобусловленном остатке, но не в истинном остатке, предобусловливатель, вероятно, является единичным или почти таким же. Это характерно для задач седловой точки (например, несжимаемый поток) или сильно несимметричных операторов (например, гиперболические задачи с низким Махом с большими временными шагами).
  • Предварительный кондиционер слишком слабый или нестабильный. Посмотрите, -pc_type asm -sub_pc_type luулучшает ли скорость сходимости. Если GMRES теряет слишком много прогресса при перезапуске, посмотрите, поможет ли более длительный перезапуск -ksp_gmres_restart 300. Если доступна транспонирование, попробуйте -ksp_type bcgsдругие способы, не требующие перезапуска. (Обратите внимание, что сходимость с этими методами часто ошибочна.)
  • Матрица предварительного кондиционирования может быть не близка к оператору (возможно, не разобранному). Попробуйте решить с помощью прямого решателя, либо последовательно, -pc_type luлибо параллельно, используя сторонний пакет (например -pc_type lu -pc_factor_mat_solver_package superlu_dist, или mumps). Метод должен сходиться за одну итерацию, если матрицы одинаковы, а в противном случае - за «небольшое» количество итераций. Попробуйте -snes_type testпроверить матрицы при решении нелинейной задачи.
  • Предусловие является нелинейным (например, вложенное итеративное решение), попробуйте -ksp_type fgmres or -ksp_type gcr.
  • Вы используете геометрическую многосетку, но некоторые уравнения (часто граничные условия) не совместимы между уровнями. Попробуйте -pc_mg_galerkinалгебраически построить правильно масштабированный грубый оператор или убедитесь, что все уравнения масштабируются одинаково, если вы хотите использовать повторно дискретизированные грубые уровни.
  • Матрица очень плохо обусловлена. Проверьте номер условия, используя методы, описанные здесь . Попробуйте улучшить его, выбрав относительное масштабирование компонентов / граничных условий. Попробуй -ksp_diagonal_scale -ksp_diagonal_scale_fix. Возможно, измените постановку задачи, чтобы получить более дружественные алгебраические уравнения. Если вы не можете исправить масштабирование, вам может понадобиться прямой решатель.
  • Матрица является нелинейной (например, оценивается с использованием конечного дифференцирования нелинейной функции). Попробуйте разные параметры разности (например -mat_mffd_type ds). Попробуйте использовать более высокую точность, чтобы сделать различие более точным ./configure --with-precision=__float128 --download-f2cblaslapack. Проверьте, сходится ли он в «более простых» режимах параметров.
  • Симметричный метод используется для несимметричной задачи.
  • Классический Грам-Шмидт становится нестабильным, попробуйте -ksp_gmres_modifiedgramschmidtили используйте метод, который ортогонализирует по-разному, например -ksp_type gcr.
Джед браун
источник
16

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

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

Вольфганг Бангерт
источник
5
-pc_type lu -pc_factor_mat_solver_type umfpackиспользовать UMFPACK (или -pc_type cholesky -pc_factor_mat_solver_package cholmodдля проблем с SPD) через PETSc, но учтите, что UMFPACK и CHOLMOD являются последовательными. Для параллельного использования, -pc_factor_mat_solver_package superlu_distили mumps, pastix, spooles.
Джед Браун
2
Просто чтобы быть ясно, полный набор параметров для использования (например) superlu_distбудет -ksp_type preonly -pc_type lu -pc_factor_mat_solver_package superlu_dist. Это правильно?
Леон Эйвери
Я не знаю. Что произойдет, если вы сделаете это?
Вольфганг Бангерт