This award, from the computational mathematics program of the Division of Mathematical Sciences, supports the research of the principal investigator, which covers a balanced mix of theoretical investigations, software support and development, and advances for modern applications. The research focuses on design of new efficient robust parallel preconditioned methods for interior eigenvalue and singular value computations. The main emphasis is on the following challenging issues: investigating availability and efficiency of preconditioning; avoiding the folded spectrum approach, analyzing the possibility of computing the singular values of an operator using preconditioning; and establishing convergence theory for novel iterative solvers. For the latter, a novel application of classical majorization theory permits analysis of the convergence behavior of block eigenvalue and singular value solvers. This work is also relevant for applications; the singular vectors, corresponding to the largest singular values of a matrix are used for performing the principal component analysis of data described by a data matrix. Here the focus is on multi-dimensional image segmentation.
The topic of this research is motivated by the fact that the class of problems under consideration describes many phenomena in physics and mechanics, and for practical calculations may require extreme computational power. Advances in the computational approaches can provide noticeable improvements in the accuracy and efficiency of calculations. Implementing the developments in publicly available software enhances the potential for significant broader impact, due to the relevance of the software for a large range of applications. The application specifically targeted by the PI is image segmentation, such as occurs in tracking moving objects in videos. Additional impact of the project is on graduate student training. The research of the PI provides an opportunity to train students in important computational research motivated by real practical applications.
Preconditioned iterative solvers for eigenvalue computations continue gaining popularity in applications. In particular, the locally optimal block preconditioned conjugate gradient (LOBPCG) method has joined the ranks of the classical Davidson and Jacobi-Davidson methods as workhorses for numerical solution of extremely large eigenvalue problems, which compete with and often outperform the traditional Lanczos method. During this project, we worked on several fronts. ( 1 - improve the efficiency of LOBPCG ) We improved the efficiency of the BLOPEX method. (1-1) We introduced a novel strategy for constructing symmetric positive definite preconditioners for linear systems with symmetric indefinite matrices. The strategy, called absolute value preconditioning, is motivated by the observation that the preconditioned minimal residual method with the inverse of the absolute value of the matrix as a preconditioner converges to the exact solution of the system in at most two steps. Our numerical tests demonstrate practical effectiveness of the new MG preconditioner, which leads to a robust iterative scheme with minimalist memory requirements. (1-2) In another paper, we numerically analyzed the possibility of turning off post-smoothing (relaxation) in geometric multigrid when used as a preconditioner in conjugate gradient linear and eigenvalue solvers for the 3D Laplacian. ( 2 - theoretical understand the convergence of LOBPCG ) We deepened our theoretical understanding of the convergence of the BLOPEX method by obtaining new results on principal angles. (2-1) Principal angles between subspaces (PABS) (also called canonical angles) serve as a classical tool in mathematics, statistics, and applications, e.g., data mining. Traditionally, PABS are introduced via their cosines. The cosines and sines of PABS are commonly defined using the singular value decomposition. We utilize the same idea for the tangents, i.e., explicitly construct matrices, such that their singular values are equal to the tangents of PABS, using several approaches: orthonormal and non-orthonormal bases for subspaces, as well as projectors. Such a construction has applications, e.g., in analysis of convergence of subspace iterations for eigenvalue problems. (2-2) In our work, we bound the absolute change in the Rayleigh quotient (RQ) in terms of the norm of the residual and the change in the vector. If x is an eigenvector of a self-adjoint bounded operator A in a Hilbert space, then the RQ of the vector x, denoted by ρ(x), is an exact eigenvalue of A. In this case, the absolute change of the RQ |ρ(x) − ρ(y)| becomes the absolute error for an eigenvalue ρ(x) of A approximated by the RQ ρ(y) on a given vector y. There are three traditional kinds of bounds for eigenvalue errors: a priori bounds via the angle between vectors x and y; a posteriori bounds via the norm of the residual Ay − ρ(y)y of vector y; mixed type bounds using both the angle and the norm of the residual. We propose a unifying approach to prove known bounds of the spectrum, analyze their sharpness, and derive new sharper bounds. The proof approach is based on novel RQ vector perturbation identities. The scientific findings of the project have been disseminated by presenting them to scientific conferences and by publishing in peer-reviewed high quality journals. The webpage for our software BLOPEX is active and the software is well used by the community. Two PhD thesis were directly written as outcome of the project. The project also supported two recently PhD granted scientists and one first-year PhD student.
