Massively Parallel Augmented Merge Tree Computation Based on the Bipartite Graph

Merge trees are fundamental topological descriptors with broad theoretical and practical significance, yet their computation, particularly for augmented merge trees, incurs substantial computational and memory overhead. We present BiGMT, a highly scalable parallel algorithm for merge tree construction based on regions of the Morse-Smale segmentation. By exploiting boundary vertex characteristics and the dynamic merging of these regions, BiGMT preserves the essential topology of d-dimensional manifolds and represents the structure as a weighted bipartite graph. This formulation decomposes merge tree construction into fine-grained parallel tasks, significantly reducing traversal cost and memory consumption. Furthermore, BiGMT efficiently constructs augmented merge trees using reverse binary lifting search and parallel connection mechanisms, substantially improving augmentation performance. Extensive experiments on medium- to large-scale scalar field datasets demonstrate substantial GPU acceleration. BiGMT consistently outperforms ExTreeM, PPP, and FTM-Tree on RTX4090 and H200, achieving speedups of up to 23.95× and demonstrating superior parallel efficiency and scalability.