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

点击翻译按钮获取中文摘要

Eigenvalue computation is a fundamental problem in numericallinear algebra. While there are numerous established algorithmsfor this, they do not guarantee in general to compute, in afloating point arithmetic, smaller eigenvalues to high relativeaccuracy. Indeed, the relative errors of smaller eigenvaluescomputed by conventional algorithms are proportional to thecondition number of the matrix. Research over the last twodecades has resulted in several classes of special matricesfor which the eigenvalues/eigenvectors can be computed to highrelative accuracy (i.e. independent of the condition number).All existing high relative accuracy algorithms, however, appearto concern small (dense) matrices only. Yet, large matrices areoften inherently ill-conditioned and it is typically a fewsmaller eigenvalues that are of interests. The goals of thisproposal are to study high relative accuracy iterativealgorithms for computing a few eigenvalues/eigenvectors of alarge symmetric positive definite matrix. The investigator willdevelop algorithms for matrices arising in some importantapplications such as discretization of differential operatorsand dimensionality reduction in machine learning, where specialstructure/properties of the matrices may be exploited toachieve higher accuracy.Spectral (eigenvalue) analysis is a widely used mathematicaltool in science and engineering. Eigenvalues of differentialoperators describe the natural vibrating frequencies ofmechanical structures. Dimensionality reduction ofhigh-dimensional data in machine learning often leads tominimization of certain quadratic functionals, the solutions ofwhich are eigenvectors. Solving such eigenvalue problems tohigh relative accuracy pose a challenge to existing algorithms.Therefore, the proposed works will not only advance theoreticalfoundations and algorithm developments for large scaleeigenvalue problems, but also contribute to the general areasof applied science/engineering and machine learning bysignificantly improving the accuracy of the algorithms used inthese applications.