Space-filling curves for 2-simplicial meshes created with bisections and reflections

Joseph M. Maubach

Applications of Mathematics (2005)

  • Volume: 50, Issue: 3, page 309-321
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Maubach, Joseph M.. "Space-filling curves for 2-simplicial meshes created with bisections and reflections." Applications of Mathematics 50.3 (2005): 309-321. <http://eudml.org/doc/33223>.

@article{Maubach2005,
abstract = {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.},
author = {Maubach, Joseph M.},
journal = {Applications of Mathematics},
keywords = {grid generation; space filling curve; load balancing; grid generation; space filling curve; load balancing},
language = {eng},
number = {3},
pages = {309-321},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Space-filling curves for 2-simplicial meshes created with bisections and reflections},
url = {http://eudml.org/doc/33223},
volume = {50},
year = {2005},
}

TY - JOUR
AU - Maubach, Joseph M.
TI - Space-filling curves for 2-simplicial meshes created with bisections and reflections
JO - Applications of Mathematics
PY - 2005
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 50
IS - 3
SP - 309
EP - 321
AB - 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.
LA - eng
KW - grid generation; space filling curve; load balancing; grid generation; space filling curve; load balancing
UR - http://eudml.org/doc/33223
ER -

References

top
  1. 10.1016/0899-8248(91)90006-G, IMPACT Comput. Sci. Eng. 3 (1991), 181–191. (1991) MR1141298DOI10.1016/0899-8248(91)90006-G
  2. Matrix Computations, 2nd edition, The Johns Hopkins University Press, Baltimore, 1989. (1989) MR1002570
  3. 10.1090/S0025-5718-1994-1240660-4, Math. Comput. 63 (1994), 141–154. (1994) MR1240660DOI10.1090/S0025-5718-1994-1240660-4
  4. 10.1016/0377-0427(94)90034-5, J.  Comput. App. Math. 55 (1994), 275–288. (1994) Zbl0823.65119MR1329875DOI10.1016/0377-0427(94)90034-5
  5. 10.1137/S1064827595293545, SIAM J.  Sci. Comput. 19 (1998), 1870–1891. (1998) MR1638068DOI10.1137/S1064827595293545
  6. 10.1007/s002110050135, Numer. Math. 71 (1995), 29–58. (1995) MR1339731DOI10.1007/s002110050135
  7. 10.1137/0916014, SIAM J.  Sci. Comput. 16 (1995), 210–227. (1995) MR1311687DOI10.1137/0916014
  8. 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. (1996) 
  9. Iterative Methods for Non-Linear Partial Differential Equations, CWI, Amsterdam, 1994. (1994) Zbl0820.65022MR1354839
  10. 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. (1997) 
  11. 10.1137/0913009, SIAM J.  Sci. Stat. Comput. 13 (1992), 146–167. (1992) Zbl0746.65087MR1145181DOI10.1137/0913009
  12. An adaptive finite element code for elliptic boundary value problems in three dimensions with applications in numerical relativity, PhD. Thesis, Penn State University, 1996. (1996) 
  13. 10.1016/j.cagd.2004.01.001, Comput. Aided Geom. Des. 21 (2004), 353–369. (2004) MR2046913DOI10.1016/j.cagd.2004.01.001
  14. 10.1002/cnm.1630080502, Commun. Appl. Numer. Methods 8 (1992), 281–290. (1992) DOI10.1002/cnm.1630080502

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.