面向结构网格自适应并行计算的矩形区域求差集快速算法

结构网格自适应程序需要使用矩形区域求差集算法计算网格层间数据依赖关系和网格层嵌套关系.原有的矩形区域求差集算法时间复杂度较高，成为该类应用大规模并行计算可扩展性能瓶颈.本文利用分而治之的方法，构造近似线性时间复杂度的矩形区域求差集快速算法，并利用区域分解实现该算法的并行计算.分别针对规则矩形区域和多层自适应网格的非规则矩形区域求差集问题，验证该算法的效率.结果表明，该算法具有近似线性计算复杂度，对于大规模计算问题，加速效果显著.

A Fast Box Set Subtraction Algorithm for Parallel Structured Adaptive Mesh Refinement Applications

Box set subtraction is widely used in SAMR to compute data dependency and nested restriction. Traditional box set subtraction algorithms suffer from high time complexity, which often dominates execution time for large scale SAMR simulations. In this paper, a divide and conquer box set subtraction algorithm with linear time complexity was proposed, and enhanced by domain decomposition parallelization. Experiment results on regular box set and irregular box set of SAMR application verify linear time complexity property. And for large scale problems, our algorithm shows great improvement on computing time.