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

HTML articles powered by AMS MathViewer

- by Michael Shub and Steve Smale PDF
- J. Amer. Math. Soc.
**6**(1993), 459-501 Request permission

## References

- E. Allgower and K. Georg,

*Numerical continutation methods*, Springer-Verlag, New York, 1990. D. Brownawell,

*Bounds for the degrees in the Nullstellensatz*, Ann. of Math. (2)

**126**(1987), 577-591. J. Canny,

*Generalized characteristic polynomials*, J. Symb. Comput.

**9**(1990), 241-250. J. Demmel,

*On condition numbers and the distance to the nearest ill-posed problem*, Numer. Math.

**51**(1987), 251-289. —,

*The probability that a numerical analysis problem is difficult*, Math. Comp.

**50**(1988), 449-480. C. Eckart and G.Young,

*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. G. Golub and C. Van Loan,

*Matrix computations*, Johns Hopkins Univ. Press, Baltimore, MD, 1989. D. Grigoriev,

*Computational complexity in polynomial algebra*, Proc. Internat. Congr. Math. (Berkeley, 1986), vol. 1, 2, Amer. Math. Soc., Providence, RI, 1987, 1452-1460. J. Heintz,

*Definability and fast quantifier elimination in algebraically closed fields*, Theoret. Comput. Sci.

**24**(1983), 239-278. M. Hirsch and S. Smale,

*On algorithms for solving*$f(x) = 0$, Comm. Pure Appl. Math.

**32**(1979), 281-312. 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). H. Keller,

*Global homotopic and Newton methods*, Recent Advances in Numerical Analysis, Academic Press, New York, 1978, pp. 73-94. Eric Kostlan,

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

*Real analysis*, Addison-Wesley, Reading, Mass., 1983. T. Li, T. Sauer, and Yorke,

*Numerical solution of a class of deficient polynomial systems*, SIAM J. Numer. Anal.

**24**(1987), 435-451. A. Morgan,

*Solving polynomial systems using continuation for scientific and engineering problems*, Prentice-Hall, Englewood Cliffs, NJ, 1987. —,

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

*Algebraic geometry*. I,

*Complex projective varieties*, Springer-Verlag, New York, 1976. J. Renegar,

*On the efficiency of Newton’s Method in approximating all zeros of systems of complex polynomials*, Math. Oper. Res.

**12**(1987), 121-148. —,

*On the worst case arithmetic complexity of approximating zeros of systems of polynomials*, SIAM J. Comp.

**18**(1989), 350-370. J. Renegar and M. Shub,

*Unified complexity analysis for Newton LP Methods*, Math. Programming (to appear). H. Royden,

*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). M. Shub and S. Smale,

*Computational complexity: On the geometry of polynomials and a theory of cost*. I, Ann. Sci. École Norm. Sup. (4)

**18**(1985), 107-142. —,

*Computational complexity: On the geometry of polynomials and a theory of cost*. II, SIAM J. Comput.

**15**(1986), 145-161. S. Smale,

*The fundamental theorem of algebra and complexity theory*, Bull. Amer. Math. Soc. (N.S.)

**4**(1981), 1-36. —,

*On the efficiency of algorithms of analysis*, Bull. Amer. Math. Soc. (N.S.)

**13**(1985), 87-121. —,

*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. —,

*Algorithms for solving equations*, Proc. Internat. Congr. Math. (Berkeley 1986), vol. 1, Amer. Math. Soc., Providence, RI, 1987, 172-195. E. Stein and G. Weiss,

*Introduction to Fourier analysis on Euclidean spaces*, Princeton Univ. Press, Princeton, NJ, 1971. Xinghua Wang and DanFu Han,

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

*Rounding errors in algebraic processes*, Prentice Hall, Englewood Cliffs, NJ, 1963. A. Wright,

*Finding all solutions to a system of polynomial equations*, Math. Comp.

**44**(1985), 125-133. W. Zulehner,

*A simple homotopy method for determining all isolated solutions to polynomial systems*, Math. Comp.

**50**(1988), 167-177.

## Additional Information

- © Copyright 1993 American Mathematical Society
- 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