Massively Parallel Augmented Merge Tree Computation Based on the Bipartite Graph

Area of Science:

• Topological Data Analysis
• Scientific Visualization
• High-Performance Computing

Background:

• Merge trees are crucial for understanding data topology but are computationally expensive to construct, especially augmented merge trees.
• Existing methods face significant computational and memory overhead, limiting their scalability for large datasets.

Purpose of the Study:

• To present BiGMT, a novel, highly scalable parallel algorithm for efficient merge tree and augmented merge tree construction.
• To reduce the computational and memory footprint of merge tree algorithms.

Main Methods:

• BiGMT utilizes regions from Morse-Smale segmentation, exploiting boundary vertex characteristics and dynamic region merging.
• The algorithm represents the merge tree structure as a weighted bipartite graph, enabling fine-grained parallel task decomposition.
• Augmented merge trees are constructed using reverse binary lifting search and parallel connection mechanisms.

Main Results:

• BiGMT achieves significant reductions in traversal cost and memory consumption compared to existing methods.
• Experiments show substantial GPU acceleration, with speedups up to 23.95× over state-of-the-art algorithms like ExTreeM, PPP, and FTM-Tree.
• The algorithm demonstrates superior parallel efficiency and scalability on medium- to large-scale scalar field datasets.

Conclusions:

• BiGMT offers a highly efficient and scalable solution for constructing merge trees and augmented merge trees.
• The parallel approach significantly enhances performance, making complex topological analysis more accessible for large datasets.