×

Multithread parallelization of LEPP-bisection algorithms. (English) Zbl 1241.65110

Summary: Longest edge (nested) algorithms for triangulation refinement in two dimensions are able to produce hierarchies of quality and nested irregular triangulations as needed both for adaptive finite element methods and for multigrid methods. They can be formulated in terms of the longest edge propagation path (LEPP) and terminal edge concepts, to refine the target triangles and some related neighbors. We discuss a parallel multithread algorithm, where every thread is in charge of refining a triangle \(t\) and its associated LEPP neighbors. The thread manages a changing LEPP\((t)\) (ordered set of increasing triangles) both to find a last longest (terminal) edge and to refine the pair of triangles sharing this edge. The process is repeated until triangle t is destroyed. We discuss the algorithm, related synchronization issues, and the properties inherited from the serial algorithm. We present an empirical study that shows that a reasonably efficient parallel method with good scalability was obtained.

MSC:

65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Adler, A., On the bisection method for triangles, Mathematics of Computation, 40, 571-574 (1983) · Zbl 0523.65033
[2] Antonopoulos, C.; Blagajevic, F.; Chernikov, A.; Chrisochoides, N.; Nikolopoulos, D., Algorithm software, and hardware optimizations for Delaunay mesh generation on simultaneous multithreaded architectures, Journal on Parallel and Distributed Computing, 69 (2009)
[3] Antonopoulos, C.; Blagajevic, F.; Chernikov, A.; Chrisochoides, N.; Nikolopoulos, D., A multigrain Delaunay mesh generation method for multicore SMT-based architectures, Journal of Parallel and Distributed Computing, 69, 7 (2009)
[4] Babuska, I.; Aziz, A. K., On the angle condition in the finite element method, SIAM Journal on Numerical Analysis, 13, 214-226 (1976) · Zbl 0324.65046
[5] Baker, T., Automatic mesh generation for complex three dimensional regions using a constrained Delaunay triangulation, Engineering with Computers, 5, 161-175 (1989)
[6] Baker, T. J., Triangulations, mesh generation and point placement strategies, (Caughey, D., Computing the Future (1994), John Wiley), 61-75
[7] Boissonnat, Jean-Daniel; Devillers, Olivier; Pion, Sylvain; Teillaud, Monique; Yvinec, Mariette, Triangulations in CGAL, Computational Geometry: Theory and Applications, 22, 5-19 (2002) · Zbl 1016.68138
[8] Borouchaki, H.; George, P. L., Aspects of 2-D Delaunay mesh generation, International Journal for Numerical Methods in Engineering, 40, 1957-1975 (1997) · Zbl 0884.65143
[9] Breshears, C., The Art of Concurrency: A Thread Monkeyʼs Guide to Writing Parallel Applications (2009), OʼReilly Media, Inc.
[10] J.G. Castaños, J.E. Savage, Pared: a framework for the adaptive solution of PDEs, in: 8th IEEE Symposium on High Performance Distributed Computing, 1999.; J.G. Castaños, J.E. Savage, Pared: a framework for the adaptive solution of PDEs, in: 8th IEEE Symposium on High Performance Distributed Computing, 1999.
[11] José G. Cataños, John E. Savage, Parallel refinement of unstructured meshes, in: Proc. IASTED Conference on Parallel and Distributed Computing and Systems (PDCSʼ99), Boston, 1999.; José G. Cataños, John E. Savage, Parallel refinement of unstructured meshes, in: Proc. IASTED Conference on Parallel and Distributed Computing and Systems (PDCSʼ99), Boston, 1999.
[12] Cataños, José G.; Savage, John E., Repartitioning unstructured adaptive meshes, (IPDPS (2000), IEEE Computer Society), 823-832
[13] Chernikov, A.; Chrisochoides, N., Algorithm 872: Parallel 2d constrained Delaunay mesh generation, ACM Transactions on Mathematical Software, 34, 1, 1-20 (2008) · Zbl 1291.65054
[14] Chernikov, A.; Chrisochoides, N., Generalized two-dimensional Delaunay mesh refinement, SIAM Journal on Scientific Computing, 31, 3387-3403 (2009) · Zbl 1200.65014
[15] Chew, L. P., Constrained Delaunay triangulations, Algorithmica, 4, 97-108 (1989) · Zbl 0664.68042
[16] George, P. L.; Hecht, F.; Saltel, E., Automatic mesh generator with specified boundary, Computer Methods in Applied Mechanics and Engineering, 92, 269-288 (1991) · Zbl 0756.65133
[17] Grama, A.; Gupta, A.; Karypis, G.; Kumar, V., Introduction to Parallel Computing (2003), Addison-Wesley
[18] Gutierrez, C.; Gutierrez, F.; Rivara, M. C., Complexity on the bisection method, Theoretical Computer Science, 382, 131-138 (2007) · Zbl 1127.68108
[19] Jones, M. T.; Plassmann, P. E., Computational results for parallel unstructured mesh computations, Computing Systems Engineering, 5, 297-309 (1994)
[20] Jones, Mark T.; Plassmann, Paul E., Parallel algorithms for adaptive mesh refinement, SIAM Journal on Scientific Computing, 18, 3, 686-708 (1997) · Zbl 0871.65100
[21] Jones, M. T.; Plassmann, E., Adaptive refinement of unstructured finite element meshes, Finite Elements in Analysis and Design, 25, 41-60 (1997) · Zbl 0897.65074
[22] Karp, A. H.; Flatt, H. P., Measuring parallel processor performance, Communications of the ACM, 33, 539-543 (1990)
[23] Lawson, C. L., Software for \(C^1\) surface interpolation, (Rice, John R., Mathematical Software III (1977), Academic Press), 161-194 · Zbl 0407.68033
[24] Liu, A.; Joe, B., Quality local refinement of tetrahedral meshes based on bisection, SIAM Journal on Scientific Computing, 16, 1269-1291 (1995) · Zbl 0841.65098
[25] Manber, U., Introduction to Algorithms. A Creative Approach (1991), Addison-Wesley
[26] Muthukrishnan, S. N.; Shiakolas, P. S.; Nambiar, R. V.; Lawrence, K. L., Simple algorithm for adaptative refinement of three-dimensional finite element tetrahedral meshes, AIAA Journal, 33, 928-932 (1995) · Zbl 0850.73272
[27] Nambiar, N.; Valera, R.; Lawrence, K. L.; Morgan, R. B.; Amil, D., An algorithm for adaptive refinement of triangular finite element meshes, International Journal for Numerical Methods in Engineering, 36, 499-509 (1993) · Zbl 0825.73842
[28] Rauber, T.; Runger, G., Parallel Programming for Multicore and Cluester Systems (2010), Springer · Zbl 1211.68073
[29] Rivara, M. C., Design and data structure for fully adaptive, multigrid finite-element software, ACM Transactions on Mathematical Software, 10, 242-264 (1984) · Zbl 0578.65112
[30] Rivara, M. C., Algorithms for refining triangular grids suitable for adaptive and multigrid techniques, International Journal for Numerical Methods in Engineering, 20, 745-756 (1984) · Zbl 0536.65085
[31] Rivara, M. C., A dynamic multigrid algorithm suitable for partial differential equations with singular solutions, (Contesse, L.; Correa, R.; Weintraub, A., Recent Advances in Systems Modelling and Optimization. Recent Advances in Systems Modelling and Optimization, Lecture Notes in Control and Information Sciences (1986), Springer-Verlag), 190-199
[32] Rivara, M. C., Adaptive finite element refinement and fully irregular and conforming triangulations, (Babuska, I.; Gago, J.; de A. Oliveira, E. R.; Zienkiewicz, O. C., Accuracy Estimates and Adaptive Refinements in Finite Element Computations (1986), John Wiley), 359-370, (Chapter 20)
[33] Rivara, M. C., Selective refinement/derefinement algorithms for sequences of nested triangulations, International Journal for Numerical Methods in Engineering, 28, 2889-2906 (1989) · Zbl 0729.65092
[34] Rivara, M. C., New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations, International Journal for Numerical Methods in Engineering, 40, 3313-3324 (1997) · Zbl 0980.65144
[35] Rivara, M. C.; Levin, C., A 3D refinement algorithm suitable for adaptive and multigrid techniques, Communications in Applied Numerical Methods, 8, 281-290 (1992) · Zbl 0755.65115
[36] Rivara, M. C., Lepp-bisection algorithms, applications and mathematical properties, Applied Numerical Mathematics, 59, 2218-2235 (2009) · Zbl 1167.65343
[37] Rivara, M. C.; Calderon, C., Lepp terminal centroid method for quality triangulation, Computer-Aided Design, 42, 58-66 (2010)
[38] Rivara, M. C.; Palma, M., New LEPP algorithms for quality polygon and volume triangulation: Implementation issues and practical behavior, (Cannan, A.; Saigal, Trends in Unstructured Mesh Generation. Trends in Unstructured Mesh Generation, AMD, vol. 220 (1997), ASME), 1-8
[39] Rivara, M. C.; Hitschfeld, N.; Simpson, R. B., Terminal edges Delaunay (small angle based) algorithm for the quality triangulation problem, Computer-Aided Design, 33, 263-277 (2001)
[40] Rivara, M. C.; Calderón, C.; Federov, A.; Chrisochoides, N., Parallel decoupled terminal-edge bisection method for 3D mesh generation, Engineering with Computers, 22, 536-544 (2006)
[41] Rosenberg, I. G.; Stenger, F., A lower bound on the angles of triangles constructed by bisecting the longest side, Mathematics of Computation, 29, 390-395 (1975) · Zbl 0302.65085
[42] Ruppert, J., A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, 18, 548-585 (1995) · Zbl 0828.68122
[43] Shephard, M. S.; Guerinoni, F.; Flaherty, J. E.; Ludwig, R. A.; Baehmann, P. L., Finite octree mesh generation for three-dimensional flow analysis, (Numerical Grid Generation in Computational Fluid Mechanics (1988), Pineridge Press), 709-718
[44] Shephard, M. S.; Flaherty, J. E.; Bottasso, C. L.; de Cougny, H. L.; Ozturan, C.; Simone, M. L., Parallel automatic adaptive analysis, Parallel Computing, 23, 9, 1327-1347 (1997) · Zbl 0894.68020
[45] Shewchuk, J. R., Delaunay refinement algorithms for triangular mesh generation, Computational Geometry: Theory and Applications, 22, 21-74 (2002) · Zbl 1016.68139
[46] Sibson, R., Locally equiangular triangulations, Computer Journal, 21, 1978, 243-245 (1978)
[47] Stynes, M., On faster convergence of the bisection method for certain triangles, Mathematics of Computation, 33, 1195-1202 (1979)
[48] Stynes, M., On faster convergence of the bisection method for all triangles, Mathematics of Computation, 35, 1195-1202 (1980) · Zbl 0463.65005
[49] Weiss, M. A., Data Structures and Algorithm Analysis in C++ (2006), Addison-Wesley
[50] Williams, R., Adaptive parallel meshes with complex geometry, (Arcilla, A. S.; Hauser, J.; Eiseman, P. R.; Thompson, J. F., Numerical Grid Generation in Computational Fluid Dynamics and Related Fields (1991), Elsevier Science Publishers), 201-213
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.