Discrete Morse Theoretic Algorithms for Computing Homology of Complexes and Maps

Shaun Harker, Konstantin Mischaikow, Marian Mrozek, Vidit Nanda

Research output: Contribution to journalArticlepeer-review

48 Scopus citations


We provide explicit and efficient reduction algorithms based on discrete Morse theory to simplify homology computation for a very general class of complexes. A set-valued map of top-dimensional cells between such complexes is a natural discrete approximation of an underlying (and possibly unknown) continuous function, especially when the evaluation of that function is subject to measurement errors. We introduce a new Morse theoretic preprocessing framework for deriving chain maps from such set-valued maps, and hence provide an effective scheme for computing the morphism induced on homology by the approximated continuous function.

Original languageEnglish (US)
Pages (from-to)151-184
Number of pages34
JournalFoundations of Computational Mathematics
Issue number1
StatePublished - Feb 2014

All Science Journal Classification (ASJC) codes

  • Analysis
  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Computational homology
  • Discrete Morse theory


Dive into the research topics of 'Discrete Morse Theoretic Algorithms for Computing Homology of Complexes and Maps'. Together they form a unique fingerprint.

Cite this