Author(s):

Chen, Chao; Kerber, Michael

Article Title: 
An output sensitive algorithm for persistent homology

Affiliation 
IST Austria 
Abstract: 
In this paper, we present the first outputsensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ > 0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0, 1), the running time is O (C (1  δ) Γ R d (n) log n), where C (1  δ) Γ is the number of homology classes with persistence at least (1  δ) Γ, n is the total number of simplices in the complex, d its dimension, and R d (n) is the complexity of computing the rank of an n × n matrix with O (d n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O (C (1  δ) Γ n 2.376) algorithm, an O (C (1  δ) Γ n 2.28) LasVegas algorithm, or an O (C (1  δ) Γ n 2 + ε{lunate}) MonteCarlo algorithm for an arbitrary ε{lunate} > 0. The space complexity of the MonteCarlo version is bounded by O (d n) = O (n log n).

Keywords: 
persistent homology; Computational topology; Randomized algorithms; Rank computation

Journal Title:

Computational Geometry: Theory and Applications

Volume: 
46

Issue 
4

ISSN:

09257721

Publisher:

Elsevier

Date Published:

20130501

Start Page: 
435

End Page:

447

Copyright Statement: 
Copyright © 2012 Elsevier B.V. All rights reserved.

DOI: 
10.1016/j.comgeo.2012.02.010

Notes: 
The authors thank Herbert Edelsbrunner for many helpful discussions and suggestions. Moreover, they are grateful for the careful reviews that helped to improve the quality of the paper.

Open access: 
no 