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.