Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombinatorial Conditions for Directed Collapsing
47
0
0.0
(
0
)
Added by
Robyn Brooks
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The purpose of this article is to study directed collapsibility of directed Euclidean cubical complexes. One application of this is in the nontrivial task of verifying the execution of concurrent programs. The classical definition of collapsibility involves certain conditions on a pair of cubes of the complex. The direction of the space can be taken into account by requiring that the past links of vertices remain homotopy equivalent after collapsing. We call this type of collapse a link-preserving directed collapse. In this paper, we give combinatorially equivalent conditions for preserving the topology of the links, allowing for the implementation of an algorithm for collapsing a directed Euclidean cubical complex. Furthermore, we give conditions for when link-preserving directed collapses preserve the contractability and connectedness of directed path spaces, as well as examples when link-preserving directed collapses do not preserve the number of connected components of the path space between the minimum and a given vertex.
rate research
Read More
In the directed setting, the spaces of directed paths between fixed initial and terminal points are the defining feature for distinguishing different directed spaces. The simplest case is when the space of directed paths is homotopy equivalent to that of a single path; we call this the trivial space of directed paths. Directed spaces that are topologically trivial may have non-trivial spaces of directed paths, which means that information is lost when the direction of these topological spaces is ignored. We define a notion of directed collapsibility in the setting of a directed Euclidean cubical complex using the spaces of directed paths of the underlying directed topological space relative to an initial or a final vertex. In addition, we give sufficient conditions for a directed Euclidean cubical complex to have a contractible or a connected space of directed paths from a fixed initial vertex. We also give sufficient conditions for the path space between two vertices in a Euclidean cubical complex to be disconnected. Our results have applications to speeding up the verification process of concurrent programming and to understanding partial executions in concurrent programs.
In this paper we study the properties of the homology of different geometric filtered complexes (such as Vietoris-Rips, Cech and witness complexes) built on top of precompact spaces. Using recent developments in the theory of topological persistence we provide simple and natural proofs of the stability of the persistent homology of such complexes with respect to the Gromov--Hausdorff distance. We also exhibit a few noteworthy properties of the homology of the Rips and Cech complexes built on top of compact spaces.
An augmented metric space is a metric space $(X, d_X)$ equipped with a function $f_X: X to mathbb{R}$. This type of data arises commonly in practice, e.g, a point cloud $X$ in $mathbb{R}^d$ where each point $xin X$ has a density function value $f_X(x)$ associated to it. An augmented metric space $(X, d_X, f_X)$ naturally gives rise to a 2-parameter filtration $mathcal{K}$. However, the resulting 2-parameter persistent homology $mathrm{H}_{bullet}(mathcal{K})$ could still be of wild representation type, and may not have simple indecomposables. In this paper, motivated by the elder-rule for the zeroth homology of 1-parameter filtration, we propose a barcode-like summary, called the elder-rule-staircode, as a way to encode $mathrm{H}_0(mathcal{K})$. Specifically, if $n = |X|$, the elder-rule-staircode consists of $n$ number of staircase-like blocks in the plane. We show that if $mathrm{H}_0(mathcal{K})$ is interval decomposable, then the barcode of $mathrm{H}_0(mathcal{K})$ is equal to the elder-rule-staircode. Furthermore, regardless of the interval decomposability, the fibered barcode, the dimension function (a.k.a. the Hilbert function), and the graded Betti numbers of $mathrm{H}_0(mathcal{K})$ can all be efficiently computed once the elder-rule-staircode is given. Finally, we develop and implement an efficient algorithm to compute the elder-rule-staircode in $O(n^2log n)$ time, which can be improved to $O(n^2alpha(n))$ if $X$ is from a fixed dimensional Euclidean space $mathbb{R}^d$, where $alpha(n)$ is the inverse Ackermann function.
Characterizing the dynamics of time-evolving data within the framework of topological data analysis (TDA) has been attracting increasingly more attention. Popular instances of time-evolving data include flocking/swarming behaviors in animals and social networks in the human sphere. A natural mathematical model for such collective behaviors is a dynamic point cloud, or more generally a dynamic metric space (DMS). In this paper we extend the Rips filtration stability result for (static) metric spaces to the setting of DMSs. We do this by devising a certain three-parameter spatiotemporal filtration of a DMS. Applying the homology functor to this filtration gives rise to multidimensional persistence module derived from the DMS. We show that this multidimensional module enjoys stability under a suitable generalization of the Gromov-Hausdorff distance which permits metrizing the collection of all DMSs. On the other hand, it is recognized that, in general, comparing two multidimensional persistence modules leads to intractable computational problems. For the purpose of practical comparison of DMSs, we focus on both the rank invariant or the dimension function of the multidimensional persistence module that is derived from a DMS. We specifically propose to utilize a certain metric d for comparing these invariants: In our work this d is either (1) a certain generalization of the erosion distance by Patel, or (2) a specialized version of the well known interleaving distance. We also study the computational complexity associated to both choices of d.
The classical persistence algorithm virtually computes the unique decomposition of a persistence module implicitly given by an input simplicial filtration. Based on matrix reduction, this algorithm is a cornerstone of the emergent area of topological data analysis. Its input is a simplicial filtration defined over the integers $mathbb{Z}$ giving rise to a $1$-parameter persistence module. It has been recognized that multi-parameter version of persistence modules given by simplicial filtrations over $d$-dimensional integer grids $mathbb{Z}^d$ is equally or perhaps more important in data science applications. However, in the multi-parameter setting, one of the main challenges is that topological summaries based on algebraic structure such as decompositions and bottleneck distances cannot be as efficiently computed as in the $1$-parameter case because there is no known extension of the persistence algorithm to multi-parameter persistence modules. We present an efficient algorithm to compute the unique decomposition of a finitely presented persistence module $M$ defined over the multiparameter $mathbb{Z}^d$.The algorithm first assumes that the module is presented with a set of $N$ generators and relations that are emph{distinctly graded}. Based on a generalized matrix reduction technique it runs in $O(N^{2omega+1})$ time where $omega<2.373$ is the exponent for matrix multiplication. This is much better than the well known algorithm called Meataxe which runs in $tilde{O}(N^{6(d+1)})$ time on such an input. In practice, persistence modules are usually induced by simplicial filtrations. With such an input consisting of $n$ simplices, our algorithm runs in $O(n^{2omega+1})$ time for $d=2$ and in $O(n^{d(2omega + 1)})$ time for $d>2$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
