Fast computation of eigenvalues of companion,comrade, and related matrices |
| |
Authors: | Jared L Aurentz Raf Vandebril David S Watkins |
| |
Institution: | 1. Department of Mathematics, Washington State University, Pullman, WA, 99164-3113, USA 2. Department of Computer Science, KU Leuven, 3001, Leuven, (Heverlee), Belgium
|
| |
Abstract: | The class of eigenvalue problems for upper Hessenberg matrices of banded-plus-spike form includes companion and comrade matrices as special cases. For this class of matrices a factored form is developed in which the matrix is represented as a product of essentially 2×2 matrices and a banded upper-triangular matrix. A non-unitary analogue of Francis’s implicitly-shifted QR algorithm that preserves the factored form and consequently computes the eigenvalues in O(n 2) time and O(n) space is developed. Inexpensive a posteriori tests for stability and accuracy are performed as part of the algorithm. The results of numerical experiments are mixed but promising in certain areas. The single-shift version of the code applied to companion matrices is much faster than the nearest competitor. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|