Sparse parallel Delaunay mesh refinement
Sparse parallel Delaunay mesh refinement
复制标题
稀疏并行 Delaunay 网格细化
DOI：
10.1145/1248377.1248435
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Todd Phillips
中科院分区：
文献类型：
--
作者：
Benoît Hudson;G. Miller;Todd Phillips
作者最近介绍了稀疏网格细化的技术，以产生第一个接近最优的顺序时间界O（n lg L/s+m）的输入在任何固定的尺寸与piecewiselinear约束（PLC）功能。本文将这项工作扩展到并行的情况下，细化相同的输入时间O（lg（L/s）lgm）的EREW PRAM上，同时保持工作界;在实践中，这意味着我们期望线性加速任何实际数量的处理器。这是最快的速度比以前已知的并行Delaunay网格细化算法在两个维度。这是第一个工作界限等于顺序情况的技术。在更高的维度，它是第一个可证明的快速并行技术的任何类型的质量网格细化与PLC输入。此外，该算法的实现非常简单，在实践中可能非常快。
The authors recently introduced the technique of sparse mesh refinement to produce the first near-optimal sequential time bounds of O(n lg L/s+m) for inputs in any fixed dimension with piecewiselinear constraining (PLC) features. This paper extends that work to the parallel case, refining the same inputs in time O(lg(L/s) lgm) on an EREW PRAM while maintaining the work bound; in practice, this means we expect linear speedup for any practical number of processors. This is faster than the best previously known parallel Delaunay mesh refinement algorithms in two dimensions. It is the first technique with work bounds equal to the sequential case. In higher dimension, it is the first provably fast parallel technique for any kind of quality mesh refinement with PLC inputs. Furthermore, the algorithm's implementation is straightforward enough that it is likely to be extremely fast in practice.