
[Sponsors] 
February 11, 2005, 12:45 
Compact schemes

#1 
Guest
Posts: n/a

Does anyone know any papers on the implicit schemes for compact finite differences methods? Basically I am thinking to make my code implicit, but my code uses the Lele' scheme for the spatial derivatives...and so the procedure is not staightforward.


February 11, 2005, 13:36 
Re: Compact schemes

#2 
Guest
Posts: n/a

First of all, I'm going to assume that you're talking about finitedifferences on a uniform grid. Proceeding under these assumptions, let's talk about centered firstderivative operators. The basic stencil looks like this:
... gamma*(f'_{i+3}  f'_{i3}) + beta*(f'_{i+2}  f'_{i2}) + alpha*(f'_{i+1}  f'_{i1}) + f'_{i} = a*(f_{i+1}  f_{i1}) + b*(f_{i+2}  f_{i2}) + c*(f_{i+3}  f_{i3}) + ... where f and f' are the function you want to differentiate and the derivative. Compact derivatives have at least one of the alpha, beta, or gamma coefficients not equal to zero. The benefit of using compact operators is that they have better highwavenumber performance. The downside is that they are much more expensive to implement. Don't get caught up in the hype of compact derivative operators unless that high wavenumber information is critical and the grid cannot be increased. The trick is to compare methods at equal cost. Since explicit stencils are much cheaper to run, the grid can be increased a bit while maintaining similar operations counts. Instead of using 4th or 6thorder compact operators with alpha \= 0 but beta=gamma=0, set alpha=0 and use 6th or 8thorder explicit stencils. 4thorder explicit a=2/3, b=1/12, c=0, d=0 6thorder explicit a=3/4, b=3/20, c=1/60, d=0 8thorder explicit a=4/5, b=1/5, c=4/105, d=1/280 The stencils must be closed on the boundaries. The fourthorder needs 2 points closed on each side, the sixth needs 3 etc. Close them like this 3,34E3,3 3,3,46E4,3,3 3,3,4,68E6,4,3,3 where xE is the interior operator. The 3rdorder operators are (left side): f'_{1} = [1/(6*Dx)]*[11*f_{1} + 18*f_{2}  9*f_{3} + 2*f_{4}] f'_{2} = [1/(6*Dx)]*[2*f_{1}  3*f_{2} + 6*f_{3}  f_{4}] Good luck!! 

February 11, 2005, 17:37 
Re: Compact schemes

#3 
Guest
Posts: n/a

Hi. Thank you very much for your brilliant response, but maybe I didn't explain my problem very well. My code is already running by compact schemes but for the time being it is explicit in "time"; I want to make it implicit in time continuing to use the Lele scheme which to my experience is one of the best and not much time consuming. However I have been thinking about my issue, and my conclusion is that it would be useless to do such a modification because the final matrix to invert would be full, and of dimension (5*N) where N is the number of grid on the direction considerd and 5 is state vector. I would think that the real point of weakness for this schemes is exactly this. So I believe I'll forget this idea, and probably move to Multigrid. I would appreciate your further considerations. Thank you


February 11, 2005, 18:49 
Re: Compact schemes

#4 
Guest
Posts: n/a

Going implicit in both time and space is going to be a challenge. I'd still drop the compact derivatives. Do a test comparing your compact derivs. to explicit derivs. with the explicit ones being 2 orders higher. As to implicit in time, the analog to finite difference in time is the BDF family of methods. Here's a paper comparing several popular implicit methods for the NavierStokes Eqns.
http://fun3d.larc.nasa.gov/papers/carpenter.pdf You want an Lstable method with error control. Astable isn't good enough. BDF3 doesn't work well with NavierStokes because of a small region of instability where small convective eigenvalues live. 

February 12, 2005, 09:54 
Re: Compact schemes

#5 
Guest
Posts: n/a

Definitely if the integration in time is explicit, thre is not any competition between compact and not compact explicit finite difference scemes. To achieve the same accuracy the second ones require an higher grid and the CFL condition would impose a worse time step restriction. So , in this case, compact are better than not compact.
The interesting question is to see what happen when the time integrator is implicit. Maybe non compact spatial derivatives coupled with implicit time integration may be faster than an explicit in time with compact spatial derivatives, keeping the same accuracy. But the answer will always depend on the dynamics to simalute. And I do not have time to make these experiment. Bye 

February 12, 2005, 23:46 
Re: Compact schemes

#6 
Guest
Posts: n/a

"Definitely if the integration in time is explicit, thre is not any competition between compact and not compact explicit finite difference scemes. To achieve the same accuracy the second ones require an higher grid and the CFL condition would impose a worse time step restriction. So , in this case, compact are better than not compact."
================================================== ===== While many may believe this, I don't think it is actually true for most circumstances. The measure here is computational cost, for whatever you need to compute, at fixed accuracy. Compare 8thorder explicit versus 6thorder compact. The CFL of the explicit deriv. is 15% greater than the 6thorder tridiagonal deriv. . A collegue of mine ran these two operators and found the 8thorder was 15 times faster. While I believe that's probably too much, the difference is big. The 8thorder operator is actually more accurate for wavenumbers below 0.55 ( the grid holds 0 <> Pi). It is only at wavenumbers beyond maybe 1.4 where the 6thorder compact is clearly better. I'd just grid up 15%25% in each direction unless I was memorybound and the explicit code would likely be just as accurate and faster. Now, redo this thought experiment on a parallel machine. Good luck with your Thomas algorithm on a MPP machine. 

February 13, 2005, 17:59 
Re: Compact schemes

#7 
Guest
Posts: n/a

Well, maybe what you say it's true. 15 times faster is absolutely wrong! Also, the Thomas is O(N) as an ordinary explicit method ...so I don't see how it can be so slow. As regard the parallel machine, all you need is swap, and that's it. Bye


February 13, 2005, 19:29 
Re: Compact schemes

#8 
Guest
Posts: n/a

"15 times faster is absolutely wrong!"
This is "absolutely" what my collegue told me happened using a governmentfunded DNS code in 1995 using a Cray J90. I'm not going to say that his results are the best showing compact methods could make but he's a smart guy. I walk away from his comments thinking there is a substantial workload penalty to tridiagonal deriv. operators. "Thomas is O(N)" And? "As regard the parallel machine, all you need is swap, and that's it." Try to take a derivative across one direction using, say, 2048 processers. Explicit methods will gain an enormous additional advantage over compact methods. Again, the name of the game is relative computational cost at fixed accuracy. 

February 14, 2005, 10:46 
Re: Compact schemes

#9 
Guest
Posts: n/a

Consider perhaps the sense of the question.
When one uses compact schemes like Lele schemes, this is because one wants to access with a high precision to small spatial scales (like quasispectral turbulence simulation). Carrying implicit time integration, which is coarse, has no sense because the interests are on the temporal scales of the structures to be studied as well. That is Physics which dictates what must be solved explicitely and what must be solved implicitely. 

February 14, 2005, 12:07 
Re: Compact schemes

#10 
Guest
Posts: n/a

Although one could argue that the "physics" dictates that the time integration should be implicit in order to respect the nature of the NavierStokes equations. After all the stability restriction on explicit methods arises because of the mistreatment of the diffusion terms in an explicit integration.


February 14, 2005, 15:39 
Re: Compact schemes

#11 
Guest
Posts: n/a

Temporal resolution of any physical phenomena may be achieved at some particular temporal integration error tolerance. It may be that some phenomena requires that the local integration error must be 10^(3) while another only requires 10^(2). Pick your favorite phenomena and figure out what resolution is required. It may be that an explicit time integrator cannot reach the corresponding step size because it places the integrator outside its stability boundary. Plot Log(local error) vs. step size for the explicit method. Extrapolate the line to the local error you want and compare that step size to the one corresponding to the stability boundary. That ratio is a measure of how stability bound you are. If possible, do the same with an implicit method. What is the step size for the implicit method at the desired local error tolerance? For NavierStokes, the implicit method needs to deliver between 10100 times the step size, while maintaining proper error, of the explicit method to be worth the aditional cost.
The thing you do not want to do is to run the implicit method at the largest stepsize that the stability and nonlinear solver can handle. This situation usually corresponds to such high error that the order property of the integrator is not even apparent. Of course, none of this would be possible without temporal error estimators and step size controllers!!! 

February 15, 2005, 05:40 
Re: Compact schemes

#12 
Guest
Posts: n/a

There is more to this than just temporal accuracy  there is very little point in being accurate in time but not resolving the spatial scales relevant to the timestep. Correct application of the boundary conditions is also important, especially for resolving near wall instability waves, since misapplication of the noslip condition can cause significant errors (higher than the temporal discretization error). The most natural way of acheiving both accuracy in time and correct application of the boundary conditions for the NavierStokes equations is to use CrankNicolson which ensures that the boundary conditions are satisfied on the "new" timestep and respects the parabolic nature of the equations.


February 15, 2005, 17:29 
Re: Compact schemes

#13 
Guest
Posts: n/a

I certainly agree that temporal resolution without spatial resolution isn't worth a whole lot. A key thing that is inevitably omitted in these types of discussion is estimating ones temporal and spatial errors and then acting on this information when it is not acceptable. The vast majority of the CFD community does frightfully little to access their errors. All I get is blank stares from people when I say this. It is foreign to the culture that most CFDers were raised in. People assume that because their implicit method is stable that all is well and good. Boundary conditions are also important, as you said. From the comments on this board, many CFD packages could offer far better BCs than they do. There is also aliasing error principally from the convective operator. Is anyone using a skewsymmetric formulation to minimize this? My focus on time was based on the thread originators comments.
Why is CrankNicolson special? The integration part is the trapezoidal rule which is order 2, stageorder 2, and only Astable. Because the order and stageorder are the same, the physical boundary conditions cannot locally diminish the temporal convergence rate as it can with explicit RungeKutta methods. Secondorder in space, by itself, is OK. However, like most methods, the scheme is implemented with no error control tools and no useful way to remove unresolved, highwavenumber garbage that piles up as the calculation proceeds. The worse the resolution, the harder the convective operator pumps highwavenumber garbage to the high end of the spectrum. 

February 16, 2005, 05:59 
Re: Compact schemes

#14 
Guest
Posts: n/a

I agree pretty much with what you say.
The reason why I, and many applied mathematicians like me, prefer CrankNicolson for parabolic equations is simply that, for 2nd order centred differences the discretized equations possess properties akin to the continous equations; i.e. it creates a 2nd order difference equation in space and a 1st order difference equation in time (just like the canonical parabolic equation u_t = u_xx) with optimal(ish) accuracy. Furthermore for parabolic equations time is the only characteristic direction with space acting in an elliptic fashion. CrankNicolson (and implicit methods in general) respect this  hence the need for a matrix inversion. If your problem is hyperbolic and not parabolic you should choose a scheme that respects the domains of dependence and influence of the problem  this, in general, rules out the use of implicit methods! At the end of the day, in my opinion, you need to ensure that to your required degree of accuracy (graphical?) that the effects of changing the timestep and grid resolution do not effect your solution. 

Thread Tools  
Display Modes  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
time stepping schemes for compressible DNS/LES  shyamdsundar  Main CFD Forum  0  January 15, 2010 00:15 
High order compact finite difference schemes  Mikhail  Main CFD Forum  6  August 5, 2003 10:36 
Compact finite difference schemes  Tom Clay  Main CFD Forum  4  November 28, 2002 09:59 
TVD Schemes  Matt Umbel  Main CFD Forum  1  January 25, 2000 05:21 
Higherorder bounded convection schemes for pure advection with discontinuity  Anthony  Main CFD Forum  3  June 13, 1999 02:36 