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

This proposal is concerned with high relative accuracy iterative algorithms for com- puting a few eigenvalues/eigenvectors of a large symmetric positive definite matrix. Our goals are to develop numerically most accurate algorithms possible for computing eienval- ues/eigenvectors of differential operators and for computing elgenspaces of an alignment matrix arising in manifold-based nonlinear dimension reduction in machine learning and, at the same time, to lay a theoretical foundation for high relative accuracy algorithms in the setting of large scale eigenvalue problems. Intellectual Merit of the Proposed Activity: Eigenvalue computation is a fundamen- tal problem in numerical linear algebra. While there are numerous established algorithms for this, they do not guarantee in general to compute smaller eigenvalues, in a floating point arithmetic, to high relative accuracy. Indeed, the relative errors of smaller eigenvalues computed by conventional algorithms will be proportional to the condition number of the matrix. Over the last two decades, extensive research has been carried out on high relative accuracy eigenvalue algorithms, where several classes of special matrices have been identified for which the eigenvalues/eigenvectors can be computed to high relative accuracy (i.e. inde- pendent of the condition number). All existing high relative accuracy algorithms, however, appear to concern small (dense) matrices only. Yet, large scale matrices are often inherently ill-conditioned and it is typically a few smaller eigenvalues that are of interests. Therefore, the potential issues of relative accuracy would actually be more typical in the setting of large scale problems. We propose to initiate a study of high relative accuracy iterative algorithms for large scale eigenvalue problems. We shall focus on developing algorithms for matrices arising in two important applications where some special structure/properties may be exploited to achieve higher accuracy. Broader Impacts Resulting from the Proposed Activity: The discoveries from this proposed research are expected to impact a wide range of research areas of current sig- nificance. They will not only advance theoretical foundations and algorithm development for large scale eigenvalue problems, but also contribute to the general areas of applied sci- ence/engineering and machine learning where eigenvalue analysis and dimension reduction are essential. Our proposed algorithms have the promise of significantly improving the ac- curacy of existing algorithms without extra cost, and thus removing potential numerical accuracy issues that may present a significant challenge to many applications. Furthermore, our proposed activities would potentially increase awareness on the relative accuracy issues in large scale eigenvalue problems among practitioners in these application areas.