Multihomogeneous Newton methods

Dedieu, Jean-Pierre; Shub, Mike

doi:10.1090/S0025-5718-99-01114-X

Multihomogeneous Newton methods
HTML articles powered by AMS MathViewer

by Jean-Pierre Dedieu and Mike Shub PDF

Math. Comp. 69 (2000), 1071-1098 Request permission

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.

References

Eugene L. Allgower and Kurt Georg, Numerical continuation methods, Springer Series in Computational Mathematics, vol. 13, Springer-Verlag, Berlin, 1990. An introduction. MR 1059455, DOI 10.1007/978-3-642-61257-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, DOI 10.1007/978-1-4612-0701-6
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, DOI 10.1016/S0024-3795(96)00366-7
J. P. Dedieu, Condition Number Analysis for Sparse Polynomial Systems, in : Foundations of Computational Mathematics, F. Cucker, M. Shub Eds. Springer (1997).
T. Y. Li, Numerical Solution of Multivariate Polynomial Systems by Homotopy Continuation Methods, Acta Numerica 6, 399-436 (1997).
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, DOI 10.1016/0304-3975(94)00065-4
H. Royden. Newton’s Method. Preprint.
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
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, DOI 10.1090/S0894-0347-1993-1175980-4
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, DOI 10.1007/978-1-4612-2752-6_{1}9
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, DOI 10.1006/jcom.1993.1002
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, DOI 10.1137/0733008
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, DOI 10.1016/0304-3975(94)90122-8
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
G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
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).