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), 18971906
MSC (2010):
Primary 05E05, 05A15, 65D15; Secondary 65Q05, 65H05
Published electronically:
February 5, 2010
MathSciNet review:
2596023
Fulltext 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 . 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 rootfinding iteration functions.
 1.
Xavier
Buff and Christian
Henriksen, On König’s rootfinding algorithms,
Nonlinearity 16 (2003), no. 3, 989–1015. MR 1975793
(2004c:37086), 10.1088/09517715/16/3/312
 2.
Charles
M. Fiduccia, An efficient formula for linear recurrences, SIAM
J. Comput. 14 (1985), no. 1, 106–112. MR 774930
(86h:39001), 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
(55 #6829)
 4.
Yi
Jin and Bahman
Kalantari, Symmetric functions and rootfinding algorithms,
Adv. in Appl. Math. 34 (2005), no. 1, 156–174.
MR
2102280 (2006a:05167), 10.1016/j.aam.2004.05.005
 5.
Y. Jin, Combinatorics of polynomial rootfinding 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
(2007e:65046), 10.1090/S0025571806018680
 7.
Bahman
Kalantari, Iraj
Kalantari, and Rahim
ZaareNahandi, 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
(98d:65066), 10.1016/S03770427(97)000149
 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. 12, 287–318. MR 1806762
(2001m:41035), 10.1016/S03770427(99)00360X
 9.
B.
Kalantari and Y.
Jin, On extraneous fixedpoints of the basic family of iteration
functions, BIT 43 (2003), no. 2, 453–458.
MR
2010487 (2004g:65066), 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
(2005d:12001)
 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
(2005k:65093), 10.1090/S0025571804016862
 12.
H.
T. Kung, A new upper bound on the complexity of derivative
evaluation, Information Processing Lett. 2 (1973),
146–147. MR 0347135
(49 #11855)
 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 (96h:05207)
 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
 1.
 X. Buff and C. Henriksen, On König's rootfinding algorithms, Nonlinearity, 16 (2003) 9891015. MR 1975793 (2004c:37086)
 2.
 C.M. Fiduccia, An efficient formula for linear recurrences, SIAM J. Comput., 14 (1985) 106112. MR 774930 (86h:39001)
 3.
 E. Hansen and M. Patrick, A family of root finding methods, Numer. Math., 27 (1976/77) 257269. MR 0433858 (55:6829)
 4.
 Y. Jin and B. Kalantari, Symmetric functions and rootfinding algorithms, Adv. Appl. Math., 34 (2005) 156174. MR 2102280 (2006a:05167)
 5.
 Y. Jin, Combinatorics of polynomial rootfinding algorithms, Ph.D. dissertation, Dept. of Computer Science, Rutgers University, New Brunswick, NJ, October 2005.
 6.
 Y. Jin, On efficient computation and asymptotic sharpness of Kalantari's bounds for zeros of polynomials, Math. Comp., 75 (2006) 19051912. MR 2240641 (2007e:65046)
 7.
 B. Kalantari, I. Kalantari, and R. ZaareNahandi, A basic family of iteration functions for polynomial root finding and its characterizations, J. Comput. Appl. Math., 80 (1997) 209226. MR 1455244 (98d:65066)
 8.
 B. 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) 287318. MR 1806762 (2001m:41035)
 9.
 B. Kalantari and Y. Jin, On extraneous fixedpoints of the basic family of iteration functions, BIT, 43 (2003) 453458. MR 2010487 (2004g:65066)
 10.
 B. Kalantari, On homogeneous linear recurrence relations and approximation of zeros of complex polynomials, Unusual applications of number theory, 125143, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 64, Amer. Math. Soc., Providence, RI, 2004. MR 2063208 (2005d:12001)
 11.
 B. Kalantari, An infinite family of bounds on zeros of analytic functions and relationship to Smale's bound, Math. Comp., 74 (2005) 841852. MR 2114651 (2005k:65093)
 12.
 H.T. Kung, A new upper bound on the complexity of derivative evaluation, Inform. Process. Lett., 2 (1973) 146147. MR 0347135 (49:11855)
 13.
 I.G. MacDonald, Symmetric Functions and Hall Polynomials, 2nd Edition, The Clarendon Press, Oxford University Press, Oxford, 1995. MR 1354144 (96h:05207)
 14.
 E. Schröder, Ueber unendlich viele Algorithmen zur Auflösung der Gleichungen, Math. Ann., 2 (1870) 317365. (English translation, ``On infinitely many algorithms for solving equations'', by G.W. Stewart, TR92121, Institute for Advanced Computer Studies, University of Maryland, College Park, MD, 1992.) MR 1509664
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 CenterBusch Campus, 110 Frelinghuysen Road, Piscataway, New Jersey 08854
Email:
kalantar@cs.rutgers.edu
DOI:
http://dx.doi.org/10.1090/S0002993910103098
Keywords:
Symmetric functions,
generating functions,
recurrence relation,
multiple roots,
rootfinding,
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
