complexity of flux limiter techniques

Question

My question is not related to any particular problem, rather, I am looking at the equations of the form $$u_t+c(t,x)u_x=0$$ and attempt to solve it numerically. According to http://en.wikipedia.org/wiki/Flux_limiter I can apply Flux limiter method, say with Van Leer limiter function, and obtain a numerical method for the equation.

Flux limiter technique is for the discretization in space, I have to make a choice for the time. I compare explicit, implicit, and central difference. I would think explicit would have have some sort of stability/CFL condition which I don't like. Thus, I can use the other two. The latter is preferred due to a bettor error of second order. Thus, my first question is what type of time discretization is used in practice and why? Some basic intuition is sufficient to me.

Second, in either one of the implicit/central case, if I write the iteration explicitly for each time step, it requires the performance of Newton's iterations, simply because the equation is not linear anymore. However, in some cases there are only a few iterations are sufficient to obtain a solution provided a good initial guess. Since this is a nonlinear method the complexity is larger relative to a linear method, say implicit Euler in time and one sided difference in space. But, if there are only a few iterations to solve the nonlinear system to be performed, isn't comparable to the linear numerical methods in complexity? Thus, I want to know how complex those limiter methods and can they compete with linear methods in complexity? Or there is something else apart from Newton's iterations that make flux limiter methods more complex? Why one would like to have a linear method to solve an equation compare to non-linear?

Answer 1

If you only consider linear equations, you can use rather simple methods. Lax-Wendroff is a nice example of a second order method, but you could even use an upwind-based method, which is first order and diffusive.

The problem with hyperbolic conservation laws comes with nonlinearity. So let's consider $u_t + f(u)_x=0$, which means $f^\prime=c$ in your example. If $c$ is constant (ie. $f$ is linear), you have linear transport, so your initial data will be transported with velocity $c$. For nonlinear $f$, however, even smooth initial data can lead to discontinuities. Burger's equation is a classic example: $u_t+uu_x=0$ or $u_t+\frac12(u^2)_x=0$. If you look at the characteristics, you see what happens. Suppose we have piecewise constant initial data. If their value on left is greater than on the right, the part on the left travels to the right faster than the rest and this will end up in a shock. If it's the other way around, you have a rarefaction wave where both parts travel away from each other. But shocks are the greater problem as far as high order is concerned. Near shocks or steep gradients, order of accuracy doesn't make sense because it involves derivatives (Taylor series). I already mentioned that the upwind method is diffusive, but it can deal with shocks. Higher order ($\ge2$) methods develop spurious oscillations. This is why people invented flux limiters and the like. You use your high order method where possible and drop to the safe first order where necessary. There's a lot of theory out there. One property many people want to have is TVD (total variation diminishing). Since you already mentioned the wikipedia site, you have probably seen that. Not all of those flux limiters are TVD, but of those mentioned in that article, superbee is optimal in the sense that it allows the highest possible use of the high order method. Van Leer and Osher are other widely used limiters. If you want to go beyond second order, you should take a look at http://en.wikipedia.org/wiki/MUSCL_scheme .

As far as your question about implicit schemes is concerned, from the theory of nonlinear stability, you usually get a CFL-like condition anyway. The only unconditionally stable (in the strong, nonlinear sense) is backward Euler. There is an excellent book on "Strong Stability Preserving Time Discretizations" by Gottlieb, Ketcheson and Shu. This is the kind of method you want to use for nonlinear problems. The book contains a theorem saying no Runge-Kutta method of order greater than one is unconditionally SSP. Plus, the effective CFL number is probably bounded by two, so you really wouldn't gain anything.

You see, nonlinear hyperbolic equations are a lot different from what you know about simple ODEs. If you want to learn more, I recommend the book "Finite Volume Methods for Hyperbolic Problems" by Randall J. LeVeque. It covers the theory as well as a wide range of numerical methods (including flux limiters).

Answer 2

As the reviewers already suggested, it would be nice to keep things in a context rather then speaking in general. Still, I believe I could comment on the questions. Even if the implicit solution approach is also not clear (matrix-free, automatic differentiation, lagged Jacobian, or nonlinear-gs with local Newton iterations, Newton-MG, preconditioning?) I would give some insight for flux limiters. They are usually use to track the fields that exhibit abrupt changes like shocks or interfaces in general. Apart selection of the type of the limiters, there are two main steps: calculation of r and calculation of f(r). Starting from the latter, f is usually nonlinear - that has different complexity depending on the selected limiter. Some are simpler when considered in the Jacobian, some not. Even in some cases, max-min combinations should be evaluated (which also requires different measures for CPU and GPU computing). For r, if the mesh is simple - like uniform and structured, it is most of the time straightforward to compute (might need ghost cells in finite volumes to extend the stencils). Yet, for an unstructured mesh - the neighborhood is important. The computations can be handled more efficiently if the grid data is well sorted, still some geometric interpolations will be needed to calculate r (there are papers on that, refer the ones given in An Introduction to Computational Fluid Dynamics: The Finite Volume Method chapters 5 & 11). From my personal experience, I would focus on van Leer and Sweby and condense the study on the complexity.