TY - JOUR

T1 - On correction equations and domain decomposition for computing invariant subspaces

AU - Philippe, Bernard

AU - Saad, Yousef

PY - 2007/1/20

Y1 - 2007/1/20

N2 - 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.

AB - 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.

KW - Algebraic Multilevel Substructuring (AMLS)

KW - Correction equation

KW - Domain decomposition

KW - Eigenvalue problem

KW - Jacobi-Davidson

KW - Subspace correction

UR - http://www.scopus.com/inward/record.url?scp=33751093300&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33751093300&partnerID=8YFLogxK

U2 - 10.1016/j.cma.2006.03.026

DO - 10.1016/j.cma.2006.03.026

M3 - Article

AN - SCOPUS:33751093300

SN - 0045-7825

VL - 196

SP - 1471

EP - 1483

JO - Computer Methods in Applied Mechanics and Engineering

JF - Computer Methods in Applied Mechanics and Engineering

IS - 8

ER -