Numerical Linear Algebra and Eigenvalue Computations

本计画将探讨求解中大型本征值与广义本征值问题的数值演算法。 一个变体QR算法正在开发解决的代数特征值问题。 新算法避免了传统多移位QR算法中的移位模糊现象，从而大大降低了算法的收敛速度。 新的方法表明，能够使用几乎任何数量的同时转移，而不会对收敛速度产生实质性的不利影响的承诺。 它应该达到“BLAS-3 71速度的计算机与先进的体系结构，包括分层高速缓存存储和指令流水线。 此外，变体算法将使用早期放气程序，该程序有望大幅减少所需的Hessenberg QR步骤的数量。 一个广义关系代数被用来分析和修改算法的中等规模的特征值问题。 这些包括逆自由谱分治算法和矩阵符号函数的其他推广。 大规模特征值问题的定位/验证问题也将受到攻击。 最初的方法将使用有理函数逼近光谱投影的轨迹，以便计算目标区域内的特征值。 这种方法所需的计算工作预计不会密切相关的本征值的数量在该地区。 这可能使它有吸引力的定位特征值集群。 在验证设置中，目标区域中的许多特征值已经通过一些其他数值方法定位，例如，Krylov子空间方法。 在这种情况下，光谱投影仪的近似轨迹确定在目标区域中是否存在未定位的特征值。

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.