Implicit QR for Companion-like Pencils
Provides a faster and more memory-efficient algorithm for polynomial zerofinding, a key problem in numerical linear algebra.
The paper adapts an implicit QR algorithm for eigenvalue computation of low-rank corrections of unitary matrices to handle matrix pencils from polynomial zerofinding, achieving O(N^2) ops and O(N) memory. Numerical experiments confirm its effectiveness and stability.
A fast implicit QR algorithm for eigenvalue computation of low rank corrections of unitary matrices is adjusted to work with matrix pencils arising from polynomial zerofinding problems . The modified QZ algorithm computes the generalized eigenvalues of certain NxN rank structured matrix pencils using O(N^2) ops and O(N) memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.