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

Complexity of Bézout’s theorem. I. Geometric aspects
HTML articles powered by AMS MathViewer

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

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

PDF | Request permission

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
W. Dale Brownawell, Bounds for the degrees in the Nullstellensatz, Ann. of Math. (2) 126 (1987), no. 3, 577–591. MR 916719, DOI 10.2307/1971361
John Canny, Generalised characteristic polynomials, J. Symbolic Comput. 9 (1990), no. 3, 241–250. MR 1056626, DOI 10.1016/S0747-7171(08)80012-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 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 10.1090/S0025-5718-1988-0929546-7

The approximation of one matrix by another of lower rank

1

Pathways to solutions, fixed points, and equilibria

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 10.1016/0304-3975(83)90002-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 10.1002/cpa.3160320302

Quantifier elimination in the first-order theory of algebraically closed fields

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

Random polynomials and the statistical fundamental theorem of algebra

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 10.1137/0724032
Alexander Morgan, Solving polynomial systems using continuation for engineering and scientific problems, Prentice Hall, Inc., Englewood Cliffs, NJ, 1987. MR 1049872

Polynomial continuation and its relationship to the symbolic reduction of polynomial systems

David Mumford, Algebraic geometry. I, Grundlehren der Mathematischen Wissenschaften, No. 221, Springer-Verlag, Berlin-New York, 1976. Complex projective varieties. 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 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 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 10.1007/BF01585691

Newton’s method

Some remarks on Bezout’s theorem and complexity theory

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, DOI 10.24033/asens.1486
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 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 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 10.1090/S0273-0979-1985-15391-1

Newton’s method estimates from data at one point

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 Mathematical Series, No. 32, Princeton University Press, Princeton, N.J., 1971. MR 0304972

Precise point estimates on continuous complexity theory

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 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 10.1090/S0025-5718-1988-0917824-7