Complex shift and invert strategies for real matrices

Beresford N. Parlett, Youcef Saad

Research output: Contribution to journalArticlepeer-review

46 Scopus citations

Abstract

When using an iterative method for solving a generalized nonsymmetric eigenvalue problem of the form Fu = λMu, where F and M are real banded matrices, it is often desirable to work with the shifted and inverted operator B = (F - σM)-1M in order to enhance the eigenvalue separation and improve efficiency. Unfortunately, the shift σ is generally complex, and so is the matrix B. The question then is whether it is possible to avoid complex arithmetic while preserving any advantages of bandedness of the pair (F, M). For the classical problem where M = I and F is banded, complex arithmetic can be avoided by using double shifts, i.e., by working with the real matrix BB̄, whose bandwidth is double that of F. This satisfactory solution extends to the case where M is diagonal as well. In the generalized case the answer to the above question is negative, in the sense that complex arithmetic can be avoided only at the expense of losing the advantage of bandedness. One solution is to factor the shifted matrix F - σM in complex arithmetic but employ real arithmetic subsequently in the iterative procedure. This paper examines several approaches and discusses their respective merits under various circumstances.

Original languageEnglish (US)
Pages (from-to)575-595
Number of pages21
JournalLinear Algebra and Its Applications
Volume88-89
Issue numberC
DOIs
StatePublished - Apr 1987
Externally publishedYes

Bibliographical note

Funding Information:
*The work of B. N. Parlett was supported in part by the Office of Naval Research under contract NOOO1476C~l3. The work of Y. Saad was supported in part by the Department of Energy under contract DEAC0%8lER10996 and in part by the Army Research Office under contract DAAG83-0177.

Fingerprint

Dive into the research topics of 'Complex shift and invert strategies for real matrices'. Together they form a unique fingerprint.

Cite this