×

A parallel version of the quasi-minimal residual method based on coupled two-term recurrences. (English) Zbl 0888.65036

Waśniewski, Jerzy (ed.) et al., Applied parallel computing: industrial computation and optimization. Third international workshop, PARA ’96, Lyngby, Denmark, August 18–21, 1996. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1184, 157-165 (1996).
Summary: For the solution of linear systems of equations with unsymmetric coefficient matrix, R. W. Freund and N. M. Nachtigal [SIAM J. Sci. Comput. 15, No. 2, 313-337 (1994; Zbl 0803.65036)] proposed a Krylov subspace method called quasi-minimal residual method (QMR). The two main ingredients of QMR are the unsymmetric Lanczos algorithm and the quasi-minimal residual approach that minimizes a factor of the residual vector rather than the residual itself. The Lanczos algorithm spans a Krylov subspace by generating two sequences of biorthogonal vectors called Lanczos vectors. Due to the orthogonalization and scaling of the Lanczos vectors, algorithms that make use of the Lanczos process contain inner products leading to global communication and synchronization on parallel processors.
For massively parallel computers, these effects cause delays preventing scalability of the implementation. Consequently, parallel algorithms should avoid global synchronization as far as possible. We propose a new version of QMR with the following properties: Firstly, the Lanczos process is based on coupled two-term recurrences; secondly, both sequences of Lanczos vectors are scalable; and finally, there is only a single global synchronization point per iteration. The efficiency of this algorithm is demonstrated by numerical experiments on a PARAGON system using up to 121 processors.
For the entire collection see [Zbl 0856.00039].

MSC:

65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65Y05 Parallel numerical computation

Citations:

Zbl 0803.65036
PDFBibTeX XMLCite