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 -