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

References | Similar Articles | Additional Information

**[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]**W. Dale Brownawell,*Bounds for the degrees in the Nullstellensatz*, Ann. of Math. (2)**126**(1987), no. 3, 577–591. MR**916719**, https://doi.org/10.2307/1971361**[3]**John Canny,*Generalised characteristic polynomials*, J. Symbolic Comput.**9**(1990), no. 3, 241–250. MR**1056626**, https://doi.org/10.1016/S0747-7171(08)80012-0**[4]**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**, https://doi.org/10.1007/BF01400115**[5]**James W. Demmel,*The probability that a numerical analysis problem is difficult*, Math. Comp.**50**(1988), no. 182, 449–480. MR**929546**, https://doi.org/10.1090/S0025-5718-1988-0929546-7**[6]**C. Eckart and G.Young,*The approximation of one matrix by another of lower rank*, Psychometrika**1**(1936), 211-218.**[7]**C. Garcia and W. Zangwill,*Pathways to solutions, fixed points, and equilibria*, Prentice Hall, Englewood Cliffs, NJ, 1981.**[8]**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****[9]**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****[10]**Joos Heintz,*Definability and fast quantifier elimination in algebraically closed fields*, Theoret. Comput. Sci.**24**(1983), no. 3, 239–277. MR**716823**, https://doi.org/10.1016/0304-3975(83)90002-6**[11]**Morris W. Hirsch and Stephen Smale,*On algorithms for solving 𝑓(𝑥)=0*, Comm. Pure Appl. Math.**32**(1979), no. 3, 281–313. MR**517937**, https://doi.org/10.1002/cpa.3160320302**[12]**D. Ierardi,*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).**[13]**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****[14]**Eric Kostlan,*Random polynomials and the statistical fundamental theorem of algebra*, Preprint, Univ. of Hawaii (1987).**[15]**Serge Lang,*Real analysis*, 2nd ed., Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. MR**783635****[16]**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**, https://doi.org/10.1137/0724032**[17]**Alexander Morgan,*Solving polynomial systems using continuation for engineering and scientific problems*, Prentice Hall, Inc., Englewood Cliffs, NJ, 1987. MR**1049872****[18]**-,*Polynomial continuation and its relationship to the symbolic reduction of polynomial systems*, Preprint (1990).**[19]**David Mumford,*Algebraic geometry. I*, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties; Grundlehren der Mathematischen Wissenschaften, No. 221. MR**0453732****[20]**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**, https://doi.org/10.1287/moor.12.1.121**[21]**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**, https://doi.org/10.1137/0218024**[22]**James Renegar and Michael Shub,*Unified complexity analysis for Newton LP methods*, Math. Programming**53**(1992), no. 1, Ser. A, 1–16. MR**1151762**, https://doi.org/10.1007/BF01585691**[23]**H. Royden,*Newton's method*, Preprint (1986).**[24]**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).**[25]**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****[26]**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**, https://doi.org/10.1137/0215011**[27]**Steve Smale,*The fundamental theorem of algebra and complexity theory*, Bull. Amer. Math. Soc. (N.S.)**4**(1981), no. 1, 1–36. MR**590817**, https://doi.org/10.1090/S0273-0979-1981-14858-8**[28]**Steve Smale,*On the efficiency of algorithms of analysis*, Bull. Amer. Math. Soc. (N.S.)**13**(1985), no. 2, 87–121. MR**799791**, https://doi.org/10.1090/S0273-0979-1985-15391-1**[29]**-,*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.**[30]**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****[31]**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****[32]**Xinghua Wang and DanFu Han,*Precise point estimates on continuous complexity theory*, Preprint, Hangzhou Univ. (1986).**[33]**J. H. Wilkinson,*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456****[34]**Alden H. Wright,*Finding all solutions to a system of polynomial equations*, Math. Comp.**44**(1985), no. 169, 125–133. MR**771035**, https://doi.org/10.1090/S0025-5718-1985-0771035-4**[35]**Walter Zulehner,*A simple homotopy method for determining all isolated solutions to polynomial systems*, Math. Comp.**50**(1988), no. 181, 167–177. MR**917824**, https://doi.org/10.1090/S0025-5718-1988-0917824-7

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

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

Additional Information

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

Article copyright:
© Copyright 1993
American Mathematical Society