A novel partitioning method for block-structured adaptive meshes. (English) Zbl 1376.76049

Summary: We propose a novel partitioning method for block-structured adaptive meshes utilizing the meshless Lagrangian particle concept. With the observation that an optimum partitioning has high analogy to the relaxation of a multi-phase fluid to steady state, physically motivated model equations are developed to characterize the background mesh topology and are solved by multi-phase smoothed-particle hydrodynamics. In contrast to well established partitioning approaches, all optimization objectives are implicitly incorporated and achieved during the particle relaxation to stationary state. Distinct partitioning sub-domains are represented by colored particles and separated by a sharp interface with a surface tension model. In order to obtain the particle relaxation, special viscous and skin friction models, coupled with a tailored time integration algorithm are proposed. Numerical experiments show that the present method has several important properties: generation of approximately equal-sized partitions without dependence on the mesh-element type, optimized interface communication between distinct partitioning sub-domains, continuous domain decomposition which is physically localized and implicitly incremental. Therefore it is particularly suitable for load-balancing of high-performance CFD simulations.


76M28 Particle methods and lattice-gas methods
65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
65M75 Probabilistic methods, particle methods, etc. for initial value and initial-boundary value problems involving PDEs
Full Text: DOI


[1] Butz, D.; Gao, Y.; Kempf, A. M.; Chakraborty, N., Large eddy simulations of a turbulent premixed swirl flame using an algebraic scalar dissipation rate closure, Combust. Flame, 162, 9, 3180-3196, (2015)
[2] Han, L. H.; Hu, X. Y.; Adams, N. A., Adaptive multi-resolution method for compressible multi-phase flows with sharp interface model and pyramid data structure, J. Comput. Phys., 262, 131-152, (2014) · Zbl 1349.76338
[3] Ji, H.; Lien, F. S.; Yee, E., A new adaptive mesh refinement data structure with an application to detonation, J. Comput. Phys., 229, 8981-8993, (2010) · Zbl 1207.80023
[4] Boman, E.; Devine, K.; Heaphy, R.; Hendrickson, R.; Leung, V.; Vaughan, L. A.C., Zoltan: parallel partitioning, load balancing and data management services, 1-173, (2007), User’s Guide Version 3.0
[5] Hendrickson, B.; Devine, K., Dynamic load balancing in computational mechanics, Comput. Methods Appl. Mech. Eng., 184, 2C4, 485-500, (2000) · Zbl 0965.74080
[6] Kavouklis, C.; Kallinderis, Y., Parallel adaptation of general three-dimensional hybrid meshes, J. Comput. Phys., 229, 9, 3454-3473, (2010) · Zbl 1307.76057
[7] Karypis, G.; Kumar, V., Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, (1995)
[8] Berger, M.; Bokhari, S., A partitioning strategy for nonuniform problems on multiprocessors, IEEE Trans. Comput., 36, 570-580, (1987)
[9] Berger, M. J.; Oliger, J., Adaptive mesh refinement for hyperbolic partial differential equations, J. Comput. Phys., 53, 3, 484-512, (1984) · Zbl 0536.65071
[10] Butz, A. R., Space filling curves and mathematical programming, Inf. Control, 12, 314-330, (1968) · Zbl 0187.12702
[11] Sagan, H., Space-filling curves, (1994), Springer · Zbl 0806.01019
[12] Nivarti, G. V.; Salehi, M. M.; Bushe, W. K., A mesh partitioning algorithm for preserving spatial locality in arbitrary geometries, J. Comput. Phys., 281, 352-364, (2015) · Zbl 1352.65074
[13] Pothen, A.; Simon, H.; Liou, K., Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl., 11, 3, 430-452, (1990) · Zbl 0711.65034
[14] 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
[15] Barnard, S. T.; Simon, H. D., Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, Concurr., Pract. Exp., 6, 2, 101-117, (1994)
[16] Kernighan, B. W.; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J., 49, 2, 291-307, (1970) · Zbl 0333.05001
[17] Fiduccia, C. M.; Mattheyses, R. M., A linear-time heuristic for improving network partitions, (19th Conference on Design Automation, (1982), IEEE), 175-181
[18] Buluç, A.; Meyerhenke, H.; Safro, I.; Sanders, P.; Schulz, C., Recent advances in graph partitioning, CoRR
[19] Hendrickson, B.; Kolda, T. G., Graph partitioning models for parallel computing, Parallel Comput., 26, 12, 1519-1534, (2000) · Zbl 0948.68130
[20] Meyerhenke, H.; Monien, B.; Schamberger, S., Graph partitioning and disturbed diffusion, Parallel Comput., 35, 10-11, 544-569, (2009)
[21] Diekmann, R.; Preis, R.; Schlimbach, F.; Walshaw, C., Shape-optimized mesh partitioning and load balancing for parallel adaptive FEM, Parallel Comput., 26, 12, 1555-1581, (2000) · Zbl 0948.68076
[22] Pellegrini, F., A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries, (Euro-Par 2007 Parallel Processing, Lect. Notes Comput. Sci., vol. 4641, (2007)), 195-204
[23] Rama Mohan Rao, A., Parallel mesh-partitioning algorithms for generating shape optimised partitions using evolutionary computing, Adv. Eng. Softw., 40, 2, 141-157, (2009) · Zbl 1156.65067
[24] Catalyurek, U.; Aykanat, C., Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication, IEEE Trans. Parallel Distrib. Syst., 10, 7, 673-693, (1999)
[25] H. Meyerhenke, J. Gehweiler, On dynamic graph partitioning and graph clustering using diffusion, in: Dagstuhl Seminar Proceedings, 2010.
[26] Meyerhenke, H.; Monien, B.; Sauerwald, T., A new diffusion-based multilevel algorithm for computing graph partitions of very high quality, (IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2008, (2008)), 1-13
[27] Monaghan, J. J., Smoothed particle hydrodynamics, Rep. Prog. Phys., 68, 1703-1759, (2005)
[28] Andreev, K.; Raecke, H., Balanced graph partitioning, (Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, (2004)), 120-124
[29] Hu, X. Y.; Adams, N. A., A multi-phase SPH method for macroscopic and mesoscopic flows, J. Comput. Phys., 213, 844-861, (2006) · Zbl 1136.76419
[30] Yang, X. F.; Liu, M. B.; Peng, S. L., Smoothed particle hydrodynamics modeling of viscous liquid drop without tensile instability, Comput. Fluids, 92, 199-208, (2014) · Zbl 1391.76644
[31] Osting, B.; White, C. D.; Oudet, É., Minimal Dirichlet energy partitions for graphs, SIAM J. Sci. Comput., 36, 4, A1635-A1651, (2014) · Zbl 1302.05146
[32] Verlet, L., Computer experiments on classical fluids. I. thermodynamical properties of lennard-Jones molecules, Phys. Rev., 159, 98-103, (1967)
[33] Courant, R.; Friedrichs, K.; Lewy, H., Über die partiellen differenzengleichungen der mathematischen physik, Math. Ann., 100, 1, 32-74, (1928) · JFM 54.0486.01
[34] Diehl, S.; Rockefelle, G.; Fryer, C. L.; Riethmiller, D.; Statler, T. S., Generating optimal initial conditions for smooth particle hydrodynamics simulations
[35] Hockney, R. W.; Eastwood, J. W., Computer simulation using particles, (1998), Institute of Physics Publishing · Zbl 0662.76002
[36] L. Arge, M.D. Berg, H.J. Haverkort, K. Yi, The priority r-tree: a practically efficient and worst-case optimal r-tree, in: Proc. SIGMOD, Intl. Conf. Management of Data. · Zbl 1445.68060
[37] Contreras, G.; Martonosi, M., Characterizing and improving the performance of intel threading building blocks, (2008 IEEE International Symposium on Workload Characterization, IISWC2008, (2008)), 57-66
[38] Monaghan, J. J.; Kajtar, J. B., SPH particle boundary forces for arbitrary boundaries, Comput. Phys. Commun., 180, 1811-1820, (2009) · Zbl 1197.76104
[39] Ferrari, A.; Dumbser, M.; Toro, E. F.; Armanini, A., A new 3d parallel SPH scheme for free surface flows, Comput. Fluids, 38, 1203-1217, (2009) · Zbl 1242.76270
[40] Leroy, A.; Violeau, D.; Ferrand, M.; Kassiotis, C., Unified semi-analytical wall boundary conditions applied to 2-D incompressible SPH, J. Comput. Phys., 261, 106-129, (2014) · Zbl 1349.76706
[41] Dehnen, W.; Aly, H., Improving convergence in smoothed particle hydrodynamics simulations without pairing instability, Mon. Not. R. Astron. Soc., 425, 1068-1082, (2012)
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.