Multihomogeneous Newton methods
Authors:
JeanPierre Dedieu and Mike Shub
Journal:
Math. Comp. 69 (2000), 10711098
MSC (1991):
Primary 65H10, 15A99
Published electronically:
March 10, 1999
MathSciNet review:
1752092
Fulltext 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, SpringerVerlag, Berlin, 1990. An
introduction. MR
1059455 (92a:65165)
 [2]
Lenore
Blum, Felipe
Cucker, Michael
Shub, and Steve
Smale, Complexity and real computation, SpringerVerlag, New
York, 1998. With a foreword by Richard M. Karp. MR 1479636
(99a:68070)
 [3]
JeanPierre
Dedieu, Condition operators, condition numbers, and condition
number theorem for the generalized eigenvalue problem, Linear Algebra
Appl. 263 (1997), 1–24. MR 1453962
(98e:15008), http://dx.doi.org/10.1016/S00243795(96)003667
 [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, 399436 (1997). CMP 98:06
 [6]
Gregorio
Malajovich, On generalized Newton algorithms: quadratic
convergence, pathfollowing 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
(95g:65073), http://dx.doi.org/10.1016/03043975(94)000654
 [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
(95a:14002)
 [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
(93k:65045), http://dx.doi.org/10.1090/S08940347199311759804
 [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
(94m:68086)
 [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
(94g:65152), http://dx.doi.org/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
(97k:65310), http://dx.doi.org/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
(96d:65091), http://dx.doi.org/10.1016/03043975(94)901228
 [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
(88e:65076)
 [15]
G.
W. Stewart and Ji
Guang Sun, Matrix perturbation theory, Computer Science and
Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
(92a:65017)
 [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, 456465 (1993). CMP 94:03
 [1]
 E. Allgower, K. Georg, Numerical Continuation Methods, Springer Verlag (1990). MR 92a:65165
 [2]
 L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer Verlag (1997). MR 99a:68070
 [3]
 J. P. Dedieu, Condition Operators, Condition Numbers, and Condition Number Theorem for the Generalized Eigenvalue Problem, Linear Algebra and its Applications 263, 124 (1997). MR 98e:15008
 [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, 399436 (1997). CMP 98:06
 [6]
 G. Malajovich, On Generalized Newton Algorithms, Theoretical Computer Science 133, 6584 (1994). MR 95g:65073
 [7]
 H. Royden. Newton's Method. Preprint.
 [8]
 M. Shub, Some Remarks on Bézout's Theorem and Complexity, in : Proceedings of the Smalefest, M. V. Hirsch, J. E. Marsden, M. Shub Eds., Springer, 443455 (1993). MR 95a:14002
 [9]
 M. Shub, S. Smale, Complexity of Bézout's Theorem I : Geometric Aspects, J. Am. Math. Soc. 6, 459501 (1993). MR 93k:65045
 [10]
 M. Shub, S. Smale, Complexity of Bézout's Theorem II : Volumes and Probabilities, in : F. Eyssette, A. Galligo Eds. Computational Algebraic Geometry, Progress in Mathematics. Vol. 109, Birkhäuser, 267285 (1993). MR 94m:68086
 [11]
 M. Shub, S. Smale, Complexity of Bézout's Theorem III : Condition Number and Packing, J. of Complexity, 9, 414 (1993). MR 94g:65152
 [12]
 M. Shub, S. Smale, Complexity of Bézout's Theorem IV : Probability of Success, Extensions, SIAM J. Numer. Anal., 33, 128148 (1996). MR 97k:65310
 [13]
 M. Shub, S. Smale, Complexity of Bézout's Theorem V : Polynomial Time, Theoretical Computer Science, 133, 141164 (1994). MR 96d:65091
 [14]
 S. Smale, Newton's Method Estimates from Data at One Point, in : The Merging of Disciplines : New Directions in Pure, Applied and Computational Mathematics, R. Ewing, K. Gross, C. Martin Eds., Springer, 185196 (1986). MR 88e:65076
 [15]
 G. Stewart, J. Sun, Matrix Perturbation Theory, Academic Press, 1990. MR 92a:65017
 [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, 456465 (1993). CMP 94:03
Similar Articles
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
JeanPierre 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 105980218, USA
Email:
mshub@us.ibm.com
DOI:
http://dx.doi.org/10.1090/S002557189901114X
PII:
S 00255718(99)01114X
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
