FAST COMPUTATION OF THE ZEROS OF A POLYNOMIAL VIA FACTORIZATION OF THE COMPANION MATRIX

被引：18

作者：

Aurentz, Jared L. ^{[1
]}

Vandebril, Raf ^{[2
]}

Watkins, David S. ^{[1
]}

机构：

[1] Washington State Univ, Dept Math, Pullman, WA 99164 USA

[2] Katholieke Univ Leuven, Dept Comp Sci, B-3001 Heverlee, Belgium

来源：

SIAM JOURNAL ON SCIENTIFIC COMPUTING | 2013年 / 35卷 / 01期

关键词：

polynomial; root; companion matrix; QR algorithm; HESSENBERG MATRICES; ALGORITHMS;

D O I：

10.1137/120865392

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A new fast algorithm for computing the zeros of a polynomial in O(n(2)) time using O(n) memory is developed. The eigenvalues of the Frobenius companion matrix are computed by applying a nonunitary analogue of Francis's implicitly shifted QR algorithm to a factored form of the matrix. The algorithm achieves high speed and low memory use by preserving the factored form. It also provides a residual and an error estimate for each root. Numerical tests confirm the high speed of the algorithm.

引用

页码：A255 / A269

页数：15

共 12 条

[1]

[Anonymous], 2010, Fundamentals of Matrix Computations

[2] Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices [J].

Bini, D. A. ;

Eidelman, Y. ;

Gemignani, L. ;

Gohberg, I. .

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2007, 29 (02) :566-585

[3] A fast implicit QR eigenvalue algorithm for companion matrices [J].

Bini, D. A. ;

Boito, P. ;

Eidelman, Y. ;

Gemignani, L. ;

Gohberg, I. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (08) :2006-2031

[4]

Chandrasekaran S, 2008, OPER THEORY ADV APPL, V179, P111

[5] A note on companion matrices [J].

Fiedler, M .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2003, 372 :325-331

[6] THE QR TRANSFORMATION .2. [J].

FRANCIS, JGF .

COMPUTER JOURNAL, 1962, 4 (04) :332-345

[7] THE QR ALGORITHM FOR UNITARY HESSENBERG MATRICES [J].

GRAGG, WB .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 1986, 16 (01) :1-8

[8] Implicit double shift QR-algorithm for companion matrices [J].

Van Barel, Marc ;

Vandebril, Raf ;

Van Dooren, Paul ;

Frederix, Katrijn .

NUMERISCHE MATHEMATIK, 2010, 116 (02) :177-212

[9]

Vandebril R., 2008, Matrix Computations and Semiseparable Matrices, Volume II: Eigen- value and Singular Value Methods., V2

[10]

Watkins D.S., 2007, MATRIX EIGENVALUE PR

← 1 2 →