# complexity of flux limiter techniques

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?

• Are you asking about steady-state simulation when using flux limiters? Are you familiar with why limiters are needed for problems with sharp features like shocks? Please clarify the question. Mar 6, 2013 at 5:46
• Usually such methods are explicit. Mar 6, 2013 at 12:21
• You should clarify your question. Perhaps you can include some details of your problem. Mar 6, 2013 at 12:21
• Jed, David, vanCompute, I have restated the question. I hope it is more precise now. Mar 10, 2013 at 2:29
• No, it is not "precise". What discretization are you using? Why do you need to do any Newton iterations? Mar 10, 2013 at 10:08

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).

• thanks, I think I am building some understanding, especially in the case of nonlinear problems. However, is there a good reason to use the flux limiter methods for the linear case or it would be overkill? I have looked at bunch of FDM schemes for hyperbolic equations and they all have some sort of issues. This one seems to be straightforward provided the Newton's iterations converge quickly. Or I should stick with linear methods for linear problems and keep the flux limiter only to non-linear? What's the price I pay for using limiters for linear problems? Mar 20, 2013 at 23:59
• If your $c$ is constant and your initial data is smooth, you're fine without limiters. In any other cases you can run into trouble. Constant $c$ and non-smooth initial data (square wave, for example) will cause oscillations with higher order methods. First order methods have a lot of diffusion, but won't oscillate. Still, don't use implicit time integration for hyperbolic problems - it just makes no sense.
– Anke
Mar 21, 2013 at 8:45
• Anke, could you explain why implicit doesn't make sense? Midpoint discretization is more accurate but the amplification factor might be one, and in implicit case it is less than one(say compare implicit Euler in time vs. Crank-Nicholson with central difference in space), so isn't it "safer" from the stability point of view to use implicit? As far as I know there is no CFL condition either. And second, my initial data is not very smooth, so in that case I would have to turn to limiters even if the equation is linear or this is primarily for non-linear problems? Mar 23, 2013 at 0:08
• @Kamil As I mentioned in my answer, there are other problems with implicit methods for hyperbolic problems. If you are considering ODEs, you're completely right. Even for parabolic PDEs it can be better to use implicit methods because the spatial discretization often leads to stiff ODEs. But with hyperbolic problems you have to redefine stability. A stable method simply isn't enough. To handle shocks, you need "nonlinear stability" and you end up with a CFL-like condition.
– Anke
Mar 25, 2013 at 12:18

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.

• I don't look for the precise answer, just some intuition. However, for the case of the LINEAR transport equation $u_t+c(t,x)u_x=0$ with continuous but not differentiable initial data, I have a choice of methods that handle that. So, flux methods are nonlinear as they solve a nonlinear equation at each step, but are they competitive compare to other linear FDM and FEM schemes? Shall I use them in this case or shall I start with FDM? Would this nonlinearity get resolved with a few Newton's iterations so I would not even notice on the performance scale? Mar 19, 2013 at 1:22