Entwurf paralleler iterativer Verfahren mit kurzen Rekursionen für große dünnbesetzte lineare Gleichungssysteme.

Keywords

Authors

Abstract

For the solution of large sparse systems of linear equations with general non-Hermitian coefficient matrices, Krylov subspace methods based on short recurrences are developed. The design of these methods draws a distinction between generating a basis of the Krylov subspaces and defining a vector therein as the actual iterate. By this means, the design of parallel iterative variants for the solution of linear systems is reduced to the derivation of parallel underlying processes to span the Krylov subspaces. Parallel variants of the non-Hermitian Lanczos algorithm without look-ahead are used to derive versions of the quasi-minimal residual method (QMR) and the biconjugate gradient method (BCG) consisting of a single global synchronization point per iteration. Using the Intel Paragon XPS 10 and CRAY T3E with up to 512 nodes, it is demonstrated that these new versions are significantly more scalable than their original equivalents implemented on massively parallel computers. Moreover, the 1-norm quasi-minimal residual approach is introduced to define the actual iterates of a Krylov subspace method and it is shown that this approach leads to short recurrences, e.g., when the non-Hermitian Lanczos algorithm, the conjugate gradient squared method (CGS) or the biconjugate gradient stabilized method (Bi-CGSTAB) are used to span the underlying Krylov subspaces.