Persistent Homology of Semialgebraic Sets

DOI10.1137/22M1494415arXiv2202.09591OpenAlexW4387134400MaRDI QIDQ6087751FDOQ6087751

Authors: Saugata Basu, Negin Karisani 

Publication date: 16 November 2023

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Abstract: We give an algorithm with singly exponential complexity for computing the barcodes up to dimension $ell$ (for any fixed $ellgeq0$) of the filtration of a given semi-algebraic set by the sub-level sets of a given polynomial. Our algorithm is the first algorithm for this problem with singly exponential complexity, and generalizes the corresponding results for computing the Betti numbers up to dimension $ell$ of semi-algebraic sets with no filtration present.

Full work available at URL: https://arxiv.org/abs/2202.09591

Recommendations

• Computing the homology functor on semi-algebraic maps and diagrams
• Computing the homology of semialgebraic sets. II: General formulas
• Computing persistent homology
• Computing the homology of semialgebraic sets. I: Lax formulas
• Computing the first few Betti numbers of semi-algebraic sets in single exponential time

zbMATH Keywords

persistent homologysimplicial complexsemialgebraic setsbarcodes

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10) Real algebra (13J30) Classical real and complex (co)homology in algebraic geometry (14F25)

Cites Work

• The structure and stability of persistence modules
• Persistent homology -- a survey
• Computational topology. An introduction
• Barcodes: The persistent topology of data
• Decomposition of pointwise finite-dimensional persistence modules.
• Morse Theory. (AM-51)
• Title not available (Why is that?)
• Categorification of persistent homology
• Title not available (Why is that?)
• On the Betti Numbers of Real Varieties
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Algorithms in real algebraic geometry
• Ensembles et morphismes stratifiés
• Title not available (Why is that?)
• Approximation of definable sets by compact families, and upper bounds on homotopy and homology
• Title not available (Why is that?)
• On the homology of algebraic varieties over real closed fields.
• Computing Roadmaps of General Semi-Algebraic Sets
• Computing roadmaps of semi-algebraic sets on a variety
• Counting connected components of a semialgebraic set in subexponential time
• A baby step-giant step roadmap algorithm for general algebraic sets
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets
• On the number of homotopy types of fibres of a definable map
• Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings
• Title not available (Why is that?)
• Persistent homology of groups.
• Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems
• Computing the first Betti number of a semi-algebraic set
• Learning algebraic varieties from samples
• Persistent homology and microlocal sheaf theory
• Title not available (Why is that?)
• Computing the first few Betti numbers of semi-algebraic sets in single exponential time
• Computing the Euler-Poincaré characteristics of sign conditions
• Algorithms in real algebraic geometry: a survey
• Computing the homology of basic semialgebraic sets in weak exponential time
• Computational topology for data analysis
• Computing the homology of semialgebraic sets. II: General formulas
• Computing the homology of semialgebraic sets. I: Lax formulas
• Topological persistence in geometry and analysis
• Efficient simplicial replacement of semialgebraic sets
• Real algebraic geometry. Translated from the Russian by Gerald G. Gould and David Kramer

Cited In (5)

• Title not available (Why is that?)
• On the structural theorem of persistent homology
• Efficient computation of a semi-algebraic basis of the first homology group of a semi-algebraic set
• Computing the homology functor on semi-algebraic maps and diagrams
• The persistent topology of optimal transport based metric thickenings

This page was built for publication: Persistent Homology of Semialgebraic Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087751)