极区计算对全球数值预报模式设计的重要性主要体现在2个方面:模式动力框架中的极区处理和极区并行数据划分带来的并行负载不平衡问题.其中后者是全球数值预报模式大规模并行计算的性能瓶颈,对此提出一种新的基于加权等积的球面数据划分算法.该算法以球带数目和权函数为参数,将南北两极分别划分到单独的子区域,形成极点通区,使从极点到赤道方向每个纬度对应的子区域数目逐渐增多,灵活地实现球面网格的高质量划分.从理论上分析该算法的划分质量后,以基于球谐谱的浅水波模式PSTSWM为实验平台,验证了提出的划分算法具有很好的并行划分性能以及可扩展性.结合我国自主设计的GRAPES全球模式,展望了该算法的应用前景.%Hyperplane-cover problem is a fundamental NP-hard problem in computational geometry, which has many applications in practice. For the computational hardness of the NP-hard problems, some traditional approaches have been proposed for solving these NP-hard problems. But each of them has its own limitations, and none of them can satisfy all the application requirements in practice. Recently, a new approach dealing with NP-hard problems, called parameterized computation, has been developed, which has been effectively used in solving many hard problems. In this paper, based on the further structure analysis of the line-cover problem (a special case of hyperplane-cover problem), a deterministic parameterized algorithm with running time O(k3(0. 736k)k+n logk) is proposed for the problem using depth-bounded search tree method, which significantly improves the previous best result O((k/2. 2)2++n logk). The improvement is due to taking the advantages of the relationship between points and lines, and due to the precise algorithm's running time analysis. Moreover, based on the generalization of the algorithm solving the line-cover problem in higher space, a deterministic parameterized algorithm for the hyperplane-cover problem with running time O(dkd+1). (dk)!/((d)kk!)+nd+1) is given, which greatly improves the previous best result O(kd(k+1) + nd+1). In particular, the algorithms proposed can be used to solve many other covering problems, such as covering points with spheres, covering points with polynomials, covering by sets with intersection at most d, etc.
展开▼
