Parallel implementation of an iterative algorithm for solving nonsymmetric linear systems with partial retention of spectral/singular information on explicit restarts

Authors

  • S.A. Kharchenko

Keywords:

parallel iterative algorithm
explicit restarts
subspace condition
additional preconditioning

Abstract

A parallel implementation of the SOFGMRES(m) iterative algorithm with partial retention of information on explicit restarts is discussed. An arbitrary initial subspace is an important degree of freedom for this algorithm. From the convergence substantiation of the SOFGMRES(m) algorithm it follows that an appropriately chosen initial subspace can be considered as an additional preconditioner, since this subspace reduces the generalized condition number of a matrix and accelerates the convergence of the SOFGMRES(m) algorithm. The numerical results show the reliability of the proposed algorithm and its algebraic and parallel efficiency compared to the classical Krylov subspace-type algorithms.

New computational technologies

Downloads

Published

2010-11-18

Issue

Vol. 11 (2010): Issue 4.

Section

Section 1. Numerical methods and applications

Author Biography

S.A. Kharchenko

TESIS, LLC
• Researcher

References

  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.