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.