Domain decomposition algorithms for the solution of sparse symmetric generalized eigenvalue problems

Abstract

This dissertation focuses on the design, implementation, and evaluation of domain decomposition techniques for the solution of large and sparse algebraic symmetric generalized eigenvalue problems. Domain decomposition techniques begin by partitioning the global (discretized) domain into a number of subdomains. The solution of the algebraic eigenvalue problem is then decoupled into two separate subproblems: (1) one defined locally in the interior of each subdomain, and (2) one defined on the interface region connecting neighboring subdomains. As soon as the part of the solution associated with the interface region is computed, the part of the solution associated with the interior variables in each subdomain can be computed locally and independently of the rest of the subdomains. The domain decomposition techniques proposed in this dissertation can be classified into two categories: (1) filtering techniques, and (2) root-finding techniques. Filtering techniques are projection methods applied to a transformation of the original matrix pencil chosen so that, ideally, the eigenvalues of interest are mapped to the only nonzero eigenvalues in the transformed pencil. This dissertation combines domain decomposition with filtering approaches and demonstrates how this class of hybrid algorithms can outperform current state-of-the-art filtering techniques. Apart being well-suited for execution on distributed memory systems, an immediate advantage of such hybrid techniques is that any orthogonalization necessary needs to be performed only to vectors whose length is equal to the number of interface variables. Moreover, we show that if the filter is applied only to that portion of the pencil associated with the interface variables, it is possible to even achieve convergence within a number of steps that is smaller than the number of eigenvalues located inside the interval of interest. In contrast, any projection method applied to a transformation of the original matrix pencil must perform a number of steps that is at least equal to the number of eigenvalues located inside the interval of interest. Implementation aspects of the proposed numerical schemes on many-core/multi-core computer systems and experiments on serial/distributed computing environments are also discussed. Root-finding techniques convert the interface eigenvalue problem into one of computing roots of scalar functions, i.e., the eigenvalues of the original eigenvalue problem are roots of a carefully chosen scalar function. This allows the use of existing fast iterative root-finding schemes, e.g. Newton's method, for the solution of symmetric generalized eigenvalue problems. Root-finding techniques can be especially useful when only a few eigenvalues and associated eigenvectors are sought. The numerical schemes proposed in this part of the present dissertation are compared against other single-vector eigenvalue solvers such as the Rayleigh Quotient Iteration and Residual Inverse Iteration. Numerous theoretical details and practical considerations are considered. Implementation aspects of the proposed numerical schemes on multi-core computer systems and experiments on serial/distributed computing environments are also presented.