tachyon: Efficient Shared Memory Parallel Computation of Extremum Graphs

The extremum graph is a succinct representation of the Morse decomposition of a scalar field. It has increasingly become a useful data structure that supports topological feature-directed visualization of 2D/3D scalar fields, and enables dimensionality reduction together with exploratory analysis of high-dimensional scalar fields. Current methods that employ the extremum graph compute it either using a simple sequential algorithm for computing the Morse decomposition or by computing the more detailed Morse–Smale complex. Both approaches are typically limited to two and three-dimensional scalar fields. We describe a GPU–CPU hybrid parallel algorithm for computing the extremum graph of scalar fields in all dimensions. The proposed shared memory algorithm utilizes both fine-grained parallelism and task parallelism to achieve efficiency. An open source software library, tachyon , that implements the algorithm exhibits superior performance and good scaling behaviour.