High Relative Accuracy Iterative Algorithms for Large Scale Matrix Eigenvalue Problems with Applications

University Of Kentucky Research Foundation, Lexington KY

Investigators

Abstract

Eigenvalue computation is a fundamental problem in numerical linear algebra. While there are numerous established algorithms for this, they do not guarantee in general to compute, in a floating point arithmetic, smaller eigenvalues to high relative accuracy. Indeed, the relative errors of smaller eigenvalues computed by conventional algorithms are proportional to the condition number of the matrix. Research over the last two decades has resulted in several classes of special matrices for which the eigenvalues/eigenvectors can be computed to high relative accuracy (i.e. independent of the condition number). All existing high relative accuracy algorithms, however, appear to concern small (dense) matrices only. Yet, large matrices are often inherently ill-conditioned and it is typically a few smaller eigenvalues that are of interests. The goals of this proposal are to study high relative accuracy iterative algorithms for computing a few eigenvalues/eigenvectors of a large symmetric positive definite matrix. The investigator will develop algorithms for matrices arising in some important applications such as discretization of differential operators and dimensionality reduction in machine learning, where special structure/properties of the matrices may be exploited to achieve higher accuracy. Spectral (eigenvalue) analysis is a widely used mathematical tool in science and engineering. Eigenvalues of differential operators describe the natural vibrating frequencies of mechanical structures. Dimensionality reduction of high-dimensional data in machine learning often leads to minimization of certain quadratic functionals, the solutions of which are eigenvectors. Solving such eigenvalue problems to high relative accuracy pose a challenge to existing algorithms. Therefore, the proposed works will not only advance theoretical foundations and algorithm developments for large scale eigenvalue problems, but also contribute to the general areas of applied science/engineering and machine learning by significantly improving the accuracy of the algorithms used in these applications.