Domain decomposition algorithms for the solution of sparse symmetric generalized eigenvalue problems
2018-09
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Domain decomposition algorithms for the solution of sparse symmetric generalized eigenvalue problems
Authors
Published Date
2018-09
Publisher
Type
Thesis or Dissertation
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.
Description
University of Minnesota Ph.D. dissertation. September 2018. Major: Computer Science. Advisor: Yousef Saad. 1 computer file (PDF); xix, 175 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.