Hi. i figured, if we are already talking about CFD, ill come up with an idea, about the advection scheme. since linear interpolation isnt accurate, and the monotonic cubic interpolation is slow, what will happen if we do the following: subdivide the time step into X smaller time steps, then for each little time step trace backwards in time, compute the velocity there, until you traced through the whole original time step. this will be much more accurate, and im not sure it will be slower than the hi-order interpolation. what do you think?

I''m quite tired of this recent fluid simulation thingie, but conceptually there are some universal things in your post which apply to the whole field of computational physics.

That is, you''d like to use many smaller time steps instead of one big step. This naturally gives better looks.

If you''re about to lower your timestep, then you should something about the order of your update routine:

If you''re doing your semi-Lagrangian advection using a 1st order (Euler) particle trace, your error will (in theory) go down by ONE digit if you make the time step ten times smaller (ie. linear timestep/accuracy relation).

If you''re using a 2nd order (midpoint/RK2) tracer (as Stam does), the error will (again in theory) go down by TWO digits if you make the time step ten times smaller (quadratic timestep/accuracy relation).

Wether you choose a cubic monotone interpolator or a simple linear interpolator is a rather different thing, because it''s used to interpolate within *SPATIAL* coordinates (that is, x,y,z). If you lower your timestep, you''re essentialy working in the *TEMPORAL* coordinate (t). I don''t know how these mix in theory.

But for granted, if you lower your timestep, you should see a more accurate flow, but with more computation time. Dunno if the accuracy/overhead ratio is good, depends on your case I think.

- Mikko Kauppila

actually, this isnt exactly what i meant, but never mind. thanks for answering.

I guess, if you trace your particle smaller than min(dx,dy,dz) back in time you won''t get more accurate results because you only have data(velocities) sampled at those grid points, which are dx, dy or dz away. On the other hand, the bigger the step back, the more inaccurate will be the results.

Cheers,

Oliver

pickups: Concerning interpolation...
If you are in 2D you use bilinear interpolation, in 3D, trilinear interpolation. Linear interpolation is just wrong in either case. So, if you trace your particle back in a 3D-Eulerian grid, trilinear interpolation is the only way to go.

Cheers,

Oliver

[edited by - pilarsor on August 3, 2003 1:12:34 PM]

Now I understood the meaning of your original post. You wanted to break each semi-Lagrangian path into smaller substeps and resolve each substep with Euler integration. Very well, let''s discuss this case.

Let''s assume that we would break the linear trace into two substeps. A better (generally more accurate and equally expensive) solution would be to use RK2 (the midpoint method) instead of taking two Euler steps. It can be shown theoretically that the error in RK2 is O(t^2) whereas in Euler it is O(t).

And if you read Stam''s original paper Stable Fluids carefully, it is said that he uses an adaptive tracing scheme, that is, if the particle trace takes too big leaps, the trace is subdivided into smaller subtraces (the base method being RK2).

So the method you proposed is a widely used idea. But it''s good to come up with them yourself sometimes.

- Mikko Kauppila

allright. i dont know what RK2 is, but this method is good becuase this way large time steps can be taken, while maintaining accuracy and reducing the number of time we need to solve for the pressure effect. i just noticed it is suggested in the physical fire paper by stam and fedwic and a bunch of other people.