Adaptive mesh refinement

Last updated

In numerical analysis, adaptive mesh refinement (AMR) is a method of adapting the accuracy of a solution within certain sensitive or turbulent regions of simulation, dynamically and during the time the solution is being calculated. When solutions are calculated numerically, they are often limited to predetermined quantified grids as in the Cartesian plane which constitute the computational grid, or 'mesh'. Many problems in numerical analysis, however, do not require a uniform precision in the numerical grids used for graph plotting or computational simulation, and would be better suited if specific areas of graphs which needed precision could be refined in quantification only in the regions requiring the added precision. Adaptive mesh refinement provides such a dynamic programming environment for adapting the precision of the numerical computation based on the requirements of a computation problem in specific areas of multi-dimensional graphs which need precision while leaving the other regions of the multi-dimensional graphs at lower levels of precision and resolution.

Contents

This dynamic technique of adapting computation precision to specific requirements has been accredited to Marsha Berger, Joseph Oliger, and Phillip Colella who developed an algorithm for dynamic gridding called local adaptive mesh refinement. The use of AMR has since then proved of broad use and has been used in studying turbulence problems in hydrodynamics as well as in the study of large scale structures in astrophysics as in the Bolshoi Cosmological Simulation.

Development of adaptive mesh refinement

The image above shows the grid structure of an AMR calculation of a shock impacting an inclined slope. Each of the boxes is a grid; the more boxes it is nested within, the higher the level of refinements. As the image shows, the algorithm uses high resolution grids only at the physical locations and times where they are required. Amrgridimg.jpg
The image above shows the grid structure of an AMR calculation of a shock impacting an inclined slope. Each of the boxes is a grid; the more boxes it is nested within, the higher the level of refinements. As the image shows, the algorithm uses high resolution grids only at the physical locations and times where they are required.

In a series of papers, Marsha Berger, Joseph Oliger, and Phillip Colella developed an algorithm for dynamic gridding called local adaptive mesh refinement. [1] [2] The algorithm begins with the entire computational domain covered with a coarsely resolved base-level regular Cartesian grid. As the calculation progresses, individual grid cells are tagged for refinement, using a criterion that can either be user-supplied (for example mass per cell remains constant, hence higher density regions are more highly resolved) or based on Richardson extrapolation.

All tagged cells are then refined, meaning that a finer grid is overlaid on the coarse one. After refinement, individual grid patches on a single fixed level of refinement are passed off to an integrator which advances those cells in time. Finally, a correction procedure is implemented to correct the transfer along coarse-fine grid interfaces, to ensure that the amount of any conserved quantity leaving one cell exactly balances the amount entering the bordering cell. If at some point the level of refinement in a cell is greater than required, the high resolution grid may be removed and replaced with a coarser grid.

This allows the user to solve problems that are completely intractable on a uniform grid; for example, astrophysicists have used AMR to model a collapsing giant molecular cloud core down to an effective resolution of 131,072 cells per initial cloud radius, corresponding to a resolution of 1015 cells on a uniform grid. [3]

Advanced mesh refinement has been introduced via functionals. [4] Functionals allow the ability to generate grids and provide mesh adaptation. Some advanced functionals include the Winslow and modified Liao functionals. [5]

Applications of adaptive mesh refinement

When calculating a solution to the shallow water equations, the solution (water height) might only be calculated for points every few feet apart—and one would assume that in between those points the height varies smoothly. The limiting factor to the resolution of the solution is thus the grid spacing: there will be no features of the numerical solution on scales smaller than the grid-spacing. Adaptive mesh refinement (AMR) changes the spacing of grid points, to change how accurately the solution is known in that region. In the shallow water example, the grid might in general be spaced every few feet—but it could be adaptively refined to have grid points every few inches in places where there are large waves.

If the region in which higher resolution is desired remains localized over the course of the computation, then static mesh refinement can be used - in which the grid is more finely spaced in some regions than others, but maintains its shape over time.

The advantages of a dynamic gridding scheme are:

  1. Increased computational savings over a static grid approach.
  2. Increased storage savings over a static grid approach.
  3. Complete control of grid resolution, compared to the fixed resolution of a static grid approach, or the Lagrangian-based adaptivity of smoothed particle hydrodynamics.
  4. Compared to pre-tuned static meshes, the adaptive approach requires less detailed a priori knowledge on the evolution of the solution.
  5. The computational costs inherit properties of the physical system. [6]

In addition, the AMR methods have been developed and applied to a wide range of fluid mechanics problems, including two-phase flows, [7] fluid-structure interactions, [8] and wave energy converters. [9]

Related Research Articles

<span class="mw-page-title-main">Computational fluid dynamics</span> Analysis and solving of problems that involve fluid flows

Computational fluid dynamics (CFD) is a branch of fluid mechanics that uses numerical analysis and data structures to analyze and solve problems that involve fluid flows. Computers are used to perform the calculations required to simulate the free-stream flow of the fluid, and the interaction of the fluid with surfaces defined by boundary conditions. With high-speed supercomputers, better solutions can be achieved, and are often required to solve the largest and most complex problems. Ongoing research yields software that improves the accuracy and speed of complex simulation scenarios such as transonic or turbulent flows. Initial validation of such software is typically performed using experimental apparatus such as wind tunnels. In addition, previously performed analytical or empirical analysis of a particular problem can be used for comparison. A final validation is often performed using full-scale testing, such as flight tests.

<span class="mw-page-title-main">Smoothed-particle hydrodynamics</span> Method of hydrodynamics simulation

Smoothed-particle hydrodynamics (SPH) is a computational method used for simulating the mechanics of continuum media, such as solid mechanics and fluid flows. It was developed by Gingold and Monaghan and Lucy in 1977, initially for astrophysical problems. It has been used in many fields of research, including astrophysics, ballistics, volcanology, and oceanography. It is a meshfree Lagrangian method, and the resolution of the method can easily be adjusted with respect to variables such as density.

Numerical relativity is one of the branches of general relativity that uses numerical methods and algorithms to solve and analyze problems. To this end, supercomputers are often employed to study black holes, gravitational waves, neutron stars and many other phenomena described by Einstein's theory of general relativity. A currently active field of research in numerical relativity is the simulation of relativistic binaries and their associated gravitational waves.

<span class="mw-page-title-main">Mesh generation</span> Subdivision of space into cells

Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. Mesh cells are used as discrete local approximations of the larger domain. Meshes are created by computer algorithms, often with human guidance through a GUI, depending on the complexity of the domain and the type of mesh desired. A typical goal is to create a mesh that accurately captures the input domain geometry, with high-quality (well-shaped) cells, and without so many cells as to make subsequent calculations intractable. The mesh should also be fine in areas that are important for the subsequent calculations.

<span class="mw-page-title-main">Meshfree methods</span> Methods in numerical analysis not requiring knowledge of neighboring points

In the field of numerical analysis, meshfree methods are those that do not require connection between nodes of the simulation domain, i.e. a mesh, but are rather based on interaction of each node with all its neighbors. As a consequence, original extensive properties such as mass or kinetic energy are no longer assigned to mesh elements but rather to the single nodes. Meshfree methods enable the simulation of some otherwise difficult types of problems, at the cost of extra computing time and programming effort. The absence of a mesh allows Lagrangian simulations, in which the nodes can move according to the velocity field.

<span class="mw-page-title-main">Bram van Leer</span> Dutch mathematician

Bram van Leer is Arthur B. Modine Emeritus Professor of aerospace engineering at the University of Michigan, in Ann Arbor. He specializes in Computational fluid dynamics (CFD), fluid dynamics, and numerical analysis. His most influential work lies in CFD, a field he helped modernize from 1970 onwards. An appraisal of his early work has been given by C. Hirsch (1979)

Computational magnetohydrodynamics (CMHD) is a rapidly developing branch of magnetohydrodynamics that uses numerical methods and algorithms to solve and analyze problems that involve electrically conducting fluids. Most of the methods used in CMHD are borrowed from the well established techniques employed in Computational fluid dynamics. The complexity mainly arises due to the presence of a magnetic field and its coupling with the fluid. One of the important issues is to numerically maintain the (conservation of magnetic flux) condition, from Maxwell's equations, to avoid the presence of unrealistic effects, namely magnetic monopoles, in the solutions.

The material point method (MPM) is a numerical technique used to simulate the behavior of solids, liquids, gases, and any other continuum material. Especially, it is a robust spatial discretization method for simulating multi-phase (solid-fluid-gas) interactions. In the MPM, a continuum body is described by a number of small Lagrangian elements referred to as 'material points'. These material points are surrounded by a background mesh/grid that is used to calculate terms such as the deformation gradient. Unlike other mesh-based methods like the finite element method, finite volume method or finite difference method, the MPM is not a mesh based method and is instead categorized as a meshless/meshfree or continuum-based particle method, examples of which are smoothed particle hydrodynamics and peridynamics. Despite the presence of a background mesh, the MPM does not encounter the drawbacks of mesh-based methods which makes it a promising and powerful tool in computational mechanics.

<span class="mw-page-title-main">Volume of fluid method</span> Free-surface modelling technique

In computational fluid dynamics, the volume of fluid (VOF) method is a free-surface modelling technique, i.e. a numerical technique for tracking and locating the free surface. It belongs to the class of Eulerian methods which are characterized by a mesh that is either stationary or is moving in a certain prescribed manner to accommodate the evolving shape of the interface. As such, VOF is an advection scheme—a numerical recipe that allows the programmer to track the shape and position of the interface, but it is not a standalone flow solving algorithm. The Navier–Stokes equations describing the motion of the flow have to be solved separately. The same applies for all other advection algorithms.

In computational fluid dynamics, the immersed boundary method originally referred to an approach developed by Charles Peskin in 1972 to simulate fluid-structure (fiber) interactions. Treating the coupling of the structure deformations and the fluid flow poses a number of challenging problems for numerical simulations. In the immersed boundary method the fluid is represented in an Eulerian coordinate system and the structure is represented in Lagrangian coordinates. For Newtonian fluids governed by the Navier–Stokes equations, the fluid equations are

hp-FEM is a generalization of the finite element method (FEM) for solving partial differential equations numerically based on piecewise-polynomial approximations. hp-FEM originates from the discovery by Barna A. Szabó and Ivo Babuška that the finite element method converges exponentially fast when the mesh is refined using a suitable combination of h-refinements and p-refinements .The exponential convergence of hp-FEM has been observed by numerous independent researchers.

<span class="mw-page-title-main">Phillip Colella</span> American mathematician

Phillip Colella is an American applied mathematician and a member of the Applied Numerical Algorithms Group at the Lawrence Berkeley National Laboratory. He has also worked at Lawrence Livermore National Laboratory. He is known for his fundamental contributions in the development of mathematical methods and numerical tools used to solve partial differential equations, including high-resolution and adaptive mesh refinement schemes. Colella is a member of the US National Academy of Sciences.

The Sidney Fernbach Award established in 1992 by the IEEE Computer Society, in memory of Sidney Fernbach, one of the pioneers in the development and application of high performance computers for the solution of large computational problems as the Division Chief for the Computation Division at Lawrence Livermore Laboratory from the late 1950s through the 1970s. A certificate and $2,000 are awarded for outstanding contributions in the application of high performance computers using innovative approaches. The nomination deadline is 1 July each year.

<span class="mw-page-title-main">Computational astrophysics</span> Methods and computing tools developed and used in astrophysics research

Computational astrophysics refers to the methods and computing tools developed and used in astrophysics research. Like computational chemistry or computational physics, it is both a specific branch of theoretical astrophysics and an interdisciplinary field relying on computer science, mathematics, and wider physics. Computational astrophysics is most often studied through an applied mathematics or astrophysics programme at PhD level.

A mesh is a representation of a larger geometric domain by smaller discrete cells. Meshes are commonly used to compute solutions of partial differential equations and render computer graphics, and to analyze geographical and cartographic data. A mesh partitions space into elements over which the equations can be solved, which then approximates the solution over the larger domain. Element boundaries may be constrained to lie on internal or external boundaries within a model. Higher-quality (better-shaped) elements have better numerical properties, where what constitutes a "better" element depends on the general governing equations and the particular solution to the model instance.

Grid or mesh is defined as smaller shapes formed after discretisation of geometric domain. Mesh or grid can be in 3- dimension and 2-dimension. Meshing has applications in the fields of geography, designing, computational fluid dynamics. and many more places. The two-dimensional meshing includes simple polygon, polygon with holes, multiple domain and curved domain. In three dimensions there are three types of inputs. They are simple polyhedron, geometrical polyhedron and multiple polyhedrons. Before defining the mesh type it is necessary to understand elements.

<span class="mw-page-title-main">Gerris (software)</span> Computer Software

Gerris is computer software in the field of computational fluid dynamics (CFD). Gerris was released as free and open-source software, subject to the requirements of the GNU General Public License (GPL), version 2 or any later.

Marsha J. Berger is an American computer scientist. Her areas of research include numerical analysis, computational fluid dynamics, and high-performance parallel computing. She is a Silver Professor (emeritus) of Computer Science and Mathematics in the Courant Institute of Mathematical Sciences of New York University. She is Group Leader of Modeling and Simulation in the Center for Computational Mathematics at the Flatiron Institute.

Joseph E. Oliger was an American computer scientist and professor at Stanford University. Oliger was the co-founder of the Science in Computational and Mathematical Engineering degree program at Stanford, and served as the director of the Research Institute for Advanced Computer Science.

References

  1. Berger, Marsha J.; Oliger, Joseph (1984). "Adaptive mesh refinement for hyperbolic partial differential equations" (PDF). Journal of Computational Physics. 53 (3): 484–512. doi:10.1016/0021-9991(84)90073-1. Archived (PDF) from the original on July 22, 2021. Retrieved 2021-07-22.
  2. Berger, Marsha J.; Colella, Philipp (1989). "Local adaptive mesh refinement for shock hydrodynamics" (PDF). Journal of Computational Physics. 82 (1): 64–84. Bibcode:1989JCoPh..82...64B. doi:10.1016/0021-9991(89)90035-1.
  3. Klein, Richard (1999). "Star formation with 3-D adaptive mesh refinement: the collapse and fragmentation of molecular clouds". Journal of Computational and Applied Mathematics. 109 (1–2): 123–152. doi: 10.1016/S0377-0427(99)00156-9 .
  4. Huang, Weizhang; Russell, Robert D. (2010). Adaptive Moving Mesh Method. Springer. ISBN   978-1-4419-7916-2.
  5. Khattri, Sanjay Kumar (2007). "Grid generation and adaptation by functionals". Computational & Applied Mathematics. 26 (2): 235–249. Retrieved 2021-07-22.
  6. Popinet, Stéphane (2015). "A quadtree-adaptive multigrid solver for the Serre–Green–Naghdi equations". Journal of Computational Physics. 302: 336–358. Bibcode:2015JCoPh.302..336P. doi:10.1016/j.jcp.2015.09.009 . Retrieved 2021-07-22.
  7. Zeng, Yadong; Xuan, Anqing; Blaschke, Johannes; Shen, Lian (2022). "A parallel cell-centered adaptive level set framework for efficient simulation of two-phase flows with subcycling and non-subcycling". Journal of Computational Physics. 448. Elsevier: 110740. Bibcode:2022JCoPh.44810740Z. doi: 10.1016/j.jcp.2021.110740 . S2CID   244203913.
  8. Zeng, Yadong; Bhala, Amneet; Shen, Lian (2022). "A subcycling/non-subcycling time advancement scheme-based DLM immersed boundary method framework for solving single and multiphase fluid--structure interaction problems on dynamically adaptive grids". Computers & Fluids. 238. Elsevier: 105358. doi: 10.1016/j.compfluid.2022.105358 . S2CID   247369961.
  9. Yu, Yi-Hsiang; Li, Ye (2013). "Reynolds-Averaged Navier--Stokes simulation of the heave performance of a two-body floating-point absorber wave energy system". Computers & Fluids. 73. Elsevier: 104–114. doi:10.1016/j.compfluid.2012.10.007.

See also