Article

Structured matrix methods for polynomial root-finding

Author:

Luca GemignaniAuthors Info & Claims

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

Pages 175 - 180

https://doi.org/10.1145/1277548.1277573

Published: 29 July 2007 Publication History

Abstract

In this paper we discuss the use of structured matrix methods for the numerical approximation of the zeros of a univariate polynomial. In particular, it is shown that root-finding algorithms based on floating-point eigenvalue computation can benefit from the structure of the matrix problem to reduce their complexity and memory requirements by an order of magnitude.

References

[1]

D. A. Bini, F. Daddi, and L. Gemignani. On the shifted QR iteration applied to companion matrices. Electron. Trans. Numer. Anal., 18:137--152 (electronic), 2004.

[2]

D. A. Bini, Y. Eidelman, L. Gemignani, and I. Gohberg. Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices. Technical Report 1587, Dipartimento di Matematica, Università di Pisa, 2005. In press in SIAM J. Matrix Anal. Appl.

Digital Library

[3]

D. A. Bini, Y. Eidelman, L. Gemignani, and I. Gohberg. The unitary completion and QR iterations for a class of structured matrices. In press in Mathematics of Computation.

[4]

D. A. Bini and G. Fiorentino. Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numer. Algorithms, 23(2-3):127--173, 2000.

[5]

D. A. Bini, L. Gemignani, and V. Y. Pan. Improved initialization of the accelerated and robust QR-like polynomial root-finding. Electron. Trans. Numer. Anal., 17:195--205 (electronic), 2004.

[6]

D. A. Bini, L. Gemignani, and V. Y. Pan. Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations. Numer. Math., 100(3):373--408, 2005.

Digital Library

[7]

C. Carstensen. Linear construction of companion matrices. Linear Algebra and Appl., 149:191--214, 1991.

[8]

S. Chandrasekaran, M. Gu, J. Xia, and J. Zhu. A fast QR algorithm for companion matrices. 2006.

[9]

J. Della-Dora. Numerical linear algorithms and group theory. Linear Algebra and Appl., 10:267--283, 1975.

[10]

S. Delvaux and M. Van Barel. Unitary rank structured matrices. Technical Report TW464, Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3000 Leuven (Heverlee), Belgium, July 2006.

[11]

P. Dewilde and A. J. van der Veen. Time-varying systems and computations. Kluwer Academic Publishers, Boston, MA, 1998.

[12]

Y. Eidelman, L. Gemignani, and I. Gohberg. On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms. Linear Algebra Appl., 420, 2007.

[13]

Y. Eidelman and I. Gohberg. On a new class of structured matrices. Integral Equations Operator Theory, 34:293--324, 1999.

[14]

Y. Eidelman and I. Gohberg. Fast inversion algorithms for a class of structured operator matrices. Linear Algebra Appl., 371:153--190, 2003.

[15]

Y. Eidelman, I. Gohberg, and V. Olshevsky. The QR iteration method for Hermitian quasiseparable matrices of an arbitrary order. Linear Algebra Appl., 404:305--324, 2005.

[16]

L. Elsner. On some algebraic problems in connection with general eigenvalue algorithms. Linear Algebra Appl., 26:123--138, 1979.

[17]

D. Fasino. Rational Krylov matrices and QR steps on Hermitian diagonal-plus-semiseparable matrices. Numer. Linear Algebra Appl., 12(8):743--754, 2005.

[18]

S. Fortune. Polynomial root finding using iterated eigenvalue computation. In Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, pages 121--128 (electronic), New York, 2001. ACM.

Digital Library

[19]

S. Fortune. An iterated eigenvalue algorithm for approximating roots of univariate polynomials. J. Symbolic Comput., 33(5):627--646, 2002. Computer algebra (London, ON, 2001).

Digital Library

[20]

L. Gemignani. Quasiseparable structures of companion pencils under the QZ-algorithm. Calcolo, 42(3-4):215--226, 2005.

[21]

G. I. Hargreaves. Topics in matrix computations: stability and efficiency of algorithms. PhD thesis, School of Mathematics, University of Manchester, 2005.

[22]

B. T. Smith. Error bounds for zeros of a polynomial based upon Gerschgorin's theorems. J. Assoc. Comput. Mach., 17:661--674, 1970.

Digital Library

[23]

F. Uhlig. The DQR algorithm, basic theory, convergence, and conditional stability. Numer. Math., 76(4):515--553, 1997.

[24]

R. Vandebril, M. Van Barel, and N. Mastronardi. An implicit QR algorithm for symmetric semiseparable matrices. Numer. Linear Algebra Appl., 12(7):625--658, 2005.

Cited By

De Terán FHernando C(2019)A note on generalized companion pencils in the monomial basisRevista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas10.1007/s13398-019-00760-y114:1Online publication date: 6-Dec-2019
https://doi.org/10.1007/s13398-019-00760-y
Diao HMeng Q(2019)Structured generalized eigenvalue condition numbers for parameterized quasiseparable matricesBIT Numerical Mathematics10.1007/s10543-019-00748-559:3(695-720)Online publication date: 6-Apr-2019
https://doi.org/10.1007/s10543-019-00748-5
de Terán FDopico FPérez J(2015)Backward stability of polynomial root-finding using Fiedler companion matricesIMA Journal of Numerical Analysis10.1093/imanum/dru057(dru057)Online publication date: 30-Jan-2015
https://doi.org/10.1093/imanum/dru057
Show More Cited By

Index Terms

Structured matrix methods for polynomial root-finding
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis

Recommendations

New progress in real and complex polynomial root-finding

Matrix methods are increasingly popular for polynomial root-finding. The idea is to approximate the roots as the eigenvalues of the companion or generalized companion matrix associated with an input polynomial. The algorithms also solve secular ...
Real and complex polynomial root-finding with eigen-solving and preprocessing
ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

Recent progress on root-finding for polynomial and secular equations largely relied on eigen-solving for the associated companion and diagonal plus rank-one generalized companion matrices. By applying to them Rayleigh quotient iteration, we could have ...
Implicit QR for rank-structured matrix pencils
Abstract
A fast implicit QR algorithm for eigenvalue computation of low rank corrections of Hermitian matrices is adjusted to work with matrix pencils arising from zerofinding problems for polynomials expressed in Chebyshev-like bases. The modified QZ ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

July 2007

406 pages

ISBN:9781595937438

DOI:10.1145/1277548

General Chair:
Dongming Wang
Beihang University and UPMC-CNRS (China/France)

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC07

Sponsor:

ISSAC07: International Symposium on Symbolic and Algebraic Computation

July 29 - August 1, 2007

Ontario, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
258
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

De Terán FHernando C(2019)A note on generalized companion pencils in the monomial basisRevista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas10.1007/s13398-019-00760-y114:1Online publication date: 6-Dec-2019
https://doi.org/10.1007/s13398-019-00760-y
Diao HMeng Q(2019)Structured generalized eigenvalue condition numbers for parameterized quasiseparable matricesBIT Numerical Mathematics10.1007/s10543-019-00748-559:3(695-720)Online publication date: 6-Apr-2019
https://doi.org/10.1007/s10543-019-00748-5
de Terán FDopico FPérez J(2015)Backward stability of polynomial root-finding using Fiedler companion matricesIMA Journal of Numerical Analysis10.1093/imanum/dru057(dru057)Online publication date: 30-Jan-2015
https://doi.org/10.1093/imanum/dru057
Melman A(2010)Generalizations of Gershgorin disks and polynomial zerosProceedings of the American Mathematical Society10.1090/S0002-9939-10-10294-9138:7(2349-2364)Online publication date: 10-Mar-2010
https://doi.org/10.1090/S0002-9939-10-10294-9
Lucas KJana P(2010)Parallel algorithms for finding polynomial Roots on OTIS-torusThe Journal of Supercomputing10.1007/s11227-009-0312-754:2(139-153)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1007/s11227-009-0312-7
Pan VMurphy BRosholt RTang YWang XZheng A(2008)Eigen-solving via reduction to DPR1 matricesComputers & Mathematics with Applications10.1016/j.camwa.2007.09.01256:1(166-171)Online publication date: 1-Jul-2008
https://dl.acm.org/doi/10.1016/j.camwa.2007.09.012

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten