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

用于计算大特征值和奇异值问题的数控结构

• 批准号: 9102853
• 负责人: Ilse C.F. Ipsen
• 金额: $ 18.17万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-08-15 至 1995-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9102853&HistoricalAwards=false
• 关键词: Numerical; Control; Structures; Computation; Large

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.

在对准确性影响最大的数值程序的组成部分中，可以称为数值控制结构：收敛测试，停止标准，通缩标准和确定需要特殊待遇的问题实例。 为了确保具有较大矩阵的计算中的高精度，这些控制结构必须在代数上是合理的，并且在有限的精确算术中表现良好。 该项目将利用问题的结构和几何形状，以设计数值控制结构。 奇异值分解的结构将用于确定错误的方向并发展出扰动理论。它们之间的几何形状和它们之间的角度将用于设计数值控制结构。 预计所产生的扰动理论和控制结构将导致高度准确的实现，以计算通过反迭代来计算对称矩阵和奇异向量的特征向量，以通过（扩展的）Golub-Reinsch算法计算奇异值，并通过QL AlgorithM的计算来计算（扩展的）Golub-Reinsch algorithm。 根据设计，（扩展）Golub-Reinsch算法的数值控制结构在列缩放下是不变的。 由于最新的线性系统解决方案的误差界限，奇异值分解和特征异常表现出相同的不变性，因此将使用数值控制结构来解释这些误差界的重要性和特定形式。 目的是对问题调理和算法稳定性进行更现实的评估，这对于高度准确的大问题解决方案尤为重要。