Numerical Linear Algebra and Eigenvalue Computations

本计画将研究求解中至大规模特征值与广义特征值问题的数值演算法。为解决代数特征值问题，提出了一种改进型QR算法。新算法避免了传统多位移QR算法的偏移模糊现象，从而大大降低了算法的收敛速度。新方法显示出能够使用几乎任意数量的同时移位而不会对收敛速率产生实质性不利影响的希望。它应该在具有高级架构（包括分层缓存存储和指令流水线）的计算机上实现“blas - 371”速度。此外，变体算法将使用早期通缩程序，有望大幅减少所需的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.