What are the basic principles behind generating a moving mesh?

Question

I am interested in implementing an moving mesh for an advection-diffusion problem. Adaptive Moving Mesh Methods gives a good example of how to do this for Burger's equation in 1D using finite-difference. Would someone be able to offer a worked example on solving the 1D advection-diffusion equation using finite-difference with a moving mesh?

For example, in conservative form the equation is,

$$ u_t = (a(x)u + du_x)_x $$

where $a(x)$ is the velocity (a function of space). The initial conditions $u(0,x)$ could specify (for example) a flow species moving from left to right (e.g. along a pipe) where the initial condition has a sharp gradient.

How should the equidistribution problem for the moving mesh be solved (possibly with De Boor's algorithm or other approach)? I wish to implement this myself in Python so if your answer can be readily translated into code all the better!

---

Old question prior to bounty

1. What are the basic approaches for generating an adaptive mesh based on properties of the system? Should I use flux as a measure of where the gradients are large?
2. Because I seek an iterative (time sweep) solution. I imagine it is important to interpolate from the old grid to the new grid, what is the usual approach?
3. I would be really interested to see a worked example for a simple problem (like the advection equation).

A bit of background about the specifics of the problem. I am simulating a 1D coupled system of equation,

$ \frac{\partial u}{\partial t} = a_u\frac{\partial^2 u}{\partial x^2} + b_u\frac{\partial u}{\partial x} + f_u(x,u,v,w) \\ \frac{\partial v}{\partial t} = a_v\frac{\partial^2 v}{\partial x^2} + b_v\frac{\partial v}{\partial x} + f_v(x,u,v,w) \\ \frac{\partial w}{\partial t} = a_u\frac{\partial u}{\partial x} +a_v\frac{\partial v}{\partial x} + f_w(x,u,v,w) \\ $

The set of equations describe a two species advection-diffusion problem where the third equation couples to the other two. The solution change rapidly near the centre of my grid, see below (these are illustration not calculations),

Notice that log scale on the lower graph, the solutions for $u$ and $v$ vary over orders of magnitude. On the upper graph ($w$) there is a discontinuity at the centre. I am solving the above system with an adaptive upwind where the discretization can adapt from central to upwind dominated depending on local value of Péclet number. I am solving the system implicitly with trapezoidal integration in time ("Crank-Nicolson").

I am interested in applying an adaptive grid to this problem. I think it is important because otherwise details of the shape peak (the $w$) parameter could be lost. Unlike this question, I would like to apply, a hopefully simply, algorithm for mesh generation.

As this is an advection-diffusion problem, one could imagine an adaptive mesh scheme based on the fluxes of $u$ and $v$ at the cell boundaries. As this would indicate where the value is changing rapidly. The peak of the $w$ also corresponds to the where the flux are the largest.

Answer 1

An adaptive grid is a grid network that automatically clusters grid points in regions of high flow field gradients; it uses the solution of the flow field properties to locate the grid points in the physical plane. The adaptive grid evolves in steps of time in conjunction with a time-dependent solution of the governing flow field equations, which computes the flow field variables in steps of time. During the course of the solution, the grid points in the physical plane move in such a fashion to ‘adapt’ for regions of large flow field gradients. Hence, the actual grid points in the physical plane are constantly in motion during the solution of the flow field, and become stationary only when the flow solution approaches a steady state.

Grid adaptation is used for both steady and unsteady type of problems. In case of steady flow problems grid is adapted after predetermined number of iterations and grid adaptation will stop at the point when solution is converged. In case of time accurate solutions the grid point motion and refinement are performed in conjunction with time accurate solution of the physical problem. This requires time accurate coupling of PDEs of the physical problem and those describing the grid movement or grid adaptation.

For the computations of newer configurations dependence on best practice guidelines for mesh generation and previous experience leaves the door open to large amounts of numerical error. Grid adaptation methods can produce substantial improvements in solution quality and promises better results because no limitations exist that define the limit on grid resolution that can be attained.

There are three basic types of grid adaptation techniques, that are $h$-method, $r$-method and $p$-method. There are some some mixed types of approaches one can find, such as $rp$-adaptation or $hp$-adaptation. Out of this $r$ and $h$ type of grid adaptation techniques are more popular in finite volume and finite difference schemes.

$h$ type:-

The $h$ method involves automatic refinement or coarsening of the spatial mesh based on a posteriori error estimates or error indicators.

$r$ type:-

Instead of making local topological changes to the mesh and its connectivity, r-adaptive methods make local changes to the resolution by moving the locations of a fixed total number of mesh points.

$p$ type:-

Very much popular method of grid adaptation in finite element approach rather than finite volume or finite element method. It reduces the error in the solution by enrichment of the polynomial of interpolating functions with the same geometric element order.Here no new mesh, geometry to be calculated and another advantage of this method is that it can better approximate irregular or curved boundaries with less sensitivity to aspect ratio and skew. Because of the this its very famous in structural application.

$Driving-sources-of-grid-adaptation$

$1. Feature-based-adaptation$ Feature based approximately largely used approach of grid adaptation employs feature of solution as driving force for grid adaptation. These often uses features of the solution such as solution gradients and solution curvature. Flow regions that have large solution gradients are resolved with more points and regions of minimal significance are coarsened. This leads to refinement of the region which is physically specific such as boundary layer, shocks,separation lines, stagnation points, etc. In some cases, gradient-based refinement can actually increase the solution error so there are some issues regarding feature based adaptation like robustness and others.

$2.Truncation-error-based-adaption$ Truncation error is the difference between partial differential equation and its discretized equation. Truncation error is more suitable approach to find where adaptation should occur. General concept behind truncation error based adaptation is to equidistribute the error over the domain of simulation to reduce total discretization error. For simple equations evaluation of truncation error is easiest job but for complex schemes its difficult so different approach is needed for that purpose. For simple discretization schemes, the truncation error can be computed directly. For more complex schemes where direct evaluation of the truncation is difficult, an approach for estimating the truncation error is needed.

$3.Adjoint-based-adaptation$ Next promising approach is the adjoint approach. Its very good in estimating the local contribution of each cell or element to the discretization error in any solution functionals of interest such as lift, drag, and moments. So it is useful in targeted grid adaptation as per requirement of the solution so thats its also called as goal oriented adaptation.

All the best!

$References:-$

[1] Fidkowski Krzysztof J. and Darmofal David L. Review of output-based error es-timation and mesh adaptation in computational fluid dynamics. AIAA Journal, 49:673–694, 2011.

[2] John Tannehill Richard Pletcher and Dale Anderson. Computational fluid mechanics and heat transfer. Taylor & Francis, 1997.

[3] J. D. Jr. Anderson. Computational fluid dyanamics: The basics with applications.McGraw Hill Inc., 1995.

[4] Roy Christopher J. Strategies for driving mesh adaptation in cfd. In 47th AIAA Aerospace Sciences Meeting Including The New Horizons Forum and Aerospace Ex- position, 2009.

[5] McRae Scott D. r-refinement grid adaptation algorithms and issues. Computatioanal methods in applied mechanics and engineering, 189:1161–1182, 2000.

[6] Ivanenko Sergey A. Azarenok Boris N. and Tang Tao. Adapative mesh redistribution method based on godunovs scheme. Comm. math. sci., 1:152–179.

[7] Ahmadi Majid and Ghaly Wahid S. Simulation of inviscid flow in cascades using a finite volume method with solution adaptation. In CASI 6th Aerodynamics Sympo- sium, 1997.

[8] Jasak H. and Gosman A. D. Automatic resolution control for the finite-volum e m ethod, part 1: a-posteriori error estimates. Numerical Heat Transfer,Taylor & Francis, 38:237–256, 2000.

[9] Jasak H. and Gosman A. D. Automatic resolution control for the finite-volum e m ethod, part 2: Adaptive mesh refinement and coarsening. Numerical Heat Trans- fer,Taylor & Francis, 38:257–271, 2000.

[10] Thompson David S. Soni Bharat K., Koomullil Roy and Thornburg Hugh. Solution adaptive grid strategies based on point redistribution. Computatioanal methods in applied mechanics and engineering, 189:1183–1204, 2000.

[11] Venditti David A. and Darmofal David L. Adjoint error estimation and grid adap- tation for functional outputs: Application to quasi-one-dimensional flow. Journal of Computational Physics, 164:204–227, 2000.

[12] Balasubramanian R. and Newman J. C. Comparison of adjoint-based and feature- based grid adaptation for functional outputs. International journal for numerical methods in fluids, 53:1541–1569, 2007.

[13] Hartmann Ralf. Error estimation and adjoint-based adaptation in aerodynamics. In European Conference on Computational Fluid Dynamics, 2006.

Answer 2

I was (still am) looking for good answers for this. I work with multi-level adaptive grids where I use some sort of criterion for refinement. Folks doing FEM enjoy, rather cheap (computationally), rigorous error estimates that they use as refinement criterion. For us doing FDM/FVM, I have not had luck finding any such estimates.

In this context, if you want to be rigorous about refinement, i.e refine based on some estimation of the actual error, your (almost) only choice is Richardson Extrapolation. This is what was, for instance, used by Berger and Oliger (1984) for their block-structured, AMR hyperbolic solver. The methodology is general in the sense that you can use Richardson Extrapolation for virtually any problem. The only issue with it is that it is expensive, especially for transient problems.

Other than Richardson Extrapolation, all other criterion (in my humble opinion) are just ad hoc. Yes you can set a certain threshold on a "quantity of interest" and refine based on that. You could use fluxes or derivatives of some quantity to alert some large gradient and use that. Or if you are tracking an interface, you could refine based on how close you are to the interface. All of these are very cheap, of course, but there is nothing rigorous about them.

As for interpolation between grids, you generally need something that is at least as accurate as you solver. Sometimes it is possible to build interpolations that satisfy certain properties, e.g. conserve mass or are convex thus do not introduce new extrema. I have noted that this last property is sometimes very important to the stability of the overall scheme.

Answer 3

If it is indeed 1D then you probably won't need any adaptive mesh here, for such a simple problem you can probably resolve all you need with a static grid, with a computing power of a modern workstation. But it is a perfectly reasonable strategy, in the process of time-integration, to identify periodically areas where the numerical resolution is stressed, add grid points there (and remove grid points from over-resolved areas), and interpolate to the new grid. But this should not be done too frequently because interpolation can be costly, and it would add numerical error in the overall calculation.