×

zbMATH — the first resource for mathematics

Voronoi-based finite volume methods, optimal Voronoi meshes, and PDEs on the sphere. (English) Zbl 1046.65094
The authors explain the concept of Voronoi meshes on the sphere and propose a finite volume discretization scheme for partial differential equations (PDEs) posed on the sphere. They prove that the scheme is first order accurate with respect to a mesh-dependent discrete first-derivative norm for the model convection-diffusion problem on the sphere: \[ \nabla_s\cdot (-a(x)\nabla_s u(x) + \vec{v}(x) u (x)) + b(x) u(x) = f(x)\quad \text{for}\;x\in S^2, \] where \(S^2\) is the sphere of radius \(r>0\) in \(\mathbb{R}^3\). Note that, since \(S^2\) has no boundary, no boundary conditions need to be imposed.
They introduce the notion of constrained centroidal Voronoi tessellations (CCVTs) of the sphere and illustrate the high-quality uniform and non-uniform meshes that are included in this special class of Voronoi meshes.
Computational experiments illustrate the performance of the CCVT meshes used in conjunction with the finite volume scheme for the solution of simple model PDEs on the sphere. The experiments show that the approximations are second order accurate if errors are measured in discrete \(L^2\) norms.

MSC:
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65N15 Error bounds for boundary value problems involving PDEs
58J05 Elliptic equations on manifolds, general theory
35J25 Boundary value problems for second-order elliptic equations
Software:
STRIPACK
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aurenhammer, F., Voronoi diagrams–A survey of a fundamental geometric data structure, ACM comput. surv., 23, 345-405, (1991)
[2] Baumgaedner, J.; Frederickson, P., Icosahedral discretization of the two-sphere, SIAM J. numer. anal., 22, 1107-1115, (1985) · Zbl 0601.65084
[3] Cai, Z., On the finite volume element method, Numer. math., 58, 713-735, (1991) · Zbl 0731.65093
[4] Coudière, Y.; Gallouët, T.; Herbin, R., Discrete Sobolev inequalities and Lp error extimates for finite volume solutions of convection diffusion equations, Math. model. numer. anal., 35, 767-778, (2001) · Zbl 0990.65122
[5] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM rev., 41, 637-676, (1999) · Zbl 0983.65021
[6] Du, Q.; Gunzburger, M.; Ju, L., Constrained centroidal Voronoi tessellations on general surfaces, SIAM J. sci. comput., 24, 1488-1506, (2003) · Zbl 1036.65101
[7] Q. Du, L. Ju, Finite volume methods on spheres and spherical centroidal Voronoi meshes, preprint, 2003 · Zbl 1099.65107
[8] Ewing, R.; Lazarov, R.; Vassilevski, P., Local refinement techniques for elliptic problems on cell-centered grids I. error analysis, Math. comput., 56, 437-461, (1991) · Zbl 0724.65093
[9] Dziuk, G., Finite elements for the Beltrami operator on arbitrary surfaces, (), 142-155
[10] Gallouët, T.; Herbin, R.; Vignal, M., Error estimates on the approximate finite volume solution of convection diffusion equations with general boundary conditions, SIAM J. numer. anal., 37, 1935-1972, (2000) · Zbl 0986.65099
[11] Hebey, E., Sobolev spaces on Riemannian manifolds, (1991), Springer Berlin
[12] Herbin, R., An error estimate for a finite volume scheme for a diffusion – convection problem on a triangular mesh, Numer. meth. PDE, 11, 165-173, (1995) · Zbl 0822.65085
[13] Heinrich, J.; Hyakorn, P.; Zienkiewicz, O.; Mitchell, A., An “upwind” finite element scheme for two-dimensional convective transport equations, Int. J. numer. meth. engrg., 11, 131-143, (1977) · Zbl 0353.65065
[14] Ju, L.; Du, Q.; Gunzburger, M., Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations, Paral. comput., 28, 1477-1500, (2002) · Zbl 1014.68202
[15] Lazarov, R.; Mishev, I.; Vassilevski, P., Finite volume methods for convection – diffusion problems, SIAM J. numer. anal., 33, 31-55, (1996) · Zbl 0847.65075
[16] Mishev, I., Finite volume methods on Voronoi meshes, Numer. meth. PDE, 14, 193-212, (1998) · Zbl 0903.65083
[17] Nĕcas, J., LES Méthodes directes en théorie des équations elliptiques, (1967), Masson Paris · Zbl 1225.35003
[18] Renka, R., Algorithm 772. stripack: Delaunay triangulation and Voronoi diagrams on the surface of a sphere, ACM trans. math. soft., 23, 416-434, (1997) · Zbl 0903.65111
[19] Schmidt, T., Box schemes on quadrilateral meshes, Computing, 51, 271-292, (1993) · Zbl 0787.65075
[20] Thomas, J.; Trujillo, D., Finite volume variational formulation: application to domain decomposition methods, Contem. math., 157, 127-132, (1994) · Zbl 0802.65118
[21] Vanselow, R., Relations between FEM and FVM, () · Zbl 0858.65109
[22] Vassilevski, P.; Petrova, S.; Lazarov, R., Finite difference schemes on triangular cell-centered grids with local refinement, SIAM J. sci. stat. comput., 13, 1287-1313, (1992) · Zbl 0813.65115
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.