Multishift Variants of the QZ Algorithm with Aggressive Early Deflation
Multishift Variants of the QZ Algorithm with Aggressive Early Deflation
复制标题
具有积极早期通货紧缩功能的 QZ 算法的多档变体
DOI：
10.1137/05064521x
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
D. Kressner
中科院分区：
文献类型：
--
作者：
B. Kågström;D. Kressner
提出了求解广义特征值问题的QZ算法的新变种。提出了一种扩展的小凸起多移位QR算法，该算法在每次QZ迭代中追踪多个小凸起的链而不是一个凸起。这允许有效地使用第3级BLAS操作，这进而可以提供对具有深存储器层次结构的高性能计算系统的有效利用。此外，提出了一种扩展的积极的早期紧缩策略，它可以识别和紧缩收敛的特征值之前，经典的紧缩策略。因此，直到收敛所需的总QZ迭代次数大大减少。作为第三成分，我们重新考虑无限特征值的紧缩，并提出了一个新的紧缩算法，这是特别有效的存在大量的无限特征值。结合所有这些发展，我们的实现显着改善现有的QZ算法的实现。这是证明了随机矩阵对的数值实验，以及与矩阵对所产生的各种应用程序。
New variants of the QZ algorithm for solving the generalized eigenvalue problem are proposed. An extension of the small-bulge multishift QR algorithm is developed, which chases chains of many small bulges instead of only one bulge in each QZ iteration. This allows the effective use of level 3 BLAS operations, which in turn can provide efficient utilization of high performance computing systems with deep memory hierarchies. Moreover, an extension of the aggressive early deflation strategy is proposed, which can identify and deflate converged eigenvalues long before classic deflation strategies would. Consequently, the number of overall QZ iterations needed until convergence is considerably reduced. As a third ingredient, we reconsider the deflation of infinite eigenvalues and present a new deflation algorithm, which is particularly effective in the presence of a large number of infinite eigenvalues. Combining all these developments, our implementation significantly improves existing implementations of the QZ algorithm. This is demonstrated by numerical experiments with random matrix pairs as well as with matrix pairs arising from various applications.