Computing the Homology of Semialgebraic Sets. I: Lax Formulas
Tóm tắt
We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of closed semialgebraic sets given by Boolean formulas without negations over lax polynomial inequalities. The algorithm works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data. All previous algorithms solving this problem have doubly exponential complexity. Our algorithm thus represents an exponential acceleration over state-of-the-art algorithms for all input data outside a set that vanishes exponentially fast.
Tài liệu tham khảo
D. Amelunxen and M. Lotz. Average-case complexity without the black swans. J. Complexity, 41:82–101, 2017.
S. Basu. On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pages 408–417. ACM, 1996.
S. Basu. Computing the first few Betti numbers of semi-algebraic sets in single exponential time. Journal of Symbolic Computation, 41(10):1125–1154, 2006.
S. Basu, R. Pollack, and M.-F. Roy. On the combinatorial and algebraic complexity of quantifier elimination. Journal of the Assoc. Comput. Mach., 43:1002–1045, 1996.
S. Basu, R. Pollack, and M.-F. Roy. Computing roadmaps of semi-algebraic sets on a variety. Journal of the Amer. Math. Soc., 33:55–82, 1999.
C. Beltrán and L.M. Pardo. Smale’s 17th problem: average polynomial time to compute affine and projective solutions. J. Amer. Math. Soc., 22(2):363–385, 2009.
R. Benedetti and J.-J. Risler. Real algebraic and semi-algebraic sets. Actualités Mathématiques. [Current Mathematical Topics]. Hermann, Paris, 1990.
L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. (N.S.), 21(1):1–46, 1989.
J. Bochnak, M. Coste, and M.-F. Roy. Real algebraic geometry, volume 36 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3). Springer-Verlag, Berlin, 1998. Translated from the 1987 French original, Revised by the authors.
H. Bosse, M. Grötschel, and M. Henk. Polynomial inequalities representing polyhedra. Math. Program., 103(1, Ser. A):35–44, 2005.
M. Brown. Locally flat imbeddings of topological manifolds. Annals of Mathematics, 75:331–341, 1962.
P. Bürgisser and F. Cucker. Exotic quantifiers, complexity classes, and complete problems. Found. Comput. Math., 9(2):135–170, 2009.
P. Bürgisser and F. Cucker. On a problem posed by Steve Smale. Annals of Mathematics, 174:1785–1836, 2011.
P. Bürgisser and F. Cucker. Condition, volume 349 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 2013.
P. Bürgisser, F. Cucker, and P. Lairez. Computing the homology of basic semialgebraic sets in weak exponential time. J. ACM, 66(1):5:1–5:30, December 2018.
P. Bürgisser, F. Cucker, and M. Lotz. The probability that a slightly perturbed numerical analysis problem is difficult. Mathematics of Computation, 77:1559–1583, 2008.
J. Canny. The complexity of robot motion planning, volume 1987 of ACM Doctoral Dissertation Awards. MIT Press, Cambridge, MA, 1988.
J. Canny. Computing roadmaps of general semi-algebraic sets. Comput. J., 36(5):504–514, 1993.
J. Canny, D.Yu. Grigorev, and N.N. Vorobjov. Finding connected components of a semialgebraic set in subexponential time. Appl. Algebra Engrg. Comm. Comput., 2(4):217–238, 1992.
F. Chazal, D. Cohen-Steiner, and A. Lieutier. A sampling theory for compact sets in Euclidean space. In Computational geometry (SCG’06), pages 319–326. ACM, New York, 2006.
F. Chazal and A. Lieutier. The “\(\lambda \)-medial axis”. Graphical Models, 67(4):304 – 331, 2005.
F. Chazal and A. Lieutier. Weak feature size and persistant homology: computing homology of solids in \(\mathbb{R}^n\) from noisy data samples. In Computational geometry (SCG’05), pages 255–262. ACM, New York, 2005.
G.E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition, pages 134–183. Lecture Notes in Comput. Sci., Vol. 33. Springer, Berlin, 1975.
R. Connelly. A New Proof of Brown’s Collaring Theorem. Proc. Am. Math. Soc., 27:180, 1971.
F. Cucker. Approximate zeros and condition numbers. J. Complexity, 15:214–226, 1999.
F. Cucker, T. Krick, G. Malajovich, and M. Wschebor. A numerical algorithm for zero counting. I: Complexity and accuracy. J. Complexity, 24:582–605, 2008.
F. Cucker, T. Krick, G. Malajovich, and M. Wschebor. A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis . J. Fixed Point Theory Appl., 6:285–294, 2009.
F. Cucker, T. Krick, G. Malajovich, and M. Wschebor. A numerical algorithm for zero counting. III: Randomization and condition. Adv. Applied Math., 48:215–248, 2012.
F. Cucker, T. Krick, and M. Shub. Computing the homology of real projective sets. Found. Comput. Math., 18:929–970, 2018.
F. Cucker and S. Smale. Complexity estimates depending on condition and round-off error. Journal of the Assoc. Comput. Mach., 46:113–184, 1999.
J. Demmel. The probability that a numerical analysis problem is difficult. Math. Comp., 50:449–480, 1988.
A.H. Durfee. Neighborhoods of algebraic sets. Trans. Amer. Math. Soc., 276(2):517–530, 1983.
H. Edelsbrunner and J.L. Harer. Computational topology: An introduction. American Mathematical Society, Providence, RI, 2010.
H. Federer. Curvature measures. Trans. Amer. Math. Soc., 93:418–491, 1959.
C.G. Gibson, K. Wirthmüller, A.A. du Plessis, and E.J.N. Looijenga. Topological stability of smooth mappings. Lecture Notes in Mathematics, Vol. 552. Springer-Verlag, Berlin-New York, 1976.
H.H. Goldstine and J. von Neumann. Numerical inverting matrices of high order, II. Proceedings of the Amer. Math. Soc., 2:188–202, 1951.
D.Yu. Grigoriev. Complexity of deciding Tarski algebra. Journal of Symbolic Computation, 5:65–108, 1988.
D.Yu. Grigoriev and N.N. Vorobjov. Solving systems of polynomial inequalities in subexponential time. Journal of Symbolic Computation, 5:37–64, 1988.
D.Yu. Grigoriev and N.N. Vorobjov. Counting connected components of a semialgebraic set in subexponential time. Computational Complexity, 2:133–186, 1992.
A. Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002.
J. Heintz, M.-F. Roy, and P. Solerno. Single exponential path finding in semi-algebraic sets II: The general case. In C.L. Bajaj, editor, Algebraic Geometry and its Applications, pages 449–465. Springer-Verlag, 1994.
R.E. Hodel. An Introduction to Mathematical Logic. Dover Publications Inc., Mineola, New York, 2013.
P. Koiran. The real dimension problem is \({\rm NP}_{\mathbb{R}}\)-complete. J. Complexity, 15:227–238, 1999.
E. Kostlan. Complexity theory of numerical linear algebra. J. of Computational and Applied Mathematics, 22:219–230, 1988.
P. Lairez. A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time. Found. Comput. Math., 17(5):1265–1292, 2017.
J. Mather. Notes on topological stability. Bull. Amer. Math. Soc. (N.S.), 49(4):475–506, 2012.
J. von Neumann and H.H. Goldstine. Numerical inverting matrices of high order. Bull. Amer. Math. Soc., 53:1021–1099, 1947.
P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 39(1-3):419–441, 2008.
J. Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part I. Journal of Symbolic Computation, 13:255–299, 1992.
D.J.S. Robinson. A course in the theory of groups, volume 80 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1996.
J.J. Rotman. An introduction to algebraic topology, volume 119 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1988.
J.J. Rotman. An introduction to homological algebra. Universitext. Springer, New York, second edition, 2009.
J.T. Schwartz and M. Sharir. A survey of motion planning and related geometric algorithms. Artificial Intelligence, 37:157–169, 1988.
M. Shub and S. Smale. Complexity of Bézout’s Theorem I: geometric aspects. Journal of the Amer. Math. Soc., 6:459–501, 1993.
M. Shub and S. Smale. Complexity of Bézout’s Theorem II: volumes and probabilities. In F. Eyssette and A. Galligo, editors, Computational Algebraic Geometry, volume 109 of Progress in Mathematics, pages 267–285. Birkhäuser, 1993.
M. Shub and S. Smale. Complexity of Bézout’s Theorem III: condition number and packing. Journal of Complexity, 9:4–14, 1993.
M. Shub and S. Smale. Complexity of Bézout’s Theorem V: polynomial time. Theoret. Comp. Sci., 133:141–164, 1994.
M. Shub and S. Smale. Complexity of Bézout’s Theorem IV: probability of success; extensions. SIAM J. of Numer. Anal., 33:128–148, 1996.
S. Smale. Complexity theory and numerical analysis. In A. Iserles, editor, Acta Numerica, pages 523–551. Cambridge University Press, 1997.
S. Smale. Mathematical problems for the next century. Mathematical Intelligencer, 20:7–15, 1998.
E. Spanier. Algebraic Topology. McGraw-Hill, New York, 1966.
A. Tarski. A decision method for elementary algebra and geometry. University of California Press, Berkeley and Los Angeles, Calif., 1951. 2nd ed.
R. Thom. Ensembles et morphismes stratifiés. Bull. Amer. Math. Soc., 75:240–284, 1969.
A.M. Turing. Rounding-off errors in matrix processes. Quart. J. Mech. Appl. Math., 1:287–308, 1948.
H.R. Wüthrich. Ein Entscheidungsverfahren für die Theorie der reell-abgeschlossenen Körper. In E. Specker and V. Strassen, editors, Komplexität von Entscheidungsproblemen, volume 43 of Lect. Notes in Comp. Sci., pages 138–162. Springer-Verlag, 1976.
G.M. Ziegler. Lectures on Polytopes. Graduate Texts in Mathematics. Springer New York, 2012.