---
_id: '3270'
abstract:
- lang: eng
  text: 'The persistence diagram of a filtered simplicial com- plex is usually computed
    by reducing the boundary matrix of the complex. We introduce a simple op- timization
    technique: by processing the simplices of the complex in decreasing dimension,
    we can “kill” columns (i.e., set them to zero) without reducing them. This technique
    completely avoids reduction on roughly half of the columns. We demonstrate that
    this idea significantly improves the running time of the reduction algorithm in
    practice. We also give an output-sensitive complexity analysis for the new al-
    gorithm which yields to sub-cubic asymptotic bounds under certain assumptions.'
author:
- first_name: Chao
  full_name: Chen, Chao
  id: 3E92416E-F248-11E8-B48F-1D18A9856A87
  last_name: Chen
- first_name: Michael
  full_name: Kerber, Michael
  id: 36E4574A-F248-11E8-B48F-1D18A9856A87
  last_name: Kerber
  orcid: 0000-0002-8030-9299
citation:
  ama: 'Chen C, Kerber M. Persistent homology computation with a twist. In: TU Dortmund;
    2011:197-200.'
  apa: 'Chen, C., & Kerber, M. (2011). Persistent homology computation with a
    twist (pp. 197–200). Presented at the EuroCG: European Workshop on Computational
    Geometry, Morschach, Switzerland: TU Dortmund.'
  chicago: Chen, Chao, and Michael Kerber. “Persistent Homology Computation with a
    Twist,” 197–200. TU Dortmund, 2011.
  ieee: 'C. Chen and M. Kerber, “Persistent homology computation with a twist,” presented
    at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland,
    2011, pp. 197–200.'
  ista: 'Chen C, Kerber M. 2011. Persistent homology computation with a twist. EuroCG:
    European Workshop on Computational Geometry, 197–200.'
  mla: Chen, Chao, and Michael Kerber. <i>Persistent Homology Computation with a Twist</i>.
    TU Dortmund, 2011, pp. 197–200.
  short: C. Chen, M. Kerber, in:, TU Dortmund, 2011, pp. 197–200.
conference:
  end_date: 2011-03-30
  location: Morschach, Switzerland
  name: 'EuroCG: European Workshop on Computational Geometry'
  start_date: 2011-03-28
corr_author: '1'
date_created: 2018-12-11T12:02:22Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2024-10-09T20:54:35Z
day: '01'
department:
- _id: HeEd
language:
- iso: eng
month: '01'
oa_version: None
page: 197 - 200
publication_status: published
publisher: TU Dortmund
publist_id: '3376'
quality_controlled: '1'
status: public
title: Persistent homology computation with a twist
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...