On correction equations and domain decomposition for computing invariant subspaces

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.