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 Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We construct a family of high order iteration functions for finding polynomial roots of a known multiplicity . 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 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.

**1.**Xavier Buff and Christian Henriksen,*On König’s root-finding algorithms*, Nonlinearity**16**(2003), no. 3, 989–1015. MR**1975793**, 10.1088/0951-7715/16/3/312**2.**Charles M. Fiduccia,*An efficient formula for linear recurrences*, SIAM J. Comput.**14**(1985), no. 1, 106–112. MR**774930**, 10.1137/0214007**3.**Eldon Hansen and Merrell Patrick,*A family of root finding methods*, Numer. Math.**27**(1976/77), no. 3, 257–269. MR**0433858****4.**Yi Jin and Bahman Kalantari,*Symmetric functions and root-finding algorithms*, Adv. in Appl. Math.**34**(2005), no. 1, 156–174. MR**2102280**, 10.1016/j.aam.2004.05.005**5.**Y. Jin, Combinatorics of polynomial root-finding algorithms, Ph.D. dissertation, Dept. of Computer Science, Rutgers University, New Brunswick, NJ, October 2005.**6.**Yi Jin,*On efficient computation and asymptotic sharpness of Kalantari’s bounds for zeros of polynomials*, Math. Comp.**75**(2006), no. 256, 1905–1912 (electronic). MR**2240641**, 10.1090/S0025-5718-06-01868-0**7.**Bahman Kalantari, Iraj Kalantari, and Rahim Zaare-Nahandi,*A basic family of iteration functions for polynomial root finding and its characterizations*, J. Comput. Appl. Math.**80**(1997), no. 2, 209–226. MR**1455244**, 10.1016/S0377-0427(97)00014-9**8.**Bahman Kalantari,*Generalization of Taylor’s theorem and Newton’s method via a new family of determinantal interpolation formulas and its applications*, J. Comput. Appl. Math.**126**(2000), no. 1-2, 287–318. MR**1806762**, 10.1016/S0377-0427(99)00360-X**9.**B. Kalantari and Y. Jin,*On extraneous fixed-points of the basic family of iteration functions*, BIT**43**(2003), no. 2, 453–458. MR**2010487**, 10.1023/A:1026095904985**10.**Bahman Kalantari,*On homogeneous linear recurrence relations and approximation of zeros of complex polynomials*, Unusual applications of number theory, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 64, Amer. Math. Soc., Providence, RI, 2004, pp. 125–143. MR**2063208****11.**Bahman Kalantari,*An infinite family of bounds on zeros of analytic functions and relationship to Smale’s bound*, Math. Comp.**74**(2005), no. 250, 841–852 (electronic). MR**2114651**, 10.1090/S0025-5718-04-01686-2**12.**H. T. Kung,*A new upper bound on the complexity of derivative evaluation*, Information Processing Lett.**2**(1973), 146–147. MR**0347135****13.**I. G. Macdonald,*Symmetric functions and Hall polynomials*, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR**1354144****14.**E. Schröder,*Ueber unendlich viele Algorithmen zur Auflösung der Gleichungen*, Math. Ann.**2**(1870), no. 2, 317–365 (German). MR**1509664**, 10.1007/BF01444024

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:
https://doi.org/10.1090/S0002-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