Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations

Summary We introduce a class of n×n structured matrices which includes three well-known classes of generalized companion matrices: tridiagonal plus rank-one matrices (comrade matrices), diagonal plus rank-one matrices and arrowhead matrices. Relying on the structure properties of , we show that if A then A=RQ , where A=QR is the QR decomposition of A. This allows one to implement the QR iteration for computing the eigenvalues and the eigenvectors of any A with O(n) arithmetic operations per iteration and with O(n) memory storage. This iteration, applied to generalized companion matrices, provides new O(n²) flops algorithms for computing polynomial zeros and for solving the associated (rational) secular equations. Numerical experiments confirm the effectiveness and the robustness of our approach.The results of this paper were presented at the Workshop on Nonlinear Approximations in Numerical Analysis, June 22 – 25, 2003, Moscow, Russia, at the Workshop on Operator Theory and Applications (IWOTA), June 24 – 27, 2003, Cagliari, Italy, at the Workshop on Numerical Linear Algebra at Universidad Carlos III in Leganes, June 16 – 17, 2003, Leganes, Spain, at the SIAM Conference on Applied Linear Algebra, July 15 – 19, 2003, Williamsburg, VA and in the Technical Report 8]. This work was partially supported by MIUR, grant number 2002014121, and by GNCS-INDAM. This work was supported by NSF Grant CCR 9732206 and PSC CUNY Awards 66406-0033 and 65393-0034.