Numerical Linear Algebra and Eigenvalue Computations

数值线性代数和特征值计算

• 批准号: 9732671
• 负责人: Ralph Byers
• 金额: $ 16.34万
• 依托单位: University of Kansas Center for Research Inc
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-05-15 至 2002-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9732671&HistoricalAwards=false
• 关键词: Numerical; Linear; Algebra; Eigenvalue; Computations

This project will investigate numerical algorithms for solving moderate to large scale eigenvalue and generalized eigenvalue problems. A variant QR algorithm is being developed for solving the algebraic eigenvalue problem. The new algorithm avoids the phenomenon of shift blurring that dramatically slows the rate of convergence of the conventional multi-shift QR algorithm. The new approach shows promise of being able to use nearly any number of simultaneous shifts without substantial adverse affect on the converge rate. It should achieve "BLAS-3 71 speeds on computers with advanced architectures including hierarchical cache storage and instruction pipelining. In addition, the variant algorithm will use an early deflation procedure that promises to substantially reduce the number of Hessenberg QR steps needed. A generalized algebra of relations is being used to analyze and modify algorithms for moderately large scale eigenvalue problems. These include the inverse free spectral divide and conquer algorithm and other generalizations of the matrix sign function. The location/verification problem for the large scale eigenvalue problem will also be attacked. The initial approach will use a rational function approximation to the trace of a spectral projection in order to count eigenvalues inside a target region. The computational work required by this approach is expected not to be closely related to the number of eigenvalues in the region. This may make it attractive for locating eigenvalue clusters. In the verification setting, many eigenvalues in the target region have already been located by some other numerical method, e.g., a Krylov subspace method. In this case, the approximate trace of the spectral projector determines whether there are unlocated eigenvalues in the target region.

该项目将研究用于解决中到大规模特征值和广义特征值问题的数值算法。 正在开发一种变体 QR 算法来解决代数特征值问题。 新算法避免了移位模糊现象，该现象大大降低了传统多移位 QR 算法的收敛速度。 新方法有望能够使用几乎任意数量的同时移位，而不会对收敛速度产生重大不利影响。 它应该在具有高级架构（包括分层缓存存储和指令流水线）的计算机上实现“BLAS-3 71 速度。此外，变体算法将使用早期紧缩过程，有望大幅减少所需的 Hessenberg QR 步骤数量。广义关系代数用于分析和修改中等规模特征值问题的算法。其中包括逆自由 谱分治算法和矩阵符号函数的其他推广。 大规模特征值问题的定位/验证问题也将受到攻击。 最初的方法将使用有理函数逼近光谱投影的轨迹，以便计算目标区域内的特征值。 这种方法所需的计算工作预计不会与该区域的特征值数量密切相关。 这可能会使 对于定位特征值簇很有吸引力。 在验证设置中，目标区域中的许多特征值已经通过一些其他数值方法（例如克雷洛夫子空间方法）定位。 在这种情况下，光谱投影仪的近似轨迹确定目标区域中是否存在未定位的特征值。