CUR - The Council on Undergraduate Research

Using Hasse Diagrams to Compute a Gradient Vector Field

Dr. Brittany Fasy, Ben Holmgren, Brad McCoy, and Dr. David Millman, Department of Computer Science, Montana State University, Culbertson Hall, 100, Bozeman, MT 59717

In computational geometry and topology, simplicial complexes are widely used structures  that model abstract  spaces. A simplicial  complex is a set of n-dimensional generalizations of triangles, called simplices.  Discrete Morse functions assign real numbers to each simplex in a simplicial complex.   One of the goals of Discrete Morse Theory is to generate gradient vector fields along the mappings of a function on a simplicial complex.  These gradient vector fields use vectors on a simplicial complex to display how function values change throughout the complex.  As a result, gradient vector fields can be thought of as indicating the “flow” of a simplicial complex.  To add intuition, we can imagine a mountain range as a simplicial complex, with a corresponding Morse function acting as a map to different heights in that mountain range.  That complex’s gradient vector field tells us where water would flow on that mountain range if we were to drop a bucket of water at any point.  Constructing gradient vector fields is also extremely useful when studying the topology of a simplicial complex.  However, we hypothesize that prevailing algorithms generate gradient vector fields with doubly exponential time complexity.  We are proposing new algorithms that can compute  gradient vector  fields with improved  time complexity. To do  so, we have  utilized  Hasse Diagrams,  a data structure  that is convenient  for storing a simplicial complex.  Our algorithms make use of memoization techniques in a  Hasse  diagram  in order  to limit repetitive  recursive calls prevalent  in prior algorithms.  Lastly, we are in the process of providing a thorough analysis of the time complexity of our algorithms alongside an analysis of current algorithms. In  doing  so, we  expect to  find novel contributions  in understanding the time complexity of gradient vector field computation, alongside our addition of new algorithms to do so.

Additional Abstract Information