Complexity of Bézout’s theorem. I. Geometric aspects

Authors:
Michael Shub and Steve Smale

Journal:
J. Amer. Math. Soc. **6** (1993), 459-501

MSC:
Primary 65H20; Secondary 58F14

DOI:
https://doi.org/10.1090/S0894-0347-1993-1175980-4

MathSciNet review:
1175980

Full-text PDF Free Access

References | Similar Articles | Additional Information

- Eugene L. Allgower and Kurt Georg,
*Numerical continuation methods*, Springer Series in Computational Mathematics, vol. 13, Springer-Verlag, Berlin, 1990. An introduction. MR**1059455** - W. Dale Brownawell,
*Bounds for the degrees in the Nullstellensatz*, Ann. of Math. (2)**126**(1987), no. 3, 577–591. MR**916719**, DOI https://doi.org/10.2307/1971361 - John Canny,
*Generalised characteristic polynomials*, J. Symbolic Comput.**9**(1990), no. 3, 241–250. MR**1056626**, DOI https://doi.org/10.1016/S0747-7171%2808%2980012-0 - James Weldon Demmel,
*On condition numbers and the distance to the nearest ill-posed problem*, Numer. Math.**51**(1987), no. 3, 251–289. MR**895087**, DOI https://doi.org/10.1007/BF01400115 - James W. Demmel,
*The probability that a numerical analysis problem is difficult*, Math. Comp.**50**(1988), no. 182, 449–480. MR**929546**, DOI https://doi.org/10.1090/S0025-5718-1988-0929546-7
C. Eckart and G.Young, - Gene H. Golub and Charles F. Van Loan,
*Matrix computations*, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR**1002570** - D. Yu. Grigor′ev,
*Computational complexity in polynomial algebra*, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 1452–1460. MR**934349** - Joos Heintz,
*Definability and fast quantifier elimination in algebraically closed fields*, Theoret. Comput. Sci.**24**(1983), no. 3, 239–277. MR**716823**, DOI https://doi.org/10.1016/0304-3975%2883%2990002-6 - Morris W. Hirsch and Stephen Smale,
*On algorithms for solving $f(x)=0$*, Comm. Pure Appl. Math.**32**(1979), no. 3, 281–313. MR**517937**, DOI https://doi.org/10.1002/cpa.3160320302
D. Ierardi, - Herbert B. Keller,
*Global homotopies and Newton methods*, Recent advances in numerical analysis (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1978) Publ. Math. Res. Center Univ. Wisconsin, vol. 41, Academic Press, New York-London, 1978, pp. 73–94. MR**519057**
Eric Kostlan, - Serge Lang,
*Real analysis*, 2nd ed., Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. MR**783635** - Tien-Yien Li, Tim Sauer, and James A. Yorke,
*Numerical solution of a class of deficient polynomial systems*, SIAM J. Numer. Anal.**24**(1987), no. 2, 435–451. MR**881375**, DOI https://doi.org/10.1137/0724032 - Alexander Morgan,
*Solving polynomial systems using continuation for engineering and scientific problems*, Prentice Hall, Inc., Englewood Cliffs, NJ, 1987. MR**1049872**
---, - David Mumford,
*Algebraic geometry. I*, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties; Grundlehren der Mathematischen Wissenschaften, No. 221. MR**0453732** - J. Renegar,
*On the efficiency of Newton’s method in approximating all zeros of a system of complex polynomials*, Math. Oper. Res.**12**(1987), no. 1, 121–148. MR**882846**, DOI https://doi.org/10.1287/moor.12.1.121 - James Renegar,
*On the worst-case arithmetic complexity of approximating zeros of systems of polynomials*, SIAM J. Comput.**18**(1989), no. 2, 350–370. MR**986672**, DOI https://doi.org/10.1137/0218024 - James Renegar and Michael Shub,
*Unified complexity analysis for Newton LP methods*, Math. Programming**53**(1992), no. 1, Ser. A, 1–16. MR**1151762**, DOI https://doi.org/10.1007/BF01585691
H. Royden, - Mike Shub and Steven Smale,
*Computational complexity. On the geometry of polynomials and a theory of cost. I*, Ann. Sci. École Norm. Sup. (4)**18**(1985), no. 1, 107–142. MR**803197** - M. Shub and S. Smale,
*Computational complexity: on the geometry of polynomials and a theory of cost. II*, SIAM J. Comput.**15**(1986), no. 1, 145–161. MR**822199**, DOI https://doi.org/10.1137/0215011 - Steve Smale,
*The fundamental theorem of algebra and complexity theory*, Bull. Amer. Math. Soc. (N.S.)**4**(1981), no. 1, 1–36. MR**590817**, DOI https://doi.org/10.1090/S0273-0979-1981-14858-8 - Steve Smale,
*On the efficiency of algorithms of analysis*, Bull. Amer. Math. Soc. (N.S.)**13**(1985), no. 2, 87–121. MR**799791**, DOI https://doi.org/10.1090/S0273-0979-1985-15391-1
---, - Steve Smale,
*Algorithms for solving equations*, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 172–195. MR**934223** - Elias M. Stein and Guido Weiss,
*Introduction to Fourier analysis on Euclidean spaces*, Princeton University Press, Princeton, N.J., 1971. Princeton Mathematical Series, No. 32. MR**0304972**
Xinghua Wang and DanFu Han, - J. H. Wilkinson,
*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456** - Alden H. Wright,
*Finding all solutions to a system of polynomial equations*, Math. Comp.**44**(1985), no. 169, 125–133. MR**771035**, DOI https://doi.org/10.1090/S0025-5718-1985-0771035-4 - Walter Zulehner,
*A simple homotopy method for determining all isolated solutions to polynomial systems*, Math. Comp.**50**(1988), no. 181, 167–177. MR**917824**, DOI https://doi.org/10.1090/S0025-5718-1988-0917824-7

*The approximation of one matrix by another of lower rank*, Psychometrika

**1**(1936), 211-218. C. Garcia and W. Zangwill,

*Pathways to solutions, fixed points, and equilibria*, Prentice Hall, Englewood Cliffs, NJ, 1981.

*Quantifier elimination in the first-order theory of algebraically closed fields*, Proc. 21st Annual ACM Sympos. on the Theory of Computing and Ph.D. Thesis, Cornell University (Computer Science).

*Random polynomials and the statistical fundamental theorem of algebra*, Preprint, Univ. of Hawaii (1987).

*Polynomial continuation and its relationship to the symbolic reduction of polynomial systems*, Preprint (1990).

*Newton’s method*, Preprint (1986). M. Shub,

*Some remarks on Bezout’s theorem and complexity theory*, From Topology to Computation, Proc. of the Smalefest (M. Hirsch, J. Marsden, and M. Shub, eds.) (to appear).

*Newton’s method estimates from data at one point*, The Merging of Disciplines: New Directions in Pure, Applied and Computation Math (Ewing, R., Gross, K. and Martin, C. eds.), Springer-Verlag, New York, 1986.

*Precise point estimates on continuous complexity theory*, Preprint, Hangzhou Univ. (1986).

Retrieve articles in *Journal of the American Mathematical Society*
with MSC:
65H20,
58F14

Retrieve articles in all journals with MSC: 65H20, 58F14

Additional Information

Article copyright:
© Copyright 1993
American Mathematical Society