Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Mobile Device Pairing
 Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(e) ISSN 0894-0347(p)

     

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

Author(s): Michael Shub; Steve Smale
Journal: J. Amer. Math. Soc. 6 (1993), 459-501.
MSC: Primary 65H20; Secondary 58F14
MathSciNet review: 1175980
Retrieve article in: PDF
This article is available free of charge

References | Similar articles | Additional information

References:

[1]
E. Allgower and K. Georg, Numerical continutation methods, Springer-Verlag, New York, 1990. MR 1059455 (92a:65165)

[2]
D. Brownawell, Bounds for the degrees in the Nullstellensatz, Ann. of Math. (2) 126 (1987), 577-591. MR 916719 (89b:12001)

[3]
J. Canny, Generalized characteristic polynomials, J. Symb. Comput. 9 (1990), 241-250. MR 1056626 (91i:13030)

[4]
J. Demmel, On condition numbers and the distance to the nearest ill-posed problem, Numer. Math. 51 (1987), 251-289. MR 895087 (88i:15014)

[5]
-, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), 449-480. MR 929546 (89g:65062)

[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]
G. Golub and C. Van Loan, Matrix computations, Johns Hopkins Univ. Press, Baltimore, MD, 1989. MR 1002570 (90d:65055)

[9]
D. Grigoriev, Computational complexity in polynomial algebra, Proc. Internat. Congr. Math. (Berkeley, 1986), vol. 1, 2, Amer. Math. Soc., Providence, RI, 1987, 1452-1460. MR 934349 (89e:68063)

[10]
J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), 239-278. MR 716823 (85a:68062)

[11]
M. Hirsch and S. Smale, On algorithms for solving $ f(x) = 0$, Comm. Pure Appl. Math. 32 (1979), 281-312. MR 517937 (80b:65061)

[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]
H. Keller, Global homotopic and Newton methods, Recent Advances in Numerical Analysis, Academic Press, New York, 1978, pp. 73-94. MR 519057 (80f:65059)

[14]
Eric Kostlan, Random polynomials and the statistical fundamental theorem of algebra, Preprint, Univ. of Hawaii (1987).

[15]
S. Lang, Real analysis, Addison-Wesley, Reading, Mass., 1983. MR 783635 (87b:00001)

[16]
T. Li, T. Sauer, and Yorke, Numerical solution of a class of deficient polynomial systems, SIAM J. Numer. Anal. 24 (1987), 435-451. MR 881375 (89e:90181)

[17]
A. Morgan, Solving polynomial systems using continuation for scientific and engineering problems, Prentice-Hall, Englewood Cliffs, NJ, 1987. MR 1049872 (91c:00014)

[18]
-, Polynomial continuation and its relationship to the symbolic reduction of polynomial systems, Preprint (1990).

[19]
D. Mumford, Algebraic geometry. I, Complex projective varieties, Springer-Verlag, New York, 1976. MR 0453732 (56:11992)

[20]
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. MR 882846 (88j:65112)

[21]
-, On the worst case arithmetic complexity of approximating zeros of systems of polynomials, SIAM J. Comp. 18 (1989), 350-370. MR 986672 (90j:68021)

[22]
J. Renegar and M. Shub, Unified complexity analysis for Newton LP Methods, Math. Programming (to appear). MR 1151762 (93a:90038)

[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]
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. MR 803197 (87m:68043)

[26]
-, Computational complexity: On the geometry of polynomials and a theory of cost. II, SIAM J. Comput. 15 (1986), 145-161. MR 822199 (87m:68044)

[27]
S. Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), 1-36. MR 590817 (83i:65044)

[28]
-, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), 87-121. MR 799791 (86m:65061)

[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]
-, Algorithms for solving equations, Proc. Internat. Congr. Math. (Berkeley 1986), vol. 1, Amer. Math. Soc., Providence, RI, 1987, 172-195. MR 934223 (89d:65060)

[31]
E. Stein and G. Weiss, Introduction to Fourier analysis on Euclidean spaces, Princeton Univ. Press, Princeton, NJ, 1971. MR 0304972 (46:4102)

[32]
Xinghua Wang and DanFu Han, Precise point estimates on continuous complexity theory, Preprint, Hangzhou Univ. (1986).

[33]
J. Wilkinson, Rounding errors in algebraic processes, Prentice Hall, Englewood Cliffs, NJ, 1963. MR 0161456 (28:4661)

[34]
A. Wright, Finding all solutions to a system of polynomial equations, Math. Comp. 44 (1985), 125-133. MR 771035 (86i:12001)

[35]
W. Zulehner, A simple homotopy method for determining all isolated solutions to polynomial systems, Math. Comp. 50 (1988), 167-177. MR 917824 (89b:65130)

Similar Articles:

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: 10.1090/S0894-0347-1993-1175980-4
PII: S0894-0347-1993-1175980-4
Copyright of article: Copyright 1993, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia