Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

A combinatorial construction of high order algorithms for finding polynomial roots of known multiplicity


Authors: Yi Jin and Bahman Kalantari
Journal: Proc. Amer. Math. Soc. 138 (2010), 1897-1906
MSC (2010): Primary 05E05, 05A15, 65D15; Secondary 65Q05, 65H05
Published electronically: February 5, 2010
MathSciNet review: 2596023
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We construct a family of high order iteration functions for finding polynomial roots of a known multiplicity $ s$. This family is a generalization of a fundamental family of high order algorithms for simple roots that dates back to Schröder's 1870 paper. It starts with the well known variant of Newton's method $ \hat{B}_{2}(x) = x-s \cdot p(x)/p'(x)$ and the multiple root counterpart of Halley's method derived by Hansen and Patrick. Our approach demonstrates the relevance and power of algebraic combinatorial techniques in studying rational root-finding iteration functions.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05E05, 05A15, 65D15, 65Q05, 65H05

Retrieve articles in all journals with MSC (2010): 05E05, 05A15, 65D15, 65Q05, 65H05


Additional Information

Yi Jin
Affiliation: Quantitative Research, Interest Rate Derivatives, J.P. Morgan, 270 Park Avenue, New York, New York 10017
Email: yi.x.jin@jpmorgan.com

Bahman Kalantari
Affiliation: Department of Computer Science, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Road, Piscataway, New Jersey 08854
Email: kalantar@cs.rutgers.edu

DOI: http://dx.doi.org/10.1090/S0002-9939-10-10309-8
PII: S 0002-9939(10)10309-8
Keywords: Symmetric functions, generating functions, recurrence relation, multiple roots, root-finding, iteration functions
Received by editor(s): December 4, 2007
Published electronically: February 5, 2010
Additional Notes: The main idea of this article was developed in the first author’s Ph.D. dissertation [5], supervised by the second author.
Communicated by: Peter A. Clarkson
Article copyright: © Copyright 2010 American Mathematical Society