Параллельная реализация итерационного алгоритма решения несимметричных систем линейных уравнений с частичным сохранением спектральной/сингулярной информации при явных рестартах

Авторы

  • C.А. Харченко

Ключевые слова:

параллельный итерационный алгоритм
явные рестарты
обусловленность на подпространстве
дополнительное предобусловливание

Аннотация

Предложена параллельная реализация итерационного алгоритма SOFGMRES(m) с частичным сохранением информации при явных рестартах. В алгоритме имеется важная степень свободы — произвольное начальное подпространство. Из обоснования сходимости алгоритма SOFGMRES(m) следует, что начальное подпространство при его правильном выборе можно рассматривать как дополнительное предобусловливание, поскольку оно уменьшает обобщенную обусловленность матрицы на подпространстве и ускоряет сходимость алгоритма. Результаты экспериментов показывают надежность, алгебраическую и параллельную эффективность предложенного алгоритма по сравнению с классическими алгоритмами типа подпространств Крылова. Работы выполнена в рамках государственного контракта № 02.514.11.4125 с Министерством образования и науки РФ. Статья рекомендована к печати программным комитетом международной научной конференции «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи» (http://agora.guru.ru/abrau2010)


Загрузки

Опубликован

2010-11-18

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

C.А. Харченко

ООО «ТЕСИС»
ул. Юннатов, 18, 127083, Москва
• научный сотрудник


Библиографические ссылки

  1. Aksenov A., Dyadkin A., Pokhilko V. Overcoming of barrier between CAD and CFD by modified finite volume method // Proc. 1998 ASME Pressure Vessels and Piping Division Conference. San Diego, ASME PVP. 1998.
  2. Aksenov A.A., Kharchenko S.A., Konshin V.N., Pokhilko V.I. FlowVision software: numerical simulation of industrial CFD applications on parallel computer systems // Parallel CFD 2003 Conference. Book of Abstracts. Moscow, 2003. 280-284.
  3. Тыртышников Е.Е. Краткий курс численного анализа. Москва: ВИНИТИ, 1994.
  4. Paige C.C., Saunders M.A. LSQR: An algorithm for sparse linear equations and sparse least squares // ACM Transactions on Mathematical Software. 1982. 8, N 1. 43-71.
  5. Freund R.W., Nachtigal N.M. QMR: a quasi-minimal residual method for non-Hermitian linear systems // Numer. Math. 1991. 60. 315-339.
  6. Van der Vorst H.A. Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems // SIAM J. Sci. Stat. Comput. 1992. 13, N 2. 631-644.
  7. Saad Y., Schultz M.H. GMRES: A generalized minimum residual algorithm for solving non-symmetric linear systems // SIAM J. Sci. Stat. Comput. 1986. 7. 856-869.
  8. Morgan R.B. Implicitly restarted GMRES and Arnoldi methods for nonsymmetric systems of equations // SIAM J. Matrix Anal. Appl. 2000. 21, N 4. 1112-1135.
  9. Харченко С.А., Еремин А.Ю. Новые алгоритмы типа GMRES(k) с рестартами и анализ их свойств сходимости на основе QR-формы матричных соотношений // Зап. науч. семин. ЛОМИ. 2000. 268. 190-241.
  10. Дядькин А.А., Харченко С.А. Алгоритмы декомпозиции области и нумерации ячеек с учетом локальных адаптаций расчетной сетки при параллельном решении систем уравнений в пакете FlowVision // Тр. Международной научной конференции «Научный сервис в сети Internet: многоядерный компьютерный мир». Москва, 2007. 201-206.
  11. Харченко С.А. Влияние распараллеливания вычислений с поверхностными межпроцессорными границами на масштабируемость параллельного итерационного алгоритма решения систем линейных уравнений на примере уравнений вычислительной гидродинамики // Тр. Международной научной конференции «Параллельные вычислительные технологии (ПаВТ’2008)’’, Санкт-Петербург, 28 января-1 февраля 2008 г. Челябинск: Изд-во ЮУрГУ, 2008. 494-499.
  12. Сушко Г.Б., Харченко С.А. Экспериментальное исследование на СКИФ МГУ «Чебышев» комбинированной MPI+threads реализации алгоритма решения систем линейных уравнений, возникающих во FlowVision при моделировании задач вычислительной гидродинамики // Тр. Международной научной конференции «Параллельные вычислительные технологии (ПаВТ’2009)’’, Нижний Новгород, 30 марта-3 апреля 2009 г. Челябинск: Изд-во ЮУрГУ, 2009. 316-324.
  13. Walker H.F. Implementation of the GMRES method using householder transformations // SIAM J. on Sci. and Stat. Comp. 1988. 9, N 1. 152-163.
  14. Intel Threading Building Blocks Tutorial-1.6 / Intel Corp. 2007.