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

摘要

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