Discrete Morse Theory Algorithms

Discrete Morse Theory (DMT) is the discrete version of Morse Theory and has been introduced by Robin Forman. Discrete Morse Theory provides a powerful tool for the analysis of topological spaces. The main focus of DMT, like its predecessor Morse theory, is based on finding critical points and constructing a simpler topological space which is homotopy equivalent to the original topological space. In this thesis, we will introduce discrete Morse function and explain how we can find it over a simplicial complex. We will explain how finding a discrete Morse function can be converted to a combinatorial problem which is called a discrete Morse matching. Then we will explain the algorithms for finding discrete Morse matchings over simplicial complexes. Here, we propose a parallel algorithm for discrete Morse matching computation. Then we show how to construct a Morse complex and compute its homology groups. In section 4.2, we propose an algorithm to compute homology groups based on parallel matching. Finally, we will see the results on some data sets. We will see the effect of parallelization on elapsed time of the algorithm for different simplicial complexes.