В таких методах, как gmres или bicgstab, может быть привлекательным использовать другой метод Крылова в качестве предварительного кондиционера. В конце концов, их легко реализовать без матрицы и в параллельной среде. Например, один кул может использовать несколько (скажем, ~ 5) итераций необусловленного bigcstab в качестве предварительного условия для gmres или любой другой комбинации методов Крылова. Я не нахожу много ссылок на такой подход в литературе, поэтому я ожидаю, что это потому, что он не очень эффективен. Я хотел бы понять, почему это не эффективно. Есть ли случаи, когда это хороший выбор?
В моих исследованиях меня интересует решение трехмерных эллиптических задач в параллельной (mpi) среде.
linear-algebra
linear-solver
preconditioning
krylov-method
gmres
Кристина Дарку
источник
источник
Ответы:
Интересно, что этот вопрос возник вчера, поскольку вчера я только что закончил реализацию, которая делает это.
Мой фон
Для начала, дайте мне знать, что, хотя мое образование основано на научных вычислениях, вся работа, которую я выполнял с момента выпуска, включая мою нынешнюю степень доктора философии. работа, была в области вычислительной электромагнетизма. Итак, я думаю, что наши фоны несколько похожи, так как вы также, похоже, смотрите на физику (основываясь на вашем профиле).
FGMRES
Во-первых, то, что вы ищете, как уже упоминал Гвидо Каншат в комментарии, называется Flexible GMRES или FGMRES. Ссылка, включая псевдокод, есть в [1]. Хотя я иногда нахожу числовые документы SIAM немного трудными для чтения, [1] (и большая часть других работ Саада, включая блестящую [B1], по-видимому, легально доступную для бесплатного онлайн), она отличается; статья представляет собой увлекательное чтение, очень четко написано и содержит несколько хороших примеров и предложений для приложений.
FGMRES прост в реализации, особенно если у вас уже есть работающее ПРАВО предварительно подготовленное GMRES. Обратите внимание на ключевое слово RIGHT здесь - если у вас есть предварительно обработанные GMRES LEFT, то есть вы привыкли решать MAx = Mb, вам придется внести несколько изменений. Сравните [B1, Алгоритм 9.4 на стр. 282] до [B1, Алгоритм 9.5, с. 284]. Вы также можете найти FGMRES в [B1, Алгоритм 9.6, стр. 287], но я бы очень рекомендовал вам прочитать [1], поскольку он короткий, хорошо написан и по-прежнему содержит много интересных деталей.
Что оно делает
FGMRES в основном позволяет переключать предварительные кондиционеры для каждой итерации, если вы хотите. Одним из приложений для этого является то, что вы можете использовать некоторый предварительный кондиционер, который очень хорошо работает, когда вы находитесь далеко от решения, а затем переключаться на другой, когда вы приближаетесь. [2], который я не читал подробно, похоже, обсуждает нечто подобное.
Тем не менее, наиболее интересное применение в моем случае состояло в том, что вы можете использовать (предварительно подготовленный) GMRES в качестве предварительного кондиционера для вашего FGMRES. Это причина типичного названия FGMRES, «внутренняя-внешняя GMRES». Здесь «внешний» относится к решателю FGMRES, который (как предварительный обработчик) использует «внутренний» решатель.
Итак, насколько это хорошо на практике?
В моем случае это сработало абсолютно блестяще. Во внутреннем цикле я «решаю» формулировку моей проблемы с уменьшенной сложностью. Само по себе это решение слишком неточно для нашего использования, но оно прекрасно работает в качестве предварительного кондиционера. Обратите внимание на "" вокруг "решить" - нет необходимости запускать внутренний решатель для сходимости, поскольку вы ищете только приблизительные приближения. В моем случае я перешел от использования 151 итерации, каждая из которых стоила 64 секунды, к 72 итерациям, каждая из которых стоила 79 секунд (я использовал фиксированные 5 итераций во внутренней GMRES). Это полная экономия одного часа без потери точности и очень небольшой работы по кодированию, поскольку у нас уже был функционирующий GMRES, который мы только что сделали рекурсивным.
Для некоторых применений этого материала, демонстрирующих потенциальную производительность, см. [3] (который фактически использует трехуровневый FGMRES, поэтому FGMRES, с FGMRES как внутренним, с GMRES как внутренним-внутренним) и [4], который может быть слишком Приложение предназначено для вашего использования, но содержит несколько интересных тестовых случаев.
Ссылки
[1] Ю. Саад, «Гибкий алгоритм GMRES с внутренним и внешним условием», SIAM J. Sci. Comp., Vol. 14, нет 2, с. 461–469, март 1993 г. http://www-users.cs.umn.edu/~saad/PDF/umsi-91-279.pdf
[2] Д.-З. Дин, Р.-С. Чен и З. Фан, «Предусмотренное SSOR внутренне-внешнее гибкое GMRES-метод для MLFMM-анализа рассеяния открытых объектов», Progress In Electromagnetics Research, vol. 89, стр. 339–357, 2009. http://www.jpier.org/PIER/pier89/22.08112601.pdf
[3] Т. Ф. Эйберт, «Некоторые результаты рассеяния, вычисленные с помощью поверхностно-интегрального уравнения и гибридных методов конечных элементов и границ-интегралов, ускоренных многоуровневым быстрым мультипольным методом», IEEE Antennas and Propagation Magazine, vol. 49, нет. 2, с. 61–69, 2007.
[4] Ö. Ergül, T. Malas, L. Gürel, «Решения крупномасштабных задач электромагнетизма с использованием итерационной внутренней-внешней схемы с обычными и приближенными многоуровневыми быстрыми мультипольными алгоритмами», Progress In Electromagnetics Research, vol. 106, с. 203–223, 2010. http://www.jpier.org/PIER/pier106/13.10061711.pdf
[B1] Ю. Саад, Итерационные методы для разреженных линейных систем. SIAM, 2003. http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf
источник
Такой вложенный метод подпространств Крылова может хорошо работать на практике. Это может представлять интерес для несимметричных линейных систем, для которых перезапущенный GMRES застаивается, а незапущенный GMRES слишком дорогой или использует слишком много памяти. Немного литературы:
источник