On correction equations and domain decomposition for computing invariant subspaces

Bernard Philippe, Yousef Saad

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

By considering the eigenvalue problem as a system of nonlinear equations, it is possible to develop a number of solution schemes which are related to the Newton iteration. For example, to compute eigenvalues and eigenvectors of an n × n matrix A, the Davidson and the Jacobi-Davidson techniques, construct 'good' basis vectors by approximately solving a "correction equation" which provides a correction to be added to the current approximation of the sought eigenvector. That equation is a linear system with the residual r of the approximated eigenvector as right-hand side. One of the goals of this paper is to extend this general technique to the "block" situation, i.e., the case where a set of p approximate eigenpairs is available, in which case the residual r becomes an n × p matrix. As will be seen, solving the correction equation in block form requires solving a Sylvester system of equations. The paper will define two algorithms based on this approach. For symmetric real matrices, the first algorithm converges quadratically and the second cubically. A second goal of the paper is to consider the class of substructuring methods such as the component mode synthesis (CMS) and the automatic multi-level substructuring (AMLS) methods, and to view them from the angle of the block correction equation. In particular this viewpoint allows us to define an iterative version of well-known one-level substructuring algorithms (CMS or one-level AMLS). Experiments are reported to illustrate the convergence behavior of these methods.

Original languageEnglish (US)
Pages (from-to)1471-1483
Number of pages13
JournalComputer Methods in Applied Mechanics and Engineering
Volume196
Issue number8
DOIs
StatePublished - Jan 20 2007

Bibliographical note

Funding Information:
Work supported by NSF grant ITR-0428774, by DOE under Grant DE-FG02-03ER25585, and by the Minnesota Supercomputing Institute.

Keywords

  • Algebraic Multilevel Substructuring (AMLS)
  • Correction equation
  • Domain decomposition
  • Eigenvalue problem
  • Jacobi-Davidson
  • Subspace correction

Fingerprint

Dive into the research topics of 'On correction equations and domain decomposition for computing invariant subspaces'. Together they form a unique fingerprint.

Cite this