PHIDM: Persistent Homology – Images, Data and Maps

Publications

This page contains a list of publications which contain results of research supported from the grant (in an arbitrary order).

6. M. Krčál, P. Pilarczyk, Computation of Cubical Steenrod Squares. In: A. Bac and J.-L. Mari (Eds.): Computational Topology in Image Context: 6th International Workshop, CTIC 2016, Marseille, France, June 15-17, 2016, Proceedings. LNCS 9667, pp. 140-151, 2016. DOI: 10.1007/978-3-319-39441-1_13.
[Lecture Notes in Computer Science is a book series indexed in ISI, ISSN 0302-9743.]
Abstract: Bitmap images of arbitrary dimension may be formally perceived as unions of m-dimensional boxes aligned with respect to a rectangular grid in R^m. Cohomology and homology groups are well known topological invariants of such sets. Cohomological operations, such as the cup product, provide higher-order algebraic topological invariants, especially important for digital images of dimension higher than 3. If such an operation is determined at the level of simplicial chains [see e.g. Gonzalez-Diaz, Real, Homology, Homotopy Appl, 2003, 83-93], then it is effectively computable. However, decomposing a cubical complex into a simplicial one deleteriously affects the efficiency of such an approach. In order to avoid this overhead, a direct cubical approach was applied in [Pilarczyk, Real, Adv. Comput. Math., 2015, 253-275] for the cup product in cohomology, and implemented in the ChainCon software package.
We establish a formula for the Steenrod square operations [see Steenrod, Annals of Mathematics. Second Series, 1947, 290-320] directly at the level of cubical chains, and we prove the correctness of this formula. An implementation of this formula is programmed in C++ within the ChainCon software framework. We provide a few examples and discuss the effectiveness of this approach.
One specific application follows from the fact that Steenrod squares yield tests for the topological extension problem: Can a given map from a set A to a sphere S^d be extended to a given super-complex X of A? In particular, the Robust Satisfiability Problem (ROB-SAT) reduces to the extension problem.
[PDF]

5. T. Miyaji, P. Pilarczyk, M. Gameiro, H. Kokubu, K. Mischaikow, A study of rigorous ODE integrators for multi-scale set-oriented computations, Appl. Numer. Math., Vol. 107 (2016), 34-47. DOI: 10.1016/j.apnum.2016.04.005.
[Applied Numerical Mathematics is indexed in ISI, ISSN 0168-9274, Impact Factor (2014): 1.221, MathSciNet MCQ (2014): 0.85.]
Abstract: We study the usefulness of two most prominent publicly available rigorous ODE integrators: one provided by the CAPD group, the other based on the COSY Infinity project. Both integrators are capable of handling entire sets of initial conditions and provide tight rigorous outer enclosures of the images under a time-T map. We conduct extensive benchmark computations using the well-known Lorenz system, and compare the computation time against the final accuracy achieved. We also discuss the effect of a few technical parameters, such as the order of the numerical integration method, the value of T, and the phase space resolution. We conclude that COSY may provide more precise results due to its ability of avoiding the variable dependency problem. However, the overall cost of computations conducted using CAPD is typically lower, especially when intervals of parameters are involved. Moreover, access to COSY is limited (registration required) and the rigorous ODE integrators are not publicly available, while CAPD is an open source free software project. Therefore, we recommend the latter integrator for this kind of computations. Nevertheless, proper choice of the various integration parameters turns out to be of even greater importance than the choice of the integrator itself.
[PDF]

4. P. Pilarczyk, A space-efficient algorithm for computing the minimum cycle mean in a directed graph, submitted.
Abstract: An algorithm is introduced for computing the minimum cycle mean in a strongly connected directed graph with n vertices and m arcs that requires O (n) working space. This is a considerable improvement for sparse graphs in comparison to the classical algorithms that require O (n²) working space. The time complexity of the algorithm is still O (n m). An implementation in C++ is made publicly available at http://www.pawelpilarczyk.com/cymealg/.
[PDF]

3. A. Golmakani, S. Luzzatto, P. Pilarczyk, Uniform expansivity outside a critical neighborhood in the quadratic family, Exp. Math., Vol. 25, No. 2 (2016), 116-124.
DOI: 10.1080/10586458.2015.1048011.
[Experimental Mathematics is indexed in ISI, 1058-6458 (Print), 1944-950X (Online), Impact Factor (2013): 1, MathSciNet MCQ (2013): 0.64.]
Abstract: We use rigorous numerical techniques to compute a lower bound for the exponent of expansivity outside a neighborhood of the critical point for thousands of intervals of parameter values in the quadratic family. We first compute a radius of the critical neighborhood outside which the map is uniformly expanding. This radius is taken as small as possible, yet large enough for our numerical procedure to succeed in proving that the expansivity exponent outside this neighborhood is positive. Then, for each of the intervals, we compute a lower bound for this expansivity exponent, valid for all the parameters in that interval. We illustrate and study the distribution of the radii and the expansivity exponents. The results of our computations are mathematically rigorous. The source code of the software and the results of the computations are made publicly available at http://www.pawelpilarczyk.com/quadratic/.
[PDF]

2. S. Harker, H. Kokubu, K. Mischaikow, P. Pilarczyk, Inducing a map on homology from a correspondence, Proc. Amer. Math. Soc., Vol. 144, No. 4 (2016), 1787-1801.
DOI: 10.1090/proc/12812.
[Proceedings of the American Mathematical Society (Proceedings of the AMS) are indexed in ISI, ISSN 1088-6826 (online), ISSN 0002-9939 (print), Impact Factor (2013): 0.627, MathSciNet MCQ (2013): 0.64.]
Abstract: We study the homomorphism induced in homology by a closed correspondence between topological spaces, using projections from the graph of the correspondence to its domain and codomain. We provide assumptions under which the homomorphism induced by an outer approximation of a continuous map coincides with the homomorphism induced in homology by the map. In contrast to more classical results we do not require that the projection to the domain have acyclic preimages. Moreover, we show that it is possible to retrieve correct homological information from a correspondence even if some data is missing or perturbed. Finally, we describe an application to combinatorial maps that are either outer approximations of continuous maps or reconstructions of such maps from a finite set of data points.
[PDF] [arXiv:1411.7563] [math.AT]

1. D.H. Knipl, P. Pilarczyk, G. Röst, Rich bifurcation structure in a two-patch vaccination model, SIAM J. Appl. Dyn. Syst., Vol. 14, No. 2 (2015), 980-1017.
DOI: 10.1137/140993934.
[SIAM Journal on Applied Dynamical Systems (SIADS) is indexed in ISI, ISSN 1536-0040, Impact Factor (2013): 1.245, MathSciNet MCQ (2013): 0.88.]
Abstract: We show that incorporating spatial dispersal of individuals into a simple vaccination epidemic model may give rise to a model that exhibits rich dynamical behavior. Using an SIVS (susceptible – infected – vaccinated – susceptible) model as a basis, we describe the spread of an infectious disease in a population split into two regions. In each sub-population, both forward and backward bifurcations can occur. This implies that for disconnected regions, the two-patch system may admit several steady states. We consider traveling between the regions, and investigate the impact of spatial dispersal of individuals on the model dynamics. We establish conditions for the existence of multiple non-trivial steady states in the system, and we study the structure of the equilibria. The mathematical analysis reveals an unusually rich dynamical behavior, not normally found in the simple epidemic models. In addition to the disease free equilibrium, eight endemic equilibria emerge from backward transcritical and saddle-node bifurcation points, forming an interesting bifurcation diagram. Stability of steady states, their bifurcations and the global dynamics are investigated with analytical tools, numerical simulations, and rigorous set-oriented numerical computations.
[PDF]