Document Open Access Logo

On Computability and Triviality of Well Groups

Authors Peter Franek, Marek Krcál

PDF

File

Thumbnail PDF
PDF
LIPIcs.SOCG.2015.842.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • nonlinear equations
  • robustness
  • well groups
  • computation
  • homotopy theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1.

Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set.

For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of  the (dim K-n)th well group is exact.

For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.

Cite As Get BibTex

Peter Franek and Marek Krcál. On Computability and Triviality of Well Groups. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 842-856, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.842

Author Details

Peter Franek
Marek Krcál

References

  1. G. E. Alefeld, F. A. Potra, and Z. Shen. On the existence theorems of kantorovich, moore and miranda. Technical Report 01/04, Institut für Wissenschaftliches Rechnen und Mathematische Modellbildung, 2001. Google Scholar
  2. A. Ben-Tal, L.E. Ghaoui, and A. Nemirovski. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, 2009. Google Scholar
  3. P. Bendich, H. Edelsbrunner, D. Morozov, and A. Patel. Homology and robustness of level and interlevel sets. Homology, Homotopy and Applications, 15(1):51-72, 2013. Google Scholar
  4. G. Carlsson. Topology and data. Bull. Amer. Math. Soc. (N.S.), 46(2):255-308, 2009. Google Scholar
  5. F. Chazal, A. Patel, and P. Škraba. Computing the robustness of roots. Applied Mathematics Letters, 25(11):1725 - 1728, November 2012. Google Scholar
  6. P. Collins. Computability and representations of the zero set. Electron. Notes Theor. Comput. Sci., 221:37-43, December 2008. Google Scholar
  7. H. Edelsbrunner and J. L. Harer. Computational topology. American Mathematical Society, Providence, RI, 2010. Google Scholar
  8. H. Edelsbrunner, D. Morozov, and A. Patel. Quantifying transversality by measuring the robustness of intersections. Foundations of Computational Mathematics, 11(3):345-361, 2011. Google Scholar
  9. Herbert Edelsbrunner, Dmitriy Morozov, and Amit Patel. Quantifying transversality by measuring the robustness of intersections. Foundations of Computational Mathematics, 11(3):345-361, 2011. Google Scholar
  10. P. Franek and M. Krčál. Robust satisfiability of systems of equations. In Proc. Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2014. Extended version accepted to Journal of ACM. Preprint in arXiv:1402.0858. Google Scholar
  11. P. Franek and M. Krčál. On computability and triviality of well groups, 2015. Preprint arXiv:1501.03641v2. Google Scholar
  12. P. Franek, S. Ratschan, and P. Zgliczynski. Quasi-decidability of a fragment of the analytic first-order theory of real numbers, 2012. Preprint in arXiv:1309.6280. Google Scholar
  13. A. Frommer and B. Lang. Existence tests for solutions of nonlinear equations using Borsuk’s theorem. SIAM Journal on Numerical Analysis, 43(3):1348-1361, 2005. Google Scholar
  14. F. Goudail and P. Réfrégier. Statistical Image Processing Techniques for Noisy Images: An Application-Oriented Approach. Kluwer Academic / Plenum Publishers, 2004. Google Scholar
  15. A. Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, 2001. Google Scholar
  16. N.J. Higham. Accuracy and Stability of Numerical Algorithms: Second Edition. Society for Industrial and Applied Mathematics, 2002. Google Scholar
  17. R. B. Kearfott. On existence and uniqueness verification for non-smooth functions. Reliable Computing, 8(4):267-282, 2002. Google Scholar
  18. S. Mardešić. Thirty years of shape theory. Mathematical Communications, 2(1):1-12, 1997. Google Scholar
  19. A. Neumaier. Interval Methods for Systems of Equations. Cambridge Univ. Press, Cambridge, 1990. Google Scholar
  20. P. Franek, M. Krčál. Cohomotopy groups capture robust properties of zero sets. Manuscript in preparation, 2014. Google Scholar
  21. V. V. Prasolov. Elements of Homology Theory. Graduate Studies in Mathematics. American Mathematical Society, 2007. Google Scholar
  22. P. Škraba, B. Wang, Ch. Guoning, and P. Rosen. 2D vector field simplification based on robustness, 2014. to appear in IEEE Pacific Visualization (PacificVis). Google Scholar
  23. M. Čadek, M. Krčál, J. Matoušek, F. Sergeraert, L. Vokř\'ιnek, and U. Wagner. Computing all maps into a sphere. J. ACM, 61(3):17:1-17:44, June 2014. Google Scholar
  24. A.H. Wallace. Algebraic Topology: Homology and Cohomology. Dover Books on Mathematics Series. Dover Publications, 2007. Google Scholar
  25. J.H.C. Whitehead. On the theory of obstructions. Annals of Mathematics, pages 68-84, 1951. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact