Recent advances in parallel advancing front grid generation. (English) Zbl 1349.65667

Summary: The quest for scalable, parallel advancing front grid generation techniques now spans more than two decades. A recent innovation has been the use of a so-called domaindefining grid, which has led to a dramatic increase in robustness and speed. The domain-defining grid (DDG) has the same fine surface triangulation as the final mesh desired, but a much coarser interior mesh. The DDG renders the domain to be gridded uniquely defined and allows for a well balanced work distribution among the processors during all stages of grid generation and improvement. In this way, most of the shortcomings of previous techniques are overcome. Timings show that the approach is scalable and able to produce large grids of high quality in a modest amount of clocktime. These recent advances in parallel grid generation have enabled a completely scalable simulation pipeline (grid generation, solvers, post-processing), opening the way for truly large-scale computations using unstructured, body-fitted grids.


65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
Full Text: DOI


[1] Alleaume A, Francez L, Loriot M, Maman, N (2007) Large outofCore tetrahedral meshing. In: Proceedings of the 16th international meshing roundtable, Sandia National Laboratory, Oct. 15-17 · Zbl 1134.65312
[2] Andrae, H; Ivanov, E; Gluchshenko, O; Kudryavtsev, A, Automatic parallel generation of tetrahedral grids by using a domain decomposition approach, J Comput Math Math Phys, 48, 1448-1457, (2008) · Zbl 1199.65397
[3] Baker, TJ, Developments and trends in three-dimensional mesh generation, Appl Numer Math, 5, 275-304, (1989) · Zbl 0675.65120
[4] Baum JD, Luo H, Löhner R (1993) Numerical simulation of a blast inside a Boeing 747; AIAA-93-3091
[5] Baum JD, Luo H, Löhner R (1995) Numerical simulation of blast in the World Trade Center; AIAA-95-0085
[6] Baum JD, Luo H, Löhner R, Yang C, Pelessone D, Charman C (1996) A coupled fluid/structure modeling of shock interaction with a truck; AIAA-96-0795 · Zbl 0761.76084
[7] Baum JD, Luo H, Löhner R (1998) The numerical simulation of strongly unsteady flows with hundreds of moving bodies; AIAA-98-0788 · Zbl 0764.76037
[8] Baum JD, Luo H, Mestreau E, Löhner R, Pelessone D, Charman C (1999) A coupled CFD/CSD methodology for modeling weapon detonation and fragmentation; AIAA-99-0794 · Zbl 0665.76073
[9] Blelloch, GE; Hardwick, JC; Miller, GL; Talmor, D, Design and implementation of a practical parallel Delaunay algorithm, Algorithmica, 24, 243-269, (1999) · Zbl 0941.68816
[10] Chew LP, Chrisochoides N, Sukup F (1997) Parallel constrained Delaunay meshing; In: Proceedings 1997 workshop on trends in unstructured mesh generation, June · Zbl 0631.76085
[11] Chrisochoides N, Nave D (1999) Simultaneous mesh generation and partitioning for Delaunay meshes; In: Proceedings 8th international meshing roundtable, South Lake Tahoe, October pp. 55-66 · Zbl 0993.65029
[12] Chrisochoides, N; Nave, D, Parallel Delaunay mesh generation kernel, Int J Numer Methods Eng, 58, 161-176, (2003) · Zbl 1035.65018
[13] Chrisochoides, N; Bruaset, AM (ed.); Tveito, A (ed.), Parallel mesh generation, (2005), Norfolk
[14] Cougny, HL; Shephard, MS; Ozturan, C, Parallel three-dimensional mesh generation, Comput Syst Eng, 5, 311-323, (1994)
[15] de Cougny HL, Shephard MS, Ozturan C (1995) Parallel three-dimensional mesh generation on distributed memory MIMD computers. Tech. Rep. SCOREC Rep. # 7, Rensselaer Polytechnic Institute
[16] Cougny, H; Shephard, M, Parallel volume meshing using face removals and hierarchical repartitioning, Comput Methods Appl Mech Eng, 174, 275-298, (1999) · Zbl 0963.76073
[17] Darve E, Löhner R (1997) Advanced structured-unstructured solver for electromagnetic scattering from multimaterial objects. AIAA-97-0863 · Zbl 0960.76075
[18] Freitag, LA; Gooch, C-Ollivier, Tetrahedral mesh improvement using swapping and smoothing, Int J Numer Methods Eng, 40, 3979-4002, (1997) · Zbl 0897.65075
[19] Frykestig J (1994) Advancing front mesh generation techniques with application to the finite element method; Pub. 94:10, Chalmers University of Technology; Göteborg, Sweden · Zbl 0862.65051
[20] Galtier J, George PL (1997) Prepartitioning as a way to mesh subdomains in parallel; In: Special Symposium on trends in unstructured mesh generation pp 107-122, ASME/ASCE/SES · Zbl 0825.76680
[21] George, PL; Hecht, F; Saltel, E, Automatic mesh generator with specified boundary, Comp Methods Appl Mech Eng, 92, 269-288, (1991) · Zbl 0756.65133
[22] George PL (1999) Tet meshing: construction, optimization and adaptation. In: Proceedings of the 8th international meshing roundtable, South Lake Tahoe, October · Zbl 0668.76035
[23] Hanxleden, R; Scott, LR, Load balancing on message passing architectures, J Parallel Distrib Comput, 13, 312-324, (1991)
[24] Hassan O, Bayne LB, Morgan K and Weatherill N P (1998) An adaptive unstructured mesh method for transient flows involving moving boundaries; pp. 662-674 in Computational fluid dynamics ’98 ( Papailiou KD, Tsahalis D, Périaux J and Knörzer D eds. ) Wiley · Zbl 0822.65097
[25] Ito, Y; Shih, AM; Erukala, AK; Soni, BK; Chernikov, A; Chrisochoides, N; Nakahashi, K, Parallel unstructured mesh generation by an advancing front method, J Math Comput Simul, 75, 200-209, (2007) · Zbl 1124.65025
[26] Ivanov, EG; Andrae, H; Kudryavtsev, AN, Domain decomposition approach for automatic parallel generation of tetrahedral grids, Int Math J Comput Methods Appl Math, 6, 178-193, (2006) · Zbl 1094.65017
[27] Jin, H; Tanner, RI, Generation of unstructured tetrahedral meshes by the advancing front technique, Int J Numer Methods Eng, 36, 1805-1823, (1993) · Zbl 0771.76057
[28] Jou W (1998) Comments on the feasibility of LES for commercial airplane wings. AIAA-98-2801
[29] Kadow C, Walkington N (2003) Design of a projection-based parallel Delaunay mesh generation and refinement algorithm. In: Proceedings of the fourth symposium on trends in unstructured mesh generation
[30] Kamoulakos A, Chen V, Mestreau E, Löhner R (1996) Finite element modelling of fluid/ structure interaction in explosively loaded aircraft fuselage panels using PAMSHOCK/ PAMFLOW coupling. Conference on spacecraft structures, materials and mechanical testing, Noordwijk, The Netherlands, March · Zbl 0963.76073
[31] Karypis, G; Kumar, V, A parallel algorithm for multilevel graph partitioning and sparse matrix ordering, J Parallel Distrib Comput, 48, 71-85, (1998)
[32] Karypis, G; Kumar, V, Parallel multilevel k-way partitioning scheme for irregular graphs, SIAM Rev, 41, 278-300, (1999) · Zbl 0918.68073
[33] Larwood, BG; Weatherill, NP; Hassan, O; Morgan, K, Domain decomposition approach for parallel unstructured mesh generation, Int J Numer Methods Eng, 58, 177-188, (2003) · Zbl 1032.76667
[34] Liu, J; Kailasanath, K; Ramamurti, R; Munday, D; Gutmark, E; Löhner, R, Large-eddy simulations of a supersonic jet and its near-field acoustic properties, AIAA J, 47, 1849-1864, (2009) · Zbl 1204.42021
[35] Löhner R (1988) Some useful data structures for the generation of unstructured grids. Comm Appl Numer Methods 4: 123-135 · Zbl 0643.65075
[36] Löhner, R; Parikh, P, Three-dimensional grid generation by the advancing front method, Int J Numer Methods Fluids, 8, 1135-1149, (1988) · Zbl 0668.76035
[37] Löhner, R, Three-dimensional fluid-structure interaction using a finite element solver and adaptive remeshing, Comput Syst Eng, 1, 257-272, (1990)
[38] Löhner, R; Camberos, J; Merriam, M, Parallel unstructured grid generation, Comput Methods Appl Mech Eng, 95, 343-357, (1992) · Zbl 0825.76680
[39] Löhner, R; Ramamurti, R, A load balancing algorithm for unstructured grids, Comput Fluid Dyn, 5, 39-58, (1995)
[40] Löhner, R, Extensions and improvements of the advancing front grid generation technique, Comm Numer Methods Eng, 12, 683-702, (1996) · Zbl 0862.65051
[41] Löhner, R, Regridding surface triangulations, J Comput Phys, 126, 1-10, (1996) · Zbl 0862.65010
[42] Löhner, R, Progress in grid generation via the advancing front technique, Eng Comput, 12, 186-210, (1996)
[43] Löhner R, Yang C, Cebral J, Baum JD, Luo H, Pelessone D, Charman C (1998) Fluid-structure-thermal interaction using a loose coupling algorithm and adaptive unstructured grids; AIAA-98-2419 · Zbl 0875.73165
[44] Löhner, R, Renumbering strategies for unstructured-grid solvers operating on shared- memory, cache-based parallel machines, Comput Methods Appl Mech Eng, 163, 95-109, (1998) · Zbl 0960.76075
[45] Löhner R, Yang C and Oñate E ( 1998) Viscous free surface hydrodynamics using unstructured grids; In: Proceedings 22nd symposium naval hydrodynamics, Washington DC, August · Zbl 1035.65018
[46] Löhner, R, A parallel advancing front grid generation scheme, Int J Numer Methods Eng, 51, 663-678, (2001) · Zbl 1012.76077
[47] Löhner R (2008) Applied CFD techniques, 2nd edn. Wiley, Chichester
[48] Löhner, R; Cebral, JR; Camelli, FF; Appanaboyina, S; Baum, JD; Mestreau, EL; Soto, O, Adaptive embedded and immersed unstructured grid techniques, Comput Methods Appl Mech Eng, 197, 2173-2197, (2008) · Zbl 1158.76408
[49] Marcum, DL; Weatherill, NP, Unstructured grid generation using iterative point insertion and local reconnection, AIAA J, 33, 1619-1625, (1995) · Zbl 0851.76041
[50] Mavriplis DJ and Pirzadeh S (1999) Large-scale parallel unstructured mesh computations for 3-D high-lift analysis; ICASE Rep. 99-9 · Zbl 0862.65051
[51] Mestreau E, Löhner R and Aita S (1993) TGV tunnel-entry simulations using a finite element code with automatic remeshing; AIAA-93-0890
[52] Mestreau E and Löhner R (1996) Airbag simulation using fluid/structure coupling; AIAA-96-0798
[53] Morgan K, Brookes PJ, Hassan O and Weatherill NP (1997) Parallel processing for the simulation of problems involving scattering of electro-magnetic waves; In: Proceedings Symposium advances in computational mechanics (Demkowicz L and Reddy JN eds) · Zbl 0825.76680
[54] Okusanya T, Peraire J (1996) Parallel unstructured mesh generation. In: Proceedings 5th international conference numerical grid generation in CFD and related fields, Mississippi, April
[55] Okusanya T, Peraire J (1997) 3-D Parallel unstructured mesh generation. In: Proceedings of the joint ASME/ASCE/SES summer meeting
[56] Peraire, J; Vahdati, M; Morgan, K; Zienkiewicz, OC, Adaptive remeshing for compressible flow computations, J Comput Phys, 72, 449-466, (1987) · Zbl 0631.76085
[57] Peraire, J; Peiro, J; Formaggia, L; Morgan, K; Zienkiewicz, OC, Finite element Euler calculations in three dimensions, Int J Numer Methods Eng, 26, 2135-2159, (1988) · Zbl 0665.76073
[58] Peraire J, Morgan K, Peiro J (1990) Unstructured finite element mesh generation and adaptive procedures for CFD; AGARD-CP-464, 18
[59] Peraire, J; Morgan, K; Peiro, J, Adaptive remeshing in 3-D, J Comput Phys, 103, 269-285, (1992) · Zbl 0764.76037
[60] Pirzadeh SZ, Zagaris G (2008) Domain decomposition by the advancing-partition method for parallel unstructured grid generation. NASA/TM-2008-215350, L-19508 · Zbl 1257.76057
[61] Said R, Weatherill NP, Morgan K, Verhoeven NA (1999) Distributed parallel Delaunay mesh generation. Comput Methods Appl Mech 177:109-125 · Zbl 0997.65137
[62] Shostko, A; Löhner, R, Three-dimensional parallel unstructured grid generation, Int J Numer Methods Eng, 38, 905-925, (1995) · Zbl 0822.65097
[63] Tilch, R; Tabbal, A; Zhu, M; Decker, F; Löhner, R, Combination of body-fitted and embedded grids for external vehicle aerodynamics, Eng Comput, 25, 28-41, (2008) · Zbl 1257.76057
[64] Tremel, U; Sorensen, KA; Hitzel, S; Rieger, H; Hassan, O; Weatherill, NP, Parallel remeshing of unstructured volume grids for CFD applications, Int J Numer Methods Fluids, 53, 1361-1379, (2006) · Zbl 1109.76051
[65] Vidwans A, Kallinderis Y and Venkatakrishnan V (1993) A parallel load balancing algorithm for 3-D adaptive unstructured grids; AIAA-93-3313-CP · Zbl 0800.76368
[66] Williams D (1990) Performance of dynamic load balancing algorithms for unstructured grid calculations. CalTech Report C3P913
[67] Weatherill, NP, Delaunay triangulation in computational fluid dynamics, Comput Math Appl, 24, 129-150, (1992) · Zbl 0761.76084
[68] Weatherill, NP; Hassan, O, Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints, Int J Numer Methods Eng, 37, 2005-2039, (1994) · Zbl 0806.76073
[69] Yoshimura S, Nitta H, Yagawa G, Akiba H (1998) Parallel automatic mesh generation method of ten-million nodes problem using fuzzy knowledge processing and computational geometry. In: Proceedings of the 4th World CongComp. Mech. Buenos Aires, Argentina, July
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.