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

49

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

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

JM
источник

Ответы:

33

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

Мэтт Кнепли
источник
2
«Брось в нее все, что можешь» - вот совет, к которому я привык. :) Третий документ, на который вы ссылаетесь, - это то, чего я раньше не видел; Спасибо за это!
JM
2
У Мэтта отличный ответ, но вы должны принять его в контексте сообщества, из которого он исходит (крупномасштабные научные вычисления). Вы обнаружите, что для небольших задач (скажем, менее ста тысяч неизвестных) этот прямой решатель значительно превосходит итерационные методы, если задача не является сильно эллиптической. Я не видел в литературе хороших общих статей, которые бы направили вас к первоначальной стартовой стратегии, что немного смущает меня.
Арон Ахмадиа
5
Оценка Арона хороша, но сильно зависит от заполнения, так как редкие прямые методы обычно исчерпывают память, прежде чем они истощают терпение.
Мэтт Кнеплей
18

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

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

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

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

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

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

  • Итерационные методы, когда матрица коэффициентов разрежена, а прямые методы не могут эффективно использовать разреженность (избегайте создания заполнения).
  • Прямые методы для нескольких правых частей.
  • Итерационные методы могут быть более эффективными, если точность менее важна
  • Итерационные методы для нелинейных систем уравнений.
Аллан П. Энгсиг-Каруп
источник
8
Я думаю, что важно отметить, что прямые методы не всегда лучше для нескольких правых частей. Возможно, они лучше для правых частей, но если итерационный метод а прямой метод , все же выгодно использовать итерационный решатель для правые стороны. O(n)O(n)O(n2)O(1)
Джек Поулсон
8

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

Пол
источник
5
Этот ответ, кажется, создает впечатление, что эффективность многосетки заключается в нахождении правильной первоначальной догадки. На самом деле первоначальное предположение - это небольшая проблема для линейных задач, а на самом деле это проблема только для Full Multigrid. Многосетка работает за счет спектрального разделения. Обратите внимание, что создание многосеточной системы хорошо справляется с трудными задачами. Multigrid работает довольно хорошо параллельно, он был ключевым компонентом нескольких призов Gordon Bell, и несколько пакетов с открытым исходным кодом работают с высокой эффективностью на самых больших современных машинах. Для реализации GPU, посмотрите на библиотеку CUSP.
Джед Браун
В большинстве случаев случайное начальное предположение достаточно хорошо. При извлечении собственных значений с использованием алгоритма Ланцоша случайный вектор запуска / перезапуска действительно помогает. Перезапуски случаются время от времени в алгоритме Ланцоша.
AnilJ
3

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

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

Гвидо Каншат
источник