Grid Methods in Computational Real Algebraic (and Semialgebraic) Geometry

Abstract

In recent years, a family of numerical algorithms to solve problems in real algebraic and semialgebraic geometry has been slowly growing. Unlike their counterparts in symbolic computation they are numerically stable. But their complexity analysis, based on the condition of the data, is radically different from the usual complexity analysis in symbolic computation as these numerical algorithms may run forever on a thin set of ill-posed inputs.

Keywords

Numerical algorithms / Complexity / Condition / Semialgebraic geometry

References

[1] Allgower E. L., Georg K.. Numerical Continuation Methods, 1990, Berlin: Springer-Verlag

[2] Amelunxen D., Lotz M.. Average-case complexity without the black swans. J. Complexity, 2017, 41: 82-101

[3] Basu S.. Algorithmic semi-algebraic geometry and topology—recent progress and open problems, Surveys on discrete and computational geometry. Contemp. Math., 2008 139-212

[4] Basu S., Pollack R., Roy M.-F.. On the combinatorial and algebraic complexity of quantifier elimination. 35th Annual IEEE Symp. on Foundations of Computer Science, 1994 632-641

[5] Basu S., Pollack R., Roy M.-F.. Algorithms in Real Algebraic Geometry, 2006, Berlin: Springer-Verlag

[6] Benedetti R., Risler J.-J.. Real algebraic and semi-algebraic sets, 1990, Paris: Hermann

[7] Björner A.. Graham R., Grotschel M., Lovasz L.. Topological methods. Handbook of Combinatorics, 1995, Amsterdam: North-Holland 1819-1872

[8] Blum L., Cucker F., Shub M., Smale S.. Complexity and Real Computation, 1998, New York: Springer-Verlag

[9] Blum L., Shub M., Smale S.. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the Amer. Math. Soc., 1989, 21: 1-46

[10] Bochnak J., Coste M., Roy M.-F.. Real Algebraic Geometry, Ergebnisse der Mathematik und Ihrer Grenzgebiete (3), 1998, Berlin: Springer-Verlag

[11] Bürgisser P., Cucker F.. Counting complexity classes for numeric computations II: Algebraic and semialgebraic sets. J. Complexity, 2006, 22: 147-191

[12] Bürgisser P., Cucker F.. Exotic quantifiers, complexity classes, and complete problems. Found. Comput. Math., 2009, 9: 135-170

[13] Bürgisser P., Cucker F.. Condition, Grundlehren der Mathematischen Wissenschaften, 2013, Berlin: Springer-Verlag

[14] Bürgisser P., Cucker F., Lairez P.. Computing the homology of basic semialgebraic sets in weakly exponential time, 2017

[15] Carlson J., Jaffe A., Wiles A. The Millenium Prize Problems, 2006, Cambridge, MA, American Mathematical Society, Providence, RI: Clay Mathematics Institute

[16] Collins G. E.. Quantifier elimination for real closed fields by cylindrical algebraic deccomposition. Lect. Notes in Comp. Sci., 1975, Berlin: Springer-Verlag 134-183

[17] Cucker F.. Approximate zeros and condition numbers. J. Complexity, 1999, 15: 214-226

[18] Cucker F.. A theory of complexity, condition and roundoff. Forum of Mathematics, Sigma, 2015 e4

[19] Cucker F., Krick T., Malajovich G., Wschebor M.. A numerical algorithm for zero counting, I: Complexity and accuracy. J. Complexity, 2008, 24: 582-605

[20] Cucker F., Krick T., Malajovich G., Wschebor M.. A numerical algorithm for zero counting, II: Distance to ill-posedness and smoothed analysis. J. Fixed Point Theory Appl., 2009, 6: 285-294

[21] Cucker F., Krick T., Malajovich G., Wschebor M.. A numerical algorithm for zero counting, III: Randomization and condition. Adv. Applied Math., 2012, 48: 215-248

[22] Cucker F., Krick T., Shub M.. Computing the homology of real projective sets. Found. Comp. Math., 2016

[23] Cucker F., Smale S.. Complexity estimates depending on condition and round-off error. Journal of the ACM, 1999, 46: 113-184

[24] Demmel J.. On condition numbers and the distance to the nearest ill-posed problem. Numer. Math., 1987, 51: 251-289

[25] Demmel J. W.. Applied Numerical Linear Algebra, 1997, Philadelphia: SIAM

[26] Eckart C., Young G.. The approximation of one matrix by another of lower rank. Psychometrika, 1936, 1: 211-218

[27] Grigoriev D. Yu.. Complexity of deciding Tarski algebra. Journal of Symbolic Computation, 1988, 5: 65-108

[28] Grigoriev D. Yu., Vorobjov N. N.. Solving systems of polynomial inequalities in subexponential time. Journal of Symbolic Computation, 1988, 5: 37-64

[29] Koiran P.. The real dimension problem is NP_R-complete. Journal Complexity, 1999, 15: 227-238

[30] Kostlan E.. Complexity theory of numerical linear algebra. Journal of Computational and Applied Mathematics, 1988, 22: 219-230

[31] Lairez P.. A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time. Found. Comput. Math., 2017

[32] Mehta M. L.. Random matrices, 2004 3 Amsterdam: Elsevier/Academic Press

[33] Niyogi P., Smale S., Weinberger S.. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 2008, 39: 419-441

[34] Renegar J.. On the computational complexity and geometry of the first-order theory of the reals, Part I. Journal of Symbolic Computation, 1992, 13: 255-299

[35] Renegar J.. On the computational complexity and geometry of the first-order theory of the reals, Part II. Journal of Symbolic Computation, 1992, 13: 301-327

[36] Renegar J.. On the computational complexity and geometry of the first-order theory of the reals, Part III. Journal of Symbolic Computation, 1992, 13: 329-352

[37] Renegar J.. Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim., 1995, 5: 506-524

[38] Renegar J.. Linear programming, complexity theory and elementary functional analysis. Math. Program., 1995, 70: 279-351

[39] Shub M., Smale S.. Complexity of Bézout’s theorem I: Geometric aspects. Journal of the Amer. Math. Soc., 1993, 6: 459-501

[40] Shub M., Smale S.. Eyssette F., Galligo A.. Complexity of Bézout’s theorem II: Volumes and probabilities. Computational Algebraic Geometry, 1993 267-285

[41] Shub M., Smale S.. Complexity of Bézout’s theorem III: Condition number and packing. Journal of Complexity, 1993, 9: 4-14

[42] Shub M., Smale S.. Complexity of Bézout’s theorem V: Polynomial time. Theoret. Comp. Sci., 1994, 133: 141-164

[43] Shub M., Smale S.. Complexity of Bézout’s Theorem IV: Probability of success, extensions. SIAM J. of Numer. Anal., 1996, 33: 128-148

[44] Smale S.. Ewing R., Gross K., Martin C.. Newton’s method estimates from data at one point, The Merging of Disciplines: New Directions in Pure. Applied, and Computational Mathematics, 1986, New York: Springer-Verlag

[45] Tarski A.. A Decision Method for Elementary Algebra and Geometry, 1951

[46] Trefethen L. N., Bau D. III Numerical Linear Algebra, 1997, Philadelphia: SIAM

[47] Wüthrich H. R.. Specker E., Strassen V.. Ein Entscheidungsverfahren für die Theorie der reell-abgeschlossenen Körper. Komplexit ät von Entscheidungsproblemen, 1976, Berlin: Springer-Verlag 138-162