An algorithm for calculating top-dimensional bounding chains

We describe the \textsc{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)$--...

Full description

Saved in:
Bibliographic Details
Published in:PeerJ preprints 2017-08
Main Authors: J Frederico Carvalho, Vejdemo-Johansson, Mikael, Kragic, Danica, Pokorny, Florian T
Format: Article
Language:English
Subjects:
Algorithms
Computer applications
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe the \textsc{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.
ISSN:2167-9843
DOI:10.7287/peerj.preprints.3151v1