Structured matrix methods for polynomial root-finding

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Structured matrix methods for polynomial root-finding

Full text

Pdf (189 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 2007 international symposium on Symbolic and algebraic computation table of contents

Waterloo, Ontario, Canada

SESSION: Contributed papers table of contents

Pages: 175 - 180

Year of Publication: 2007

ISBN:978-1-59593-743-8

Author

Luca Gemignani

University of Pisa, Pisa, Italy

Sponsors

ACM: Association for Computing Machinery
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 48, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1277548.1277573 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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 , I. Gohberg, Fast QR Eigenvalue Algorithms for Hessenberg Matrices Which Are Rank-One Perturbations of Unitary Matrices, SIAM Journal on Matrix Analysis and Applications, v.29 n.2, p.566-585, March 2007 [doi>10.1137/050627563]
	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	Dario A. Bini , Luca Gemignani , Victor Y. Pan, Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations, Numerische Mathematik, v.100 n.3, p.373-408, May 2005 [doi>10.1007/s00211-005-0595-4]
	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	Steven Fortune, Polynomial root finding using iterated Eigenvalue computation, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.121-128, July 2001, London, Ontario, Canada [doi>10.1145/384101.384119]
	19	Steven Fortune, An iterated eigenvalue algorithm for approximating roots of univariate polynomials, Journal of Symbolic Computation, v.33 n.5, p.627-646, May 2002 [doi>10.1006/jsco.2002.0526]
	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	Brian T. Smith, Error Bounds for Zeros of a Polynomial Based Upon Gerschgorin's Theorems, Journal of the ACM (JACM), v.17 n.4, p.661-674, Oct. 1970 [doi>10.1145/321607.321615]
	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.