A cell-centred finite volume method for the Poisson problem on non-graded quadtrees with second order accurate gradients. (English) Zbl 1380.65399

Summary: This paper introduces a two-dimensional cell-centred finite volume discretization of the Poisson problem on adaptive Cartesian quadtree grids which exhibits second order accuracy in both the solution and its gradients, and requires no grading condition between adjacent cells. At T-junction configurations, which occur wherever resolution differs between neighboring cells, use of the standard centred difference gradient stencil requires that ghost values be constructed by interpolation. To properly recover second order accuracy in the resulting numerical gradients, prior work addressing block-structured grids and graded trees has shown that quadratic, rather than linear, interpolation is required; the gradients otherwise exhibit only first order convergence, which limits potential applications such as fluid flow. However, previous schemes fail or lose accuracy in the presence of the more complex T-junction geometries arising in the case of general non-graded quadtrees, which place no restrictions on the resolution of neighboring cells. We therefore propose novel quadratic interpolant constructions for this case that enable second order convergence by relying on stencils oriented diagonally and applied recursively as needed. The method handles complex tree topologies and large resolution jumps between neighboring cells, even along the domain boundary, and both Dirichlet and Neumann boundary conditions are supported. Numerical experiments confirm the overall second order accuracy of the method in the \(L^\infty\) norm.


65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65N08 Finite volume methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
Full Text: DOI Link


[1] Grossmann, C.; Roos, H. -G.; Stynes, M.: Numerical treatment of partial differential equations. (2007) · Zbl 1180.65147
[2] Guermond, J.; Minev, P.; Shen, J.: An overview of projection methods for incompressible flows. Comput. methods appl. Mech. eng. 195, No. 44-47, 6011-6045 (2006) · Zbl 1122.76072
[3] Min, C.; Gibou, F.; Ceniceros, H. D.: A supra-convergent finite difference scheme for the variable coefficient Poisson equation on non-graded grids. J. comput. Phys. 218, No. 1, 123-140 (2006) · Zbl 1106.65093
[4] Colella, P.; Graves, D. T.; Johnson, J. N.; Keen, N. D.; Ligocki, T.; Martin, D. F.; Mccorquodale, P. W.; Modiano, D.; Schwartz, P. O.; Sternberg, T. D.; Van Straalen, B.: Chombo software package for AMR applications design document. (2013)
[5] Minion, M. L.: Two methods for the study of vortex patch evolution on locally refined grids. (1994)
[6] Martin, D. F.; Cartwright, K. L.: Solving Poisson’s equation using adaptive mesh refinement. (1996)
[7] Johansen, H.; Colella, P.: A Cartesian grid embedded boundary method for Poisson’s equation on irregular domains. J. comput. Phys. 147, No. 1, 60-85 (1998) · Zbl 0923.65079
[8] Martin, D. F.; Colella, P.; Graves, D. T.: A cell-centered adaptive projection method for the incompressible Navier-Stokes equations in three dimensions. J. comput. Phys. 227, No. 3, 1863-1886 (2008) · Zbl 1137.76040
[9] Pletzer, A.; Jamroz, B.; Crockett, R.; Sides, S.: Compact cell-centered discretization stencils at fine-coarse block structured grid interfaces. J. comput. Phys. 260, 25-36 (2014) · Zbl 1349.65570
[10] Liu, Q.: A stable and accurate projection method on a locally refined staggered mesh. Int. J. Numer. methods fluids 67, No. 1, 74-92 (2011) · Zbl 1303.76107
[11] Henshaw, W.: A fourth-order accurate method for the incompressible Navier-Stokes equations on overlapping grids. J. comput. Phys. 113, No. 1, 13-25 (1994) · Zbl 0808.76059
[12] English, R. E.; Qiu, L.; Yu, Y.; Fedkiw, R.: An adaptive discretization of incompressible flow using a multitude of moving Cartesian grids. J. comput. Phys. 254, 107-154 (2013) · Zbl 1349.76456
[13] Popinet, S.: Gerris: a tree-based adaptive solver for the incompressible Euler equations in complex geometries. J. comput. Phys. 190, No. 2, 572-600 (2003) · Zbl 1076.76002
[14] Losasso, F.; Gibou, F.; Fedkiw, R.: Simulating water and smoke with an octree data structure. ACM trans. Graph. 23, No. 3, 457-462 (2004)
[15] Losasso, F.; Fedkiw, R.; Osher, S.: Spatially adaptive techniques for level set methods and incompressible flow. Comput. fluids 35, No. 10, 995-1010 (2005) · Zbl 1177.76295
[16] Finkel, R.; Bentley, J. L.: Quad trees: a data structure for retrieval on composite keys. Acta inform. 4, No. 1, 1-9 (1974) · Zbl 0278.68030
[17] Meagher, D.: Geometric modeling using octree encoding. Comput. graph. Image process. 19, No. 2, 129-147 (1982)
[18] Minion, M. L.: A projection method for locally refined grids. J. comput. Phys. 127, No. 1, 158-178 (1996) · Zbl 0859.76047
[19] Guittet, A.; Theillard, M.; Gibou, F.: A stable projection method for the incompressible Navier-Stokes equations on arbitrary geometries and adaptive quad/octrees. J. comput. Phys. 292, 215-238 (2015) · Zbl 1349.76336
[20] Min, C.; Gibou, F.: A second order accurate projection method for the incompressible Navier-Stokes equations on non-graded adaptive grids. J. comput. Phys. 219, No. 2, 912-929 (2006) · Zbl 1330.76096
[21] Gupta, A.: A finite element for transition from a finite grid to a coarse grid. Int. J. Numer. methods eng. 12, No. 1, 35-45 (1978) · Zbl 0369.73073
[22] Tabarraei, A.; Sukumar, N.: Adaptive computations on conforming quadtree meshes. Finite elem. Anal. des. 41, No. 7, 686-702 (2005)
[23] Natarajan, S.; Ooi, E. T.; Man, H.; Song, C.: Finite element computations on quadtree meshes: strain smoothing and semi-analytical formulation. Int. J. Adv. eng. Sci. appl. Math. 7, No. 3, 124-133 (2015) · Zbl 1342.74168
[24] Barad, M.; Colella, P.: A fourth-order accurate local refinement method for Poisson’s equation. J. comput. Phys. 209, No. 1, 1-18 (2005) · Zbl 1073.65126
[25] Seibold, B.: Minimal positive stencils in meshfree finite difference methods for the Poisson equation. Comput. methods appl. Mech. eng. 198, No. 3, 592-601 (2008) · Zbl 1228.65209
[26] Olshanskii, M. A.; Terekhov, K. M.; Vassilevski, Y. V.: An octree-based solver for the incompressible Navier-Stokes equations with enhanced stability and low dissipation. Comput. fluids 84, 231-246 (2013) · Zbl 1290.76106
[27] Min, C.; Gibou, F.: A second order accurate level set method on non-graded adaptive Cartesian grids. J. comput. Phys. 225, No. 1, 300-321 (2007) · Zbl 1122.65077
[28] Chen, H.; Min, C.; Gibou, F.: A numerical scheme for the Stefan problem on adaptive Cartesian grids with supralinear convergence rate. J. comput. Phys. 228, No. 16, 5803-5818 (2009) · Zbl 1176.80059
[29] Papac, J.; Helgadottir, A.; Ratsch, C.; Gibou, F.: A level set approach for diffusion and Stefan-type problems with Robin boundary conditions on quadtree/octree adaptive Cartesian grids. J. comput. Phys. 233, 241-261 (2013)
[30] Theillard, M.; Djodom, L. F.; Vié, J. -L.; Gibou, F.: A second-order sharp numerical method for solving the linear elasticity equations on irregular domains and adaptive grids - application to shape optimization. J. comput. Phys. 233, 430-448 (2013) · Zbl 1286.74109
[31] Mirzadeh, M.; Gibou, M. Theillard; Gibou, F.: A second-order discretization of the nonlinear Poisson-Boltzmann equation over irregular geometries using non-graded adaptive Cartesian grids. J. comput. Phys. 230, No. 5, 2125-2140 (2011) · Zbl 1390.82056
[32] Helgadóttir, Á.; Gibou, F.: A Poisson-Boltzmann solver on irregular domains with Neumann or Robin boundary conditions on non-graded adaptive grid. J. comput. Phys. 230, No. 10, 3830-3848 (2011) · Zbl 1369.76033
[33] Mirzadeh, M.; Gibou, F.: A conservative discretization of the Poisson-Nernst-Planck equations on adaptive Cartesian grids. J. comput. Phys. 274, 633-653 (2014) · Zbl 1351.82082
[34] Martin, D. F.; Colella, P.: A cell-centered adaptive projection method for the incompressible Euler equations. J. comput. Phys. 163, No. 2, 271-312 (2000) · Zbl 0991.76052
[35] Chesshire, G.; Henshaw, W.: Composite overlapping meshes for the solution of partial differential equations. J. comput. Phys. 90, 1-64 (1990) · Zbl 0709.65090
[36] Shortley, G. H.; Weller, R.: The numerical solution of Laplace’s equation. J. appl. Phys. 9, No. 5, 334 (1938) · Zbl 0019.03801
[37] Gibou, F.; Fedkiw, R.; Cheng, L. -T.; Kang, M.: A second order accurate symmetric discretization of the Poisson equation on irregular domains. J. comput. Phys. 176, No. 1, 205-227 (2002) · Zbl 0996.65108
[38] Ng, Y. T.; Chen, H.; Min, C.; Gibou, F.: Guidelines for Poisson solvers on irregular domains with Dirichlet boundary conditions using the ghost fluid method. J. sci. Comput. 41, No. 2, 300-320 (2009) · Zbl 1203.65223
[39] Stanoyevitch, A.: Introduction to numerical ordinary and partial differential equations using Matlab. (2011) · Zbl 1071.65002
[40] Guennebaud, G.; Jacob, B.: Others, eigen v3. (2010)
[41] Li, X. S.: An overview of superlu: algorithms, implementation and user interface. ACM trans. Math. softw. 31, No. 3, 302-325 (2005) · Zbl 1136.65312
[42] Ng, Y. T.; Min, C.; Gibou, F.: An efficient fluid-solid coupling algorithm for single-phase flows. J. comput. Phys. 228, No. 23, 8807-8829 (2009) · Zbl 1245.76019
[43] Demmel, J. W.: Applied numerical linear algebra. (1997) · Zbl 0879.65017
[44] Chen, H.; Min, C.; Gibou, F.: A supra-convergent finite difference scheme for the Poisson and heat equations on irregular domains and non-graded adaptive Cartesian grids. J. sci. Comput. 31, No. 1, 19-60 (2007) · Zbl 1120.65113
[45] Brezzi, F.; Lipnikov, K.; Simoncini, V.: A family of mimetic finite difference methods on polygonal and polyhedral meshes. Math. models methods appl. Sci. 15, No. 10, 1533-1551 (2005) · Zbl 1083.65099
[46] Da Veiga, L. B.; Manzini, G.: A higher-order formulation of the mimetic finite difference method. SIAM J. Sci. comput. 31, No. 1, 732-760 (2008) · Zbl 1185.65201
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.