Multihomogeneous Newton methods

Authors:
Jean-Pierre Dedieu and Mike Shub

Journal:
Math. Comp. **69** (2000), 1071-1098

MSC (1991):
Primary 65H10, 15A99

Published electronically:
March 10, 1999

MathSciNet review:
1752092

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study multihomogeneous analytic functions and a multihomogeneous Newton's method for finding their zeros. We give a convergence result for this iteration and we study two examples: the evaluation map and the generalized eigenvalue problem.

**[1]**Eugene L. Allgower and Kurt Georg,*Numerical continuation methods*, Springer Series in Computational Mathematics, vol. 13, Springer-Verlag, Berlin, 1990. An introduction. MR**1059455****[2]**Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale,*Complexity and real computation*, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR**1479636****[3]**Jean-Pierre Dedieu,*Condition operators, condition numbers, and condition number theorem for the generalized eigenvalue problem*, Linear Algebra Appl.**263**(1997), 1–24. MR**1453962**, 10.1016/S0024-3795(96)00366-7**[4]**J. P. Dedieu, Condition Number Analysis for Sparse Polynomial Systems, in : Foundations of Computational Mathematics, F. Cucker, M. Shub Eds. Springer (1997).**[5]**T. Y. Li, Numerical Solution of Multivariate Polynomial Systems by Homotopy Continuation Methods, Acta Numerica 6, 399-436 (1997). CMP**98:06****[6]**Gregorio Malajovich,*On generalized Newton algorithms: quadratic convergence, path-following and error analysis*, Theoret. Comput. Sci.**133**(1994), no. 1, 65–84. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR**1294426**, 10.1016/0304-3975(94)00065-4**[7]**H. Royden. Newton's Method. Preprint.**[8]**Michael Shub,*Some remarks on Bezout’s theorem and complexity theory*, From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990) Springer, New York, 1993, pp. 443–455. MR**1246139****[9]**Michael Shub and Steve Smale,*Complexity of Bézout’s theorem. I. Geometric aspects*, J. Amer. Math. Soc.**6**(1993), no. 2, 459–501. MR**1175980**, 10.1090/S0894-0347-1993-1175980-4**[10]**M. Shub and S. Smale,*Complexity of Bezout’s theorem. II. Volumes and probabilities*, Computational algebraic geometry (Nice, 1992) Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 267–285. MR**1230872**, 10.1007/978-1-4612-2752-6_19**[11]**Michael Shub and Steve Smale,*Complexity of Bezout’s theorem. III. Condition number and packing*, J. Complexity**9**(1993), no. 1, 4–14. Festschrift for Joseph F. Traub, Part I. MR**1213484**, 10.1006/jcom.1993.1002**[12]**Michael Shub and Steve Smale,*Complexity of Bezout’s theorem. IV. Probability of success; extensions*, SIAM J. Numer. Anal.**33**(1996), no. 1, 128–148. MR**1377247**, 10.1137/0733008**[13]**M. Shub and S. Smale,*Complexity of Bezout’s theorem. V. Polynomial time*, Theoret. Comput. Sci.**133**(1994), no. 1, 141–164. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR**1294430**, 10.1016/0304-3975(94)90122-8**[14]**Steve Smale,*Newton’s method estimates from data at one point*, The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985) Springer, New York, 1986, pp. 185–196. MR**870648****[15]**G. W. Stewart and Ji Guang Sun,*Matrix perturbation theory*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR**1061154****[16]**X. Wang, Some results relevant to Smale's reports, in : Proceedings of the Smalefest, M. V. Hirsch, J. E. Marsden, M. Shub Eds., Springer, 456-465 (1993). CMP**94:03**

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
65H10,
15A99

Retrieve articles in all journals with MSC (1991): 65H10, 15A99

Additional Information

**Jean-Pierre Dedieu**

Affiliation:
Laboratoire Approximation et Optimisation, Université Paul Sabatier, 31062 Toulouse Cedex 04, France

Email:
dedieu@cict.fr

**Mike Shub**

Affiliation:
IBM T.J. Watson Research Center, Yorktown Heights, NY 10598-0218, USA

Email:
mshub@us.ibm.com

DOI:
https://doi.org/10.1090/S0025-5718-99-01114-X

Received by editor(s):
October 16, 1997

Received by editor(s) in revised form:
July 22, 1998

Published electronically:
March 10, 1999

Additional Notes:
This paper was completed when the first author was visiting at the IBM T.J. Watson Research Center in August 1997.

The second author was partially supported by an NSF grant

Article copyright:
© Copyright 2000
American Mathematical Society