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

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

Как определить, использовать ли прямой или итерационный метод? Сделав этот выбор, как выбрать определенный алгоритм? Я уже знаю об использовании симметрии (например, использовать сопряженный градиент для разреженной симметричной положительно определенной системы), но есть ли другие соображения, подобные этому, которые следует учитывать при выборе метода?

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

Выбор между прямым и итерационным методами зависит от поставленных целей и задач.

Для прямых методов мы можем отметить:

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

Для итерационных методов мы можем отметить:

• Цель состоит в том, чтобы дать частичный результат только после небольшого количества итераций.
• Усилия по решению должны быть меньше, чем прямые методы для той же проблемы.
• Экономичный в отношении хранения (без заполнения)
• Часто легко программировать.
• Известное приблизительное решение может быть использовано.
• Иногда они быстрые, а иногда нет (иногда даже расходящиеся).
• Для сложных задач итерационные методы значительно менее устойчивы по сравнению с прямыми методами.

Рекомендации, когда использовать прямые или итерационные методы?

• Итерационные методы, когда матрица коэффициентов разрежена, а прямые методы не могут эффективно использовать разреженность (избегайте создания заполнения).
• Прямые методы для нескольких правых частей.
• Итерационные методы могут быть более эффективными, если точность менее важна
• Итерационные методы для нелинейных систем уравнений.

Я полностью согласен с уже даными ответами. Я хотел добавить, что все итерационные методы требуют некоторого начального предположения. Качество этого первоначального предположения часто может влиять на скорость сходимости выбранного вами метода. Такие методы, как Jacobi, Gauss Seidel и Successive Over Relaxation, все работают для итеративного «сглаживания» как можно большего количества ошибок на каждом шаге ( подробности см. В этой статье).) Первые несколько шагов довольно быстро уменьшают высокочастотную ошибку, но низкочастотная погрешность требует гораздо больше итераций для сглаживания. Это то, что делает сближение медленным для этих методов. В таких случаях, как это, мы можем ускорить сходимость, решая сначала низкочастотную ошибку (например, решая ту же проблему на более грубой сетке), затем решая ошибку более высокой частоты (например, на более мелкой сетке). Если мы применяем эту концепцию рекурсивно, разделяй и властвуй, мы получим то, что называется многосеточным методом. Даже если линейная система не является симметричной, существуют альтернативные реализации многосеточного метода для любой неособой разреженной матричной системы (например, алгебраический многосеточный метод), которая может ускорить сходимость решателя. Однако их масштабируемость на параллельных системах является предметом множества исследований.,

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

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