August  2016, 36(8): 4247-4270. doi: 10.3934/dcds.2016.36.4247

High-order finite-volume methods on locally-structured grids

1. 

Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, United States

Received  June 2015 Revised  December 2015 Published  March 2016

We present an approach to designing arbitrarily high-order finite-volume spatial discretizations on locally-rectangular grids. It is based on the use of a simple class of high-order quadratures for computing the average of fluxes over faces. This approach has the advantage of being a variation on widely-used second-order methods, so that the prior experience in engineering those methods carries over in the higher-order case. Among the issues discussed are the basic design principles for uniform grids, the extension to locally-refined nest grid hierarchies, and the treatment of complex geometries using mapped grids, multiblock grids, and cut-cell representations.
Citation: Phillip Colella. High-order finite-volume methods on locally-structured grids. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4247-4270. doi: 10.3934/dcds.2016.36.4247
References:
[1]

M. Aftosmis, M. Berger and J. Melton, Robust and efficient Cartesian mesh generation for component-based geometry,, AIAA Journal, 6 (1998), 952.  doi: 10.2514/6.1997-196.  Google Scholar

[2]

M. Barad and P. Colella, A fourth-order accurate local refinement method for Poisson's equation,, Journal of Computational Physics, 209 (2005), 1.  doi: 10.1016/j.jcp.2005.02.027.  Google Scholar

[3]

P. Basu, M. Hall, S. Williams, B. Van Straalen, L. Oliker and P. Colella, Compiler-directed transformation for higher-order stencils,, in Proceedings of the Parallel and Distributed Processing Symposium (IPDPS), (2015), 313.  doi: 10.1109/IPDPS.2015.103.  Google Scholar

[4]

J. B. Bell, P. Colella and M. Welcome, A conservative front-tracking for inviscid compressible flow,, in Proceedings of the Tenth AIAA Computational Fluid Dynamics Conference, (1991), 814.  doi: 10.2514/6.1991-1599.  Google Scholar

[5]

M. J. Berger and P. Colella, Local adaptive mesh refinement for shock hydrodynamics,, Journal of Computational Physics, 82 (1989), 64.  doi: 10.1016/0021-9991(89)90035-1.  Google Scholar

[6]

M. J. Berger and A. Jameson, Automatic adaptive grid refinement for the Euler equations,, AIAA Journal, 23 (1985), 561.  doi: 10.2514/3.8951.  Google Scholar

[7]

M. J. Berger and R. J. LeVeque, An adaptive Cartesian mesh algorithm for the euler equations in arbitrary geometries,, in Proceedings of the AIAA 9th Computational Fluid Dynamics Conference, (1989), 1.  doi: 10.2514/6.1989-1930.  Google Scholar

[8]

J. P. Boris and D. L. Book, Flux-corrected transport. I. SHASTA, a fluid transport algorithm that works,, Journal of Computational Physics, 11 (1973), 38.  doi: 10.1016/0021-9991(73)90147-2.  Google Scholar

[9]

A. Bourlioux, A. T. Layton and M. L. Minion, Higher-order multi-implicit spectral deferred correction methods for problems of reacting flow,, Journal of Computational Physics, 189 (2003), 651.  doi: 10.1016/S0021-9991(03)00251-1.  Google Scholar

[10]

C. Chaplin and P. Colella, A single stage flux-corrected transport algorithm for high-order finite-volume methods,, preprint, ().   Google Scholar

[11]

I.-L. Chern and P. Colella, A conservative front tracking method for hyperbolic conservation laws,, Technical Report UCRL-97200, (1987).   Google Scholar

[12]

P. Colella, Multidimensional upwind methods for hyperbolic conservation laws,, Journal of Computational Physics, 87 (1990), 171.  doi: 10.1016/0021-9991(90)90233-Q.  Google Scholar

[13]

P. Colella, Volume-of-fluid methods for partial differential equations,, In Godunov Methods: Theory and Applications, (2001), 161.   Google Scholar

[14]

P. Colella, M.R. Dorr, J. A. F. Hittinger and D. F. Martin, High-order, finite-volume methods in mapped coordinates,, Journal of Computational Physics, 230 (2011), 2952.  doi: 10.1016/j.jcp.2010.12.044.  Google Scholar

[15]

P. Colella and M. D. Sekora, A limiter for PPM that preserves accuracy at smooth extrema,, Journal of Computational Physics, 227 (2008), 7069.  doi: 10.1016/j.jcp.2008.03.034.  Google Scholar

[16]

P. Colella and P. R. Woodward, The piecewise parabolic method (PPM) for gas-dynamical simulations,, Journal of Computational Physics, 54 (1989), 174.  doi: 10.1016/0021-9991(84)90143-8.  Google Scholar

[17]

D. Devendran, D. T. Graves and H. Johansen, A higher-order finite-volume discretization method for Poisson's equation in cut cell geometries,, preprint, ().   Google Scholar

[18]

C. Gatti-Bono and P. Colella, An anelastic allspeed projection method for gravitationally stratified flows,, Journal of Computational Physics, 216 (2006), 589.  doi: 10.1016/j.jcp.2005.12.017.  Google Scholar

[19]

S. M. Guzik, X. Gao, L. D. Owen, P. McCorquodale and P. Colella, A freestream-preserving fourth-order finite-volume method in mapped coordinates with adaptive mesh refinement,, Computers and Fluids, 123 (2015), 202.  doi: 10.1016/j.compfluid.2015.10.001.  Google Scholar

[20]

J. Hilditch and P. Colella, A Projection Method for Low Mach Number Fast Chemistry Reacting Flow,, Technical Report AIAA-97-0263, (1997), 97.  doi: 10.2514/6.1997-263.  Google Scholar

[21]

H. Johansen and P. Colella, A Cartesian grid embedded boundary method for Poisson's equation on irregular domains,, Journal of Computational Physics, 147 (1998), 60.  doi: 10.1006/jcph.1998.5965.  Google Scholar

[22]

C. A. Kennedy and M. H. Carpenter, Additive Runge-Kutta schemes for convection-diffusion-reaction equations,, Applied Numerical Mathematics, 44 (2003), 139.  doi: 10.1016/S0168-9274(02)00138-1.  Google Scholar

[23]

H.-O. Kreiss and J. Oliger, Comparison of accurate methods for the integration of hyperbolic equations,, Tellus, 24 (1972), 199.  doi: 10.1111/j.2153-3490.1972.tb01547.x.  Google Scholar

[24]

P. D. Lax, Weak solutions of nonlinear hyperbolic equations and their numerical computation,, Communications on Pure and Applied Mathematics 7 (1954), 7 (1954), 159.  doi: 10.1002/cpa.3160070112.  Google Scholar

[25]

P. D. Lax, On Discontinuous Initial-Value Problems and Finite-Difference Schemes,, Technical Report LAMS-1332, (1952).   Google Scholar

[26]

P. D. Lax and B. Wendroff, Systems of conservation laws,, Communications on Pure and Applied Mathematics, 13 (1960), 217.  doi: 10.1002/cpa.3160130205.  Google Scholar

[27]

R. Malladi, J. A. Sethian and B. C. Vemuri, Shape modeling with front propagation: A level set approach,, IEEE Transactions on Pattern Anal. Machine Intell, 17 (1995), 158.  doi: 10.1109/34.368173.  Google Scholar

[28]

P. McCorquodale and P. Colella, A high-order finite-volume method for conservation laws on locally refined grids,, Communications in Applied Mathematics and Computational Science 6 (2011), 6 (2011), 1.  doi: 10.2140/camcos.2011.6.1.  Google Scholar

[29]

P. McCorquodale, P. Colella and H. Johansen, A Cartesian grid embedded boundary method for the heat equation on irregular domains,, Journal of Computational Physics, 173 (2001), 620.  doi: 10.1006/jcph.2001.6900.  Google Scholar

[30]

P. McCorquodale, M. R. Dorr, J. A. F. Hittinger and P. Colella, High-order finite-volume methods for hyperbolic conservation laws on mapped multiblock grids,, Journal of Computational Physics, 288 (2015), 181.  doi: 10.1016/j.jcp.2015.01.006.  Google Scholar

[31]

L. I. Millett and S. H. Fuller, et al., The Future of Computing Performance: Game Over or Next Level?,, National Academies Press, (2011).   Google Scholar

[32]

J. von Neumann and R. D. Richtmyer, A method for the numerical calculation of hydrodynamic shocks,, Journal of Applied Physics, 21 (1950), 232.  doi: 10.1063/1.1699639.  Google Scholar

[33]

W. F. Noh, CEL: A time-dependent, two-space-dimensional, coupled Eulerian - Lagrangian code,, Methods in Computational Physics, 3 (1964), 117.   Google Scholar

[34]

R. B. Pember, J. B. Bell, P. Colella, W. Y. Crutchfield and M. L. Welcome, An adaptive Cartesian} grid method for unsteady compressible flow in irregular regions,, Journal of Computational Physics, 120 (1995), 278.  doi: 10.1006/jcph.1995.1165.  Google Scholar

[35]

R. B. Pember, L. H. Howell, J. B. Bell, P. Colella, W. Y. Crutchfield, W. A. Fiveland and J. P. Jessee, An adaptive projection method for unsteady, low-Mach-number combustion,, Combustion Science and Technology, 140 (1998), 123.  doi: 10.1080/00102209808915770.  Google Scholar

[36]

J. S. Saltzman, An unsplit 3D upwind method for hyperbolic conservation laws,, Journal of Computational Physics, 115 (1994), 153.  doi: 10.1006/jcph.1994.1184.  Google Scholar

[37]

P. Schwartz, J. Percelay, T. Ligocki, H. Johansen, D. Graves, D. Devendran, P. Colella and E. Ateljevich, High-accuracy embedded boundary grid generation using the divergence theorem,, Communications in Applied Mathematics and Computational Science, 10 (2015), 83.  doi: 10.2140/camcos.2015.10.83.  Google Scholar

[38]

D. Trebotich, M. F. Adams, S. Molins, C. I. Steefel and C. Shen, High-resolution simulation of pore-scale reactive transport processes associated with carbon sequestration,, Computing in Science and Engineering, 16 (2014), 22.  doi: 10.1109/MCSE.2014.77.  Google Scholar

[39]

B. van Leer, Towards the ultimate conservative differences scheme IV: a new approach to numerical convection,, Journal of Computational Physics, 23 (1977), 263.   Google Scholar

[40]

S. Williams, A. Waterman and D. Patterson, Roofline: an insightful visual performance model for multicore architectures,, Communications of the ACM, 52 (2009), 65.  doi: 10.1145/1498765.1498785.  Google Scholar

[41]

P. R. Woodward and P. Colella, The numerical simulation of two-dimensional fluid flow with strong shocks,, Journal of Computational Physics, 54 (1984), 115.  doi: 10.1016/0021-9991(84)90142-6.  Google Scholar

[42]

S. T. Zalesak, Fully multidimensional flux-corrected transport algorithms for fluids,, Journal of Computational Physics, 31 (1979), 335.  doi: 10.1016/0021-9991(79)90051-2.  Google Scholar

[43]

S. T. Zalesak, A physical interpretation of the Richtmyer two-step Lax-Wendroff scheme and its generalization to higher spatial order,, in Advances in Computer Methods for Partial Differential Equations, (1984), 19.   Google Scholar

show all references

References:
[1]

M. Aftosmis, M. Berger and J. Melton, Robust and efficient Cartesian mesh generation for component-based geometry,, AIAA Journal, 6 (1998), 952.  doi: 10.2514/6.1997-196.  Google Scholar

[2]

M. Barad and P. Colella, A fourth-order accurate local refinement method for Poisson's equation,, Journal of Computational Physics, 209 (2005), 1.  doi: 10.1016/j.jcp.2005.02.027.  Google Scholar

[3]

P. Basu, M. Hall, S. Williams, B. Van Straalen, L. Oliker and P. Colella, Compiler-directed transformation for higher-order stencils,, in Proceedings of the Parallel and Distributed Processing Symposium (IPDPS), (2015), 313.  doi: 10.1109/IPDPS.2015.103.  Google Scholar

[4]

J. B. Bell, P. Colella and M. Welcome, A conservative front-tracking for inviscid compressible flow,, in Proceedings of the Tenth AIAA Computational Fluid Dynamics Conference, (1991), 814.  doi: 10.2514/6.1991-1599.  Google Scholar

[5]

M. J. Berger and P. Colella, Local adaptive mesh refinement for shock hydrodynamics,, Journal of Computational Physics, 82 (1989), 64.  doi: 10.1016/0021-9991(89)90035-1.  Google Scholar

[6]

M. J. Berger and A. Jameson, Automatic adaptive grid refinement for the Euler equations,, AIAA Journal, 23 (1985), 561.  doi: 10.2514/3.8951.  Google Scholar

[7]

M. J. Berger and R. J. LeVeque, An adaptive Cartesian mesh algorithm for the euler equations in arbitrary geometries,, in Proceedings of the AIAA 9th Computational Fluid Dynamics Conference, (1989), 1.  doi: 10.2514/6.1989-1930.  Google Scholar

[8]

J. P. Boris and D. L. Book, Flux-corrected transport. I. SHASTA, a fluid transport algorithm that works,, Journal of Computational Physics, 11 (1973), 38.  doi: 10.1016/0021-9991(73)90147-2.  Google Scholar

[9]

A. Bourlioux, A. T. Layton and M. L. Minion, Higher-order multi-implicit spectral deferred correction methods for problems of reacting flow,, Journal of Computational Physics, 189 (2003), 651.  doi: 10.1016/S0021-9991(03)00251-1.  Google Scholar

[10]

C. Chaplin and P. Colella, A single stage flux-corrected transport algorithm for high-order finite-volume methods,, preprint, ().   Google Scholar

[11]

I.-L. Chern and P. Colella, A conservative front tracking method for hyperbolic conservation laws,, Technical Report UCRL-97200, (1987).   Google Scholar

[12]

P. Colella, Multidimensional upwind methods for hyperbolic conservation laws,, Journal of Computational Physics, 87 (1990), 171.  doi: 10.1016/0021-9991(90)90233-Q.  Google Scholar

[13]

P. Colella, Volume-of-fluid methods for partial differential equations,, In Godunov Methods: Theory and Applications, (2001), 161.   Google Scholar

[14]

P. Colella, M.R. Dorr, J. A. F. Hittinger and D. F. Martin, High-order, finite-volume methods in mapped coordinates,, Journal of Computational Physics, 230 (2011), 2952.  doi: 10.1016/j.jcp.2010.12.044.  Google Scholar

[15]

P. Colella and M. D. Sekora, A limiter for PPM that preserves accuracy at smooth extrema,, Journal of Computational Physics, 227 (2008), 7069.  doi: 10.1016/j.jcp.2008.03.034.  Google Scholar

[16]

P. Colella and P. R. Woodward, The piecewise parabolic method (PPM) for gas-dynamical simulations,, Journal of Computational Physics, 54 (1989), 174.  doi: 10.1016/0021-9991(84)90143-8.  Google Scholar

[17]

D. Devendran, D. T. Graves and H. Johansen, A higher-order finite-volume discretization method for Poisson's equation in cut cell geometries,, preprint, ().   Google Scholar

[18]

C. Gatti-Bono and P. Colella, An anelastic allspeed projection method for gravitationally stratified flows,, Journal of Computational Physics, 216 (2006), 589.  doi: 10.1016/j.jcp.2005.12.017.  Google Scholar

[19]

S. M. Guzik, X. Gao, L. D. Owen, P. McCorquodale and P. Colella, A freestream-preserving fourth-order finite-volume method in mapped coordinates with adaptive mesh refinement,, Computers and Fluids, 123 (2015), 202.  doi: 10.1016/j.compfluid.2015.10.001.  Google Scholar

[20]

J. Hilditch and P. Colella, A Projection Method for Low Mach Number Fast Chemistry Reacting Flow,, Technical Report AIAA-97-0263, (1997), 97.  doi: 10.2514/6.1997-263.  Google Scholar

[21]

H. Johansen and P. Colella, A Cartesian grid embedded boundary method for Poisson's equation on irregular domains,, Journal of Computational Physics, 147 (1998), 60.  doi: 10.1006/jcph.1998.5965.  Google Scholar

[22]

C. A. Kennedy and M. H. Carpenter, Additive Runge-Kutta schemes for convection-diffusion-reaction equations,, Applied Numerical Mathematics, 44 (2003), 139.  doi: 10.1016/S0168-9274(02)00138-1.  Google Scholar

[23]

H.-O. Kreiss and J. Oliger, Comparison of accurate methods for the integration of hyperbolic equations,, Tellus, 24 (1972), 199.  doi: 10.1111/j.2153-3490.1972.tb01547.x.  Google Scholar

[24]

P. D. Lax, Weak solutions of nonlinear hyperbolic equations and their numerical computation,, Communications on Pure and Applied Mathematics 7 (1954), 7 (1954), 159.  doi: 10.1002/cpa.3160070112.  Google Scholar

[25]

P. D. Lax, On Discontinuous Initial-Value Problems and Finite-Difference Schemes,, Technical Report LAMS-1332, (1952).   Google Scholar

[26]

P. D. Lax and B. Wendroff, Systems of conservation laws,, Communications on Pure and Applied Mathematics, 13 (1960), 217.  doi: 10.1002/cpa.3160130205.  Google Scholar

[27]

R. Malladi, J. A. Sethian and B. C. Vemuri, Shape modeling with front propagation: A level set approach,, IEEE Transactions on Pattern Anal. Machine Intell, 17 (1995), 158.  doi: 10.1109/34.368173.  Google Scholar

[28]

P. McCorquodale and P. Colella, A high-order finite-volume method for conservation laws on locally refined grids,, Communications in Applied Mathematics and Computational Science 6 (2011), 6 (2011), 1.  doi: 10.2140/camcos.2011.6.1.  Google Scholar

[29]

P. McCorquodale, P. Colella and H. Johansen, A Cartesian grid embedded boundary method for the heat equation on irregular domains,, Journal of Computational Physics, 173 (2001), 620.  doi: 10.1006/jcph.2001.6900.  Google Scholar

[30]

P. McCorquodale, M. R. Dorr, J. A. F. Hittinger and P. Colella, High-order finite-volume methods for hyperbolic conservation laws on mapped multiblock grids,, Journal of Computational Physics, 288 (2015), 181.  doi: 10.1016/j.jcp.2015.01.006.  Google Scholar

[31]

L. I. Millett and S. H. Fuller, et al., The Future of Computing Performance: Game Over or Next Level?,, National Academies Press, (2011).   Google Scholar

[32]

J. von Neumann and R. D. Richtmyer, A method for the numerical calculation of hydrodynamic shocks,, Journal of Applied Physics, 21 (1950), 232.  doi: 10.1063/1.1699639.  Google Scholar

[33]

W. F. Noh, CEL: A time-dependent, two-space-dimensional, coupled Eulerian - Lagrangian code,, Methods in Computational Physics, 3 (1964), 117.   Google Scholar

[34]

R. B. Pember, J. B. Bell, P. Colella, W. Y. Crutchfield and M. L. Welcome, An adaptive Cartesian} grid method for unsteady compressible flow in irregular regions,, Journal of Computational Physics, 120 (1995), 278.  doi: 10.1006/jcph.1995.1165.  Google Scholar

[35]

R. B. Pember, L. H. Howell, J. B. Bell, P. Colella, W. Y. Crutchfield, W. A. Fiveland and J. P. Jessee, An adaptive projection method for unsteady, low-Mach-number combustion,, Combustion Science and Technology, 140 (1998), 123.  doi: 10.1080/00102209808915770.  Google Scholar

[36]

J. S. Saltzman, An unsplit 3D upwind method for hyperbolic conservation laws,, Journal of Computational Physics, 115 (1994), 153.  doi: 10.1006/jcph.1994.1184.  Google Scholar

[37]

P. Schwartz, J. Percelay, T. Ligocki, H. Johansen, D. Graves, D. Devendran, P. Colella and E. Ateljevich, High-accuracy embedded boundary grid generation using the divergence theorem,, Communications in Applied Mathematics and Computational Science, 10 (2015), 83.  doi: 10.2140/camcos.2015.10.83.  Google Scholar

[38]

D. Trebotich, M. F. Adams, S. Molins, C. I. Steefel and C. Shen, High-resolution simulation of pore-scale reactive transport processes associated with carbon sequestration,, Computing in Science and Engineering, 16 (2014), 22.  doi: 10.1109/MCSE.2014.77.  Google Scholar

[39]

B. van Leer, Towards the ultimate conservative differences scheme IV: a new approach to numerical convection,, Journal of Computational Physics, 23 (1977), 263.   Google Scholar

[40]

S. Williams, A. Waterman and D. Patterson, Roofline: an insightful visual performance model for multicore architectures,, Communications of the ACM, 52 (2009), 65.  doi: 10.1145/1498765.1498785.  Google Scholar

[41]

P. R. Woodward and P. Colella, The numerical simulation of two-dimensional fluid flow with strong shocks,, Journal of Computational Physics, 54 (1984), 115.  doi: 10.1016/0021-9991(84)90142-6.  Google Scholar

[42]

S. T. Zalesak, Fully multidimensional flux-corrected transport algorithms for fluids,, Journal of Computational Physics, 31 (1979), 335.  doi: 10.1016/0021-9991(79)90051-2.  Google Scholar

[43]

S. T. Zalesak, A physical interpretation of the Richtmyer two-step Lax-Wendroff scheme and its generalization to higher spatial order,, in Advances in Computer Methods for Partial Differential Equations, (1984), 19.   Google Scholar

[1]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079

[2]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[3]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[4]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073

[5]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[6]

H. M. Srivastava, H. I. Abdel-Gawad, Khaled Mohammed Saad. Oscillatory states and patterns formation in a two-cell cubic autocatalytic reaction-diffusion model subjected to the Dirichlet conditions. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020433

[7]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[8]

Anton A. Kutsenko. Isomorphism between one-Dimensional and multidimensional finite difference operators. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020270

[9]

Wenjun Liu, Yukun Xiao, Xiaoqing Yue. Classification of finite irreducible conformal modules over Lie conformal algebra $ \mathcal{W}(a, b, r) $. Electronic Research Archive, , () : -. doi: 10.3934/era.2020123

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (28)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]