A GPU Parallel Algorithm for Computing Morse-Smale Complexes.

Area of Science:

• Computational Topology
• Scientific Visualization
• Applied Mathematics

Background:

• The Morse-Smale complex is crucial for analyzing scalar function gradient flows and multi-scale data.
• Existing parallel algorithms face challenges, particularly with saddle critical point connections.
• Efficient computation of 3D Morse-Smale complexes remains an active research area.

Purpose of the Study:

• To develop a fine-grained parallel algorithm for computing the 3D Morse-Smale complex.
• To implement a GPU-based solution (gmsc) for accelerated computation.
• To introduce a CPU-based parallel algorithm for Morse-Smale complex simplification.

Main Methods:

• A novel algorithm transforms saddle-saddle reachability into vector operations.
• Path computation between saddles is achieved through matrix operations.
• A GPU implementation (gmsc) and a CPU data-parallel simplification algorithm are presented.

Main Results:

• The gmsc implementation achieves significant speedups: up to 8.6x over pyms3d and 6x over TTK.
• Experimental analysis details the runtime performance contribution of different algorithmic steps.
• The CPU-based algorithm effectively simplifies the Morse-Smale complex via critical point pair cancellation.

Conclusions:

• The proposed fine-grained parallel algorithm and GPU implementation efficiently compute the 3D Morse-Smale complex.
• The approach addresses critical challenges in parallelizing saddle connections, enhancing computational speed.
• The study provides a robust framework for topological analysis and visualization of complex scientific data.