Numerical Control Structures for the Computation of Large Eigenvalue and Singular Value Problems

在数值程序的组件中，对精度影响最大的是可以称为数控结构的组件：收敛测试、停止准则、通货紧缩准则，以及识别需要特殊处理的问题实例。为了保证大矩阵计算的高精度，这些控制结构必须在代数上是合理的，并且在有限精度的算术中表现良好。这个项目将利用问题的结构和几何来设计数字控制结构。奇异值分解的结构将被用来确定误差的方向并发展摄动理论；子空间的几何和它们之间的角度将被用来设计数控结构。由此产生的摄动理论和控制结构有望导致通过逆迭代计算对称矩阵和奇异向量的特征向量的高精度实现，用于(扩展的)Golub-Reinsch算法的奇异值计算，以及用于QL算法的特征值计算。通过设计，(扩展的)Golub-Reinsch算法的数字控制结构在列缩放下是不变的。由于最近线性系统解、奇异值分解和特征分解的误差界表现出相同的不变性，因此将用数字控制结构来解释这些误差界的重要性和特殊形式。其目标是对问题条件和算法稳定性进行更现实的评估，这对于高度准确地解决大型问题尤其重要。

Among the components of a numerical program that have the greatest influence on accuracy are what can be called numerical control structures: convergence tests, stopping criteria, deflation criteria, and identification of problem instances that require special treatment. In order to guarantee high accuracy in computations with large matrices these control structures must be algebraically sound and perform well in finite precision arithmetic. This project will exploit the structure and geometry of a problem for the purpose of designing numerical control structures. The structure of the singular value decomposition will be used to determine the directions of errors and develop a perturbation theory; and the geometry of subspaces and angles between them will be used to design numerical control structures. The resulting perturbation theory and control structures are expected to lead to highly accurate implementations for the computation of eigenvectors of symmetric matrices and singular vectors by inverse iteration, for the computation of singular values by the (extended) Golub-Reinsch algorithm, and for the computation of eigenvalues by the QL algorithm. By design, the numerical control structures of the (extended) Golub- Reinsch algorithm are invariant under column scaling. Since recent error bounds for linear system solution, singular value decompositions, and eigendecompositions exhibit the same invariance, the numerical control structures will be employed to explain the significance and particular form of these error bounds. The goal is to produce more realistic assessments of problem conditioning and algorithm stability, which is especially important for highly accurate solution of large problems.