An algorithm for calculating top-dimensional bounding chains

J Frederico Carvalho; Mikael Vejdemo-Johansson; Danica Kragic; Florian T Pokorny

doi:10.7717/peerj-cs.153

An algorithm for calculating top-dimensional bounding chains

PeerJ Comput Sci. 2018 May 28:4:e153. doi: 10.7717/peerj-cs.153. eCollection 2018.

Authors

J Frederico Carvalho¹, Mikael Vejdemo-Johansson², Danica Kragic¹, Florian T Pokorny¹

Affiliations

¹ CAS/RPL, KTH, Royal Institute of Technology, Stockholm, Sweden.
² Mathematics Department, City University of New York, College of Staten Island, New York, NY, United States of America.

Abstract

We describe the Coefficient-Flow algorithm for calculating the bounding chain of an $(n-1)$-boundary on an $n$-manifold-like simplicial complex $S$. We prove its correctness and show that it has a computational time complexity of O(|S ^(n-1)|) (where S ^(n-1) is the set of $(n-1)$-faces of $S$). We estimate the big- $O$ coefficient which depends on the dimension of $S$ and the implementation. We present an implementation, experimentally evaluate the complexity of our algorithm, and compare its performance with that of solving the underlying linear system.

Keywords: Computational algebraic topology; Homology.

Grants and funding

This work has been supported by the Knut and Alice Wallenberg Foundation and the Swedish Research Council. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.