Advertisement
Published in:
2008 | OriginalPaper | Chapter
A Fast QR Algorithm for Companion Matrices
Authors : Shiv Chandrasekaran, Ming Gu, Jianlin Xia, Jiang Zhu
Published in: Recent Advances in Matrix and Operator Theory
Publisher: Birkhäuser Basel
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
It has been shown in [
4
,
5
,
6
,
31
] that the Hessenberg iterates of a companion matrix under the QR iterations have low off-diagonal rank structures. Such invariant rank structures were exploited therein to design fast QR iteration algorithms for finding eigenvalues of companion matrices. These algorithms require only O(
n
) storage and run in O(n
2
) time where
n
is the dimensiosn of the matrix. In this paper, we propose a new O(n
2
) complexity QR algorithm for real companion matrices by representing the matrices in the iterations in their sequentially semi-separable (SSS) forms [
9
,
10
]. The bulge chasing is done on the SSS form QR factors of the Hessenberg iterates. Both double shift and single shift versions are provided. Deflation and balancing are also discussed. Numerical results are presented to illustrate both high efficiency and numerical robustness of the new QR algorithm.