Parallel Algorithms for Intersection Computation

This paper discusses parallel algorithms for computing intersections between pairs of meshes. We used parallel intersection algorithms to compute interpolation weights in coupled solvers which are part of multi-physics simulations. We present a parallel algorithm for computing intersections that has linear computational complexity. We analyze the computation and communication complexities of this algorithm, along with lower bounds for parallel intersection computation. The algorithm has low contention and can be executed on many-core CPUs or offloaded to GPUs. We present strong scaling results for this algorithm on a heterogeneous machine with multiple GPUs per node.