Multishift variants of the QZ algorithm with aggressive early deflation. (English) Zbl 1137.65017

Kågström, Bo; Kressner, Daniel

SIAM J. Matrix Anal. Appl. 29, No. 1, 199-227 (2006).

Multishift QZ iterations that chase a tightly coupled chain of bulge pairs instead of only one bulge pair per iteration are proposed. This allows the effective use of level 3 BLAS operations during the bulge chasing process, which in turn can provide efficient utilization of high performance computing systems with deep memory hierarchies. In addition, an extension of the aggressive early deflation strategy is proposed that can identify and deflate converged eigenvalues very quickly. As a result the number of overall QZ iterations needed until the convergence is considerably reduced.
Also, a new deflation algorithm is presented, which is particularly effective in the presence of large number of infinite eigenvalues. These developments are combined in an implementation that significantly improves existing implementations of the QZ algorithm. Several numerical experiments are presented.

Reviewer: Petko Hr. Petkov (Sofia)

MSC:

65F15	Numerical computation of eigenvalues and eigenvectors of matrices
15A22	Matrix pencils

Keywords:

generalized eigenvalue problem; QZ algorithm; multishifts; blocked algorithms; convergence; deflation algorithm; numerical experiments

Software:

BLAS; DSUBSP; GEMM; LAPACK; mctoolbox