Previous |  Up |  Next


grid generation; space filling curve; load balancing
Numerical experiments in J. Maubach: Local bisection refinement and optimal order algebraic multilevel preconditioners, PRISM-97 conference Proceedings, 1977, 121–136 indicated that the refinement with the use of local bisections presented in J. Maubach: Local bisection refinement for $n$-simplicial grids generated by reflections, SIAM J. Sci. Comput. 16 (1995), 210–227 leads to highly locally refined computational 2-meshes which can be very efficiently load-balanced with the use of a space-filling curve. This paper introduces the construction of this curve which can be produced at almost no costs, proofs that all its properties are invariant under local bisection, and comments on the 3-dimensional case. With the use of a space-filling curve (which passes through all triangular elements), load balancing over several processors is trivial: The load can be distributed over $N$ processors by cutting the curve into $N$ almost equilength parts. Each processor then operates on the triangles which are passed by its part of the curve.
[1] E.  Bänsch: Local mesh refinement in 2 and 3  dimensions. IMPACT Comput. Sci. Eng. 3 (1991), 181–191. DOI 10.1016/0899-8248(91)90006-G | MR 1141298
[2] G. H.  Golub, C. F.  Van Loan: Matrix Computations, 2nd edition. The Johns Hopkins University Press, Baltimore, 1989. MR 1002570
[3] B.  Joe, A.  Liu: On the shape of tetrahedra from bisection. Math. Comput. 63 (1994), 141–154. DOI 10.1090/S0025-5718-1994-1240660-4 | MR 1240660
[4] I.  Kossaczky: A recursive approach to local mesh refinement in two and three dimensions. J.  Comput. App. Math. 55 (1994), 275–288. DOI 10.1016/0377-0427(94)90034-5 | MR 1329875 | Zbl 0823.65119
[5] W. J.  Layton, J. M.  Maubach, and P. J.  Rabier: Robustness of an elementwise parallel finite element method for convection-diffusion problems. SIAM J.  Sci. Comput. 19 (1998), 1870–1891. DOI 10.1137/S1064827595293545 | MR 1638068
[6] W.  Layton, J. M.  Maubach, and P.  Rabier: Parallel algorithms for maximal monotone operators of local type. Numer. Math. 71 (1995), 29–58. DOI 10.1007/s002110050135 | MR 1339731
[7] J.  Maubach: Local bisection refinement for $n$-simplicial grids generated by reflections. SIAM J.  Sci. Comput. 16 (1995), 210–227. DOI 10.1137/0916014 | MR 1311687
[8] J.  Maubach: The efficient location of simplicial neighbors for locally refined $n$-simplicial grids. In: Proceedings of the 5th  International Meshing Roundtable, Pittsburgh, October 1996, 1996, pp. 137–153.
[9] J.  Maubach: Iterative Methods for Non-Linear Partial Differential Equations. CWI, Amsterdam, 1994. MR 1354839 | Zbl 0820.65022
[10] J.  Maubach: Local bisection refinement and optimal order algebraic multilevel preconditioners. In: PRISM-97 conference Proceedings, O. Axelsson et al. (eds.), University of Nijmegen, 1997, pp. 121–136.
[11] W. F.  Mitchell: Optimal multilevel iterative methods for adaptive grids. SIAM J.  Sci. Stat. Comput. 13 (1992), 146–167. DOI 10.1137/0913009 | MR 1145181 | Zbl 0746.65087
[12] A.  Mukherjee: An adaptive finite element code for elliptic boundary value problems in three dimensions with applications in numerical relativity. PhD. Thesis, Penn State University, 1996.
[13] A. Plaza, J. P.  Suárez, M. A.  Padrón, S. Falcón, and D.  Amieiro: Mesh quality improvement and other properties in the four-triangles longest-edge partition. Comput. Aided Geom. Des. 21 (2004), 353–369. DOI 10.1016/j.cagd.2004.01.001 | MR 2046913
[14] M. C. Rivara, C.  Levin: A 3-D  refinement algorithm suitable for adaptive and multi-grid techniques. Commun. Appl. Numer. Methods 8 (1992), 281–290. DOI 10.1002/cnm.1630080502
Partner of
EuDML logo