page 2  (23 pages)
to previous section1
3to next section

A Parallel Version of the Unsymmetric Lanczos

Algorithm and its Application to QMR

H. Martin B?ucker? and Manfred Sauren

Zentralinstitut f?ur Angewandte Mathematik
Forschungszentrum J?ulich GmbH (KFA), D?52425 J?ulich, Germany

March 1, 1996


A new version of the unsymmetric Lanczos algorithm without look-ahead is described combining elements of numerical stability and parallel algorithm design. Firstly, stability is obtained by a coupled two-term procedure that generates Lanczos vectors scaled to unit length. Secondly, the algorithm is derived by making all inner products of a single iteration step independent such that global synchronization on parallel distributed memory computers is reduced. Among the algorithms using the Lanczos process as a major component, the quasi-minimal residual (QMR) method for the solution of systems of linear equations is illustrated by an elegant derivation. The resulting QMR algorithm maintains the favorable properties of the Lanczos algorithm while not increasing computational costs as compared with its corresponding original version.

1 Introduction

The key to many algorithms in engineering and scienti?c applications often involves the solution of large-scale eigenvalue problems that model oscillations or stability of some physical situation. Such problems are crucial in the analysis of complex dynamic systems. For example, computational physicists yield information about energy levels by investigating eigenvalue spectra in quantum mechanics. Structural engineers are led to eigenvalue problems in vibration analysis where the dynamic equations of motion model a structure subjected to a time-varying force. Control engineers use eigenanalysis to study the stability of large electric power systems whose response to small disturbances around an operating state is represented by a set of linearized equations. This list could easily be extended to molecular dynamics, plasma physics and others; see [27, 8] for illustrations from science and engineering.

Due to their overwhelming importance in applications, eigenproblems are among the most investigated issues in numerical linear algebra. Standard serial algorithms

?The research of this author was supported by the Graduiertenkolleg ?Informatik und Technik?, RWTH Aachen, D?52056 Aachen, Germany.