CFD Online Logo CFD Online URL
www.cfd-online.com
[Sponsors]
Home > Forums > Main CFD Forum

Compact schemes

Register Blogs Members List Search Today's Posts Mark Forums Read

Reply
 
LinkBack Thread Tools Display Modes
Old   February 11, 2005, 11:45
Default Compact schemes
  #1
Daniel
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.
  Reply With Quote

Old   February 11, 2005, 12:36
Default Re: Compact schemes
  #2
Runge_Kutta
Guest
 
Posts: n/a
First of all, I'm going to assume that you're talking about finite-differences on a uniform grid. Proceeding under these assumptions, let's talk about centered first-derivative operators. The basic stencil looks like this:

... gamma*(f'_{i+3} - f'_{i-3}) + beta*(f'_{i+2} - f'_{i-2}) + alpha*(f'_{i+1} - f'_{i-1}) + f'_{i} = a*(f_{i+1} - f_{i-1}) + b*(f_{i+2} - f_{i-2}) + c*(f_{i+3} - f_{i-3}) + ...

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 high-wavenumber 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 6th-order compact operators with alpha \= 0 but beta=gamma=0, set alpha=0 and use 6th- or 8th-order explicit stencils.

4th-order explicit

a=2/3, b=-1/12, c=0, d=0

6th-order explicit

a=3/4, b=-3/20, c=1/60, d=0

8th-order explicit

a=4/5, b=-1/5, c=4/105, d=-1/280

The stencils must be closed on the boundaries. The fourth-order needs 2 points closed on each side, the sixth needs 3 etc. Close them like this

3,3-4E-3,3

3,3,4-6E-4,3,3

3,3,4,6-8E-6,4,3,3

where xE is the interior operator. The 3rd-order 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!!
  Reply With Quote

Old   February 11, 2005, 16:37
Default Re: Compact schemes
  #3
daniel
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

  Reply With Quote

Old   February 11, 2005, 17:49
Default Re: Compact schemes
  #4
Runge_Kutta
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 Navier-Stokes Eqns.

http://fun3d.larc.nasa.gov/papers/carpenter.pdf

You want an L-stable method with error control. A-stable isn't good enough. BDF3 doesn't work well with Navier-Stokes because of a small region of instability where small convective eigenvalues live.
  Reply With Quote

Old   February 12, 2005, 08:54
Default Re: Compact schemes
  #5
Daniel
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

  Reply With Quote

Old   February 12, 2005, 22:46
Default Re: Compact schemes
  #6
Runge_Kutta
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 8th-order explicit versus 6th-order compact. The CFL of the explicit deriv. is 15% greater than the 6th-order tridiagonal deriv. . A collegue of mine ran these two operators and found the 8th-order was 15 times faster. While I believe that's probably too much, the difference is big. The 8th-order 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 6th-order compact is clearly better. I'd just grid up 15%-25% in each direction unless I was memory-bound 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.
  Reply With Quote

Old   February 13, 2005, 16:59
Default Re: Compact schemes
  #7
daniel
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

  Reply With Quote

Old   February 13, 2005, 18:29
Default Re: Compact schemes
  #8
Runge_Kutta
Guest
 
Posts: n/a
"15 times faster is absolutely wrong!"

This is "absolutely" what my collegue told me happened using a government-funded 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.
  Reply With Quote

Old   February 14, 2005, 09:46
Default Re: Compact schemes
  #9
Guillaume
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 quasi-spectral 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.
  Reply With Quote

Old   February 14, 2005, 11:07
Default Re: Compact schemes
  #10
Tom
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 Navier-Stokes equations. After all the stability restriction on explicit methods arises because of the mistreatment of the diffusion terms in an explicit integration.
  Reply With Quote

Old   February 14, 2005, 14:39
Default Re: Compact schemes
  #11
Runge_Kutta
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 Navier-Stokes, the implicit method needs to deliver between 10-100 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!!!
  Reply With Quote

Old   February 15, 2005, 04:40
Default Re: Compact schemes
  #12
Tom
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 no-slip 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 Navier-Stokes equations is to use Crank-Nicolson which ensures that the boundary conditions are satisfied on the "new" timestep and respects the parabolic nature of the equations.
  Reply With Quote

Old   February 15, 2005, 16:29
Default Re: Compact schemes
  #13
Runge_Kutta
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 skew-symmetric formulation to minimize this? My focus on time was based on the thread originators comments.

Why is Crank-Nicolson special? The integration part is the trapezoidal rule which is order 2, stage-order 2, and only A-stable. Because the order and stage-order are the same, the physical boundary conditions cannot locally diminish the temporal convergence rate as it can with explicit Runge-Kutta methods. Second-order 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, high-wavenumber garbage that piles up as the calculation proceeds. The worse the resolution, the harder the convective operator pumps high-wavenumber garbage to the high end of the spectrum.
  Reply With Quote

Old   February 16, 2005, 04:59
Default Re: Compact schemes
  #14
Tom
Guest
 
Posts: n/a
I agree pretty much with what you say.

The reason why I, and many applied mathematicians like me, prefer Crank-Nicolson 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. Crank-Nicolson (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.

  Reply With Quote

Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
time stepping schemes for compressible DNS/LES shyamdsundar Main CFD Forum 0 January 14, 2010 23: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 08:59
TVD Schemes Matt Umbel Main CFD Forum 1 January 25, 2000 04:21
Higher-order bounded convection schemes for pure advection with discontinuity Anthony Main CFD Forum 3 June 13, 1999 02:36


All times are GMT -4. The time now is 10:02.