# Computing interior eigenvalues and corresponding eigenvectors of definite matrix pairs

Miloloža Pandur, Marija (2016) Computing interior eigenvalues and corresponding eigenvectors of definite matrix pairs. Doctoral thesis, Faculty of Science > Department of Mathematics.

 Preview
PDF
Language: Croatian

The generalized eigenvalue problem (GEP) for given matrices $A, B \in \mathbb{C}^{n \times n}$ is to find scalars $\lambda$ and nonzero vectors $x \in \mathbb{C}^n$ such that $Ax = \lambda Bx$ (1). The pair $(\lambda, x)$ is called an eigenpair, $\lambda$ is an eigenvalue and $x$ corresponding eigenvector. GEP (1) where A and B are both Hermitian, or real symmetric, occurs in many applications of mathematics. Very important case is when B (and A) is positive definite (appearing, e.g., in the finite element discretization of self-adjoint and elliptic PDE-eigenvalue problem [25]). Another very important case is when B (and A) is indefinite, but the matrix pair (A, B) is definite, meaning, there exist real numbers $\alpha, \beta$ such that the matrix $\alpha A + \beta B$ is positive definite (appearing, e.g., in mechanics [83] and computational quantum chemistry [4]). Many theoretical properties (variational principles, perturbation theory, etc.) and eigenvalue solvers for Hermitian matrix are extended to definite matrix pairs [64, 79, 83]. A Hermitian matrix pair (A, B) is called positive (negative) definite if there exists a real $\lambda_0$ such that $A- \lambda_0 B$ is positive ( negative) definite. The set of all such $\lambda_0$ is an open interval called the definiteness interval [83], and any such $\lambda_0$ will be called definitizing shift. In the first part of this thesis we propose new algorithms for detecting definite Hermitian matrix pairs (A, B). The most simple algorithms we propose are based on testing the main submatrices of order 1 or 2. These algorithms do not have to give a final answer about (in)definiteness of the given pair, so we develop a more efficient subspace algorithm assuming B is indefinite. Our subspace algorithm for detecting definiteness is based on iterative testing of small full compressed matrix pairs formed using test-subspaces of small dimensions. It is generalization of the method of coordinate relaxation proposed in [36, Section 3.6]. We also propose acceleration of the subspace algorithm in a way that certain linear systems must be solved in every or in some iteration steps. If the matrix pair is definite, the subspace algorithm detects if it is positive or negative definite and returns one definitizing shift. The subspace algorithm is particulary suited for large, sparse and banded matrix pairs, and can be used in testing hyperbolicity of a Hermitian quadratic matrix polynomial. Numerical experiments are given which illustrate efficiency of several variants of our subspace algorithm and comparison is made with an arc algorithm [19, 17, 29]. In the second part of this thesis we are interested in solving partial positive definite GEP (1) where B (and A) is indefinite (both A and B can be singular). Specifically, we are interested in iterative algorithms which will compute a small number of eigenvalues closest to the definiteness interval and corresponding eigenvectors. These algorithms are based on trace minimization property [41, 49]: find the minimum of the trace of the function: $f(X)=X^HAX$ such that $X^HBX=diag(I_{k_+}, -I_{k_-})$ where $X \in \mathbb{C}^{n \times (k_++k_-)}, 1 \leq k_+ \leq n_+, 1 \leq k_- \leq n_-$ and $(n_+, n_-, n_0)$ is the inertia of B. The class of algorithms we propose will be preconditioned gradient type iteration, suitable for large and sparse matrices, previously studied for the case with A and/or B are known to be positive definite (for a survey of preconditioned iterations see [3, 39]). In the recent paper [42] an indefinite variants of LOBPCG algorithm [40] were suggested. The authors of [42] were not aware of any other preconditioned eigenvalue solver tailored to definite matrix pairs with indefinite matrices. In this thesis we propose some new preconditioned eigenvalue solvers suitable for this case, which include truncated and extended versions of indefinite LOBPCG from [42]. Our algorithms use one or two definitizing shifts. For the truncated versions of indefinite LOBPCG, which we call indefinite BPSD/A, we derive a sharp convergence estimates. Since for the LOBPCG type algorithms there are still no sharp convergence estimates, estimates derived for BPSD/A type methods serve as an upper (non-sharp) convergence estimates. We also devise some possibilities of using our algorithms to compute a modest number of eigenvalues around any spectral gap of a definite matrix pair (A, B). Numerical experiments are given which illustrate efficiency and some limitations of our algorithms.