A physics-motivated centroidal Voronoi particle domain decomposition method. (English) Zbl 1380.65263

Summary: In this paper, we propose a novel domain decomposition method for large-scale simulations in continuum mechanics by merging the concepts of centroidal Voronoi tessellation (CVT) and Voronoi particle dynamics (VP). The CVT is introduced to achieve a high-level compactness of the partitioning subdomains by the Lloyd algorithm which monotonically decreases the CVT energy. The number of computational elements between neighboring partitioning subdomains, which scales the communication effort for parallel simulations, is optimized implicitly as the generated partitioning subdomains are convex and simply connected with small aspect-ratios. Moreover, Voronoi particle dynamics employing physical analogy with a tailored equation of state is developed, which relaxes the particle system towards the target partition with good load balance. Since the equilibrium is computed by an iterative approach, the partitioning subdomains exhibit locality and the incremental property. Numerical experiments reveal that the proposed centroidal Voronoi particle (CVP) based algorithm produces high-quality partitioning with high efficiency, independently of computational-element types. Thus, it can be used for a wide range of applications in computational science and engineering.


65M60 Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs
76M28 Particle methods and lattice-gas methods


adsimp; Scotch
Full Text: DOI


[1] Keyes, D. E., (Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations, vol. 55, (1992), SIAM)
[2] Nepomnyaschikh, S., Domain decomposition methods, Radon Series Comp. Appl. Math., vol. 1, 89-160, (2007) · Zbl 1132.65111
[3] Berger, M.; Bokhari, S., A partitioning strategy for nonuniform problems on multiprocessors, IEEE Trans. Comput., 36, 570-580, (1987)
[4] Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20, 359-392, (1999) · Zbl 0915.68129
[5] Karypis, G.; V, K., A software package for partitioning unstructured graph, partitioning meshes, and computing fill-reducing orderings of sparse matrices. User’s guide version 4.0 and version 5.0 pre2, (1998), pp. 1-44
[6] Pellegrini, F., Scotch and libscotch 5.1. User’s guide, (2008), pp. 1-127
[7] Du, Q.; Wang, X., Centroidal Voronoi tessellation based algorithms for vector fields visualization and segmentation, (Proceedings of the Conference on Visualization’04, (2004), IEEE Computer Society), 43-50
[8] Bowyer, A., Computing Dirichlet tessellations, Comput. J., 24, 2, 162-166, (1981)
[9] Okabe, A.; Boots, B.; Sugihara, K.; Chiu, S. N., Spatial tessellations: concepts and applications of Voronoi diagrams, vol. 501, (2009), John Wiley & Sons
[10] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev., 41, 4, 637-676, (1999) · Zbl 0983.65021
[11] Du, Q.; Gunzburger, M., Grid generation and optimization based on centroidal Voronoi tessellations, Appl. Math. Comput., 133, 2, 591-607, (2002) · Zbl 1024.65118
[12] Valette, S.; Chassery, J.-M.; Prost, R., Generic remeshing of 3d triangular meshes with metric-dependent discrete Voronoi diagrams, IEEE Trans. Vis. Comput. Graph., 14, 2, 369-381, (2008)
[13] Du, Q.; Wang, D., Anisotropic centroidal Voronoi tessellations and their applications, SIAM J. Sci. Comput., 26, 3, 737-761, (2005) · Zbl 1121.65306
[14] Lloyd, S. P., Least squares quantization in pcm, IEEE Trans. Inf. Theory, 28, 2, 129-137, (1982) · Zbl 0504.94015
[15] MacQueen, J., Some methods for classification and analysis of multivariate observations, (Oakland, CA, USA, Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, (1967)), 281-297 · Zbl 0214.46201
[16] Ju, L.; Du, Q.; Gunzburger, M., Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations, Parallel Comput., 28, 10, 1477-1500, (2002) · Zbl 1014.68202
[17] Du, Q.; Emelianenko, M., Acceleration schemes for computing centroidal Voronoi tessellations, Numer. Linear Algebra Appl., 13, 2-3, 173-192, (2006) · Zbl 1174.05323
[18] Liu, Y.; Wang, W.; Lévy, B.; Sun, F.; Yan, D.-M.; Lu, L.; Yang, C., On centroidal Voronoi tessellation—energy smoothness and fast computation, ACM Trans. Graph., 28, 4, 101, (2009)
[19] Du, Q.; Wang, D., The optimal centroidal Voronoi tessellations and the Gersho’s conjecture in the three-dimensional space, Comput. Math. Appl., 49, 9, 1355-1373, (2005) · Zbl 1077.65019
[20] Bo, W.; Shashkov, M., Adaptive reconnection-based arbitrary Lagrangian Eulerian method, J. Comput. Phys., 299, 902-939, (2015) · Zbl 1352.65602
[21] Du, Q.; Gunzburger, M.; Ju, L., Advances in studies and applications of centroidal Voronoi tessellations, Numer. Math., 3, 2, 119-142, (2010) · Zbl 1224.52032
[22] Genz, A.; Cools, R., An adaptive numerical cubature algorithm for simplices, ACM Trans. Math. Softw., 29, 3, 297-308, (2003) · Zbl 1072.65032
[23] Du, Q.; Emelianenko, M.; Ju, L., Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations, SIAM J. Numer. Anal., 44, 1, 102-119, (2006) · Zbl 1115.65017
[24] Ostrovsky, R.; Rabani, Y.; Schulman, L. J.; Swamy, C., The effectiveness of Lloyd-type methods for the k-means problem, (47th Annual IEEE Symposium on Foundations of Computer Science, 2006. FOCS’06, (2006), IEEE), 165-176
[25] Heß, S.; Springel, V., Particle hydrodynamics with tessellation techniques, Mon. Not. R. Astron. Soc., 406, 4, 2289-2311, (2010)
[26] Espanol, P., Fluid particle model, Phys. Rev. E, 57, 3, 2930, (1998)
[27] Hendrickson, B.; Kolda, T. G., Graph partitioning models for parallel computing, Parallel Comput., 26, 12, 1519-1534, (2000) · Zbl 0948.68130
[28] Meyerhenke, H.; Monien, B.; Schamberger, S., Graph partitioning and disturbed diffusion, Parallel Comput., 35, 10, 544-569, (2009)
[29] Yu, W.; Li, X., A geometry-aware data partitioning algorithm for parallel quad mesh generation on large-scale 2d regions, Proc. Eng., 124, 44-56, (2015)
[30] Meyerhenke, H.; Monien, B.; Schamberger, S., Graph partitioning and disturbed diffusion, Parallel Comput., 35, 10-11, 544-569, (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.