Explicit vs Implicit time-stepping

Amdi · August 24, 2011, 23:01

I wonder which is better, explicit or implicit time-steppings. Maybe, it depends on the purpose: steady problems, unsteady problems, stiff equations, parallel computations? Anyone has ideas or opinions or references? Thanks.

Amdi

cfdnewbie · August 25, 2011, 06:42

oh, long discussion... explicit vs implicit, which is better?
Totally depends on what you want to compute.... some random thoughts:

implicit:
+ steady state ..
+ if you are not interested in the fastest wave speeds of your prob, or if the dominating physical effect takes place on large timescales
+ incompressible flow
- no pre-conditioner, no gain in speed compared to explicit....pre-conditioning is an art in itself, there are many many combinations of implicit solution methods + pre-cons.... kinda a black art to me.... seems to be a lot of experience and guess work....
- memory requirement can seriously limit your computation
- (my opinion

less intuitive, harder to program and debug
- harder if not impossible to parallelize well (and get good scaling!)

explicit:
- sucks at steady state
- computation can be bogged down by fastest wave speed
+ very easy to set up
+ often (e.g. turbulence) fastest wave speeds are of importance, so the smallest timescales must be resolved anyway
+ parallelization very easy, almost perfect scaling possible

My conclusion: Totally depends on what you want to do!!

Amdi · August 25, 2011, 10:34

Dear cfdnewbie

Thanks for your insightful comments!

Just one more question.
Why is it difficult to parallelize implicit schemes and get good scaling?
Each linear solve iteration is like an explicit scheme which scales perfectly, no?

Amdi

cfdnewbie · August 25, 2011, 10:45

Implicit schemes always require the setup of the system matrix in each step (at least for a non-linear problem), so you have to build and manipulate the matrix in memory....this matrix can become huge, as it scales with DOF ^d, with d = dimension of your problem (2d, 3d)....

so to invert this matrix, you need a) a huge amount of memory b) distribute this matrix somehow over your procs c) communicate a lot between procs (to find the inverse)
This communication is what generally slows down your code, and makes good scaling difficult. I'm no expert on implicit methods, though, maybe there are clever tricks to circumvent this and make the scaling acceptable. I prefer explicit methods, because the problems I am interested in need them anyway..

Amdi · August 25, 2011, 16:11

It's interesting that it takes a lot more effort to solve a linear system in parallel.
Thanks!
Amdi

cfdnewbie · August 25, 2011, 16:21

Keep also in mind that implicit schemes have a much higher memory requirement due to the matrix... I know that all people doing implicit stuff always complain that the memory requirement is what kills them when they are trying to get their code to perform on hpc machines...

Again, i am no expert on implicit schemes, i prefer explicit ones, so maybe somebody with more experience can give you an other opinion!

julien.decharentenay · August 25, 2011, 19:31

Hi Amid/cfdnewbie,

I agree with most comments from cfdnewbie but would like to add a few more.

There are more than one way to do implicit time-stepping:
- iterative solver (conjuguate gradient and the like) can be used to keep memory down and they scale reasonably well in parallel - also quite good for sparse matrix (which most CFD solver require);
- simple/piso like algorithm where the implicit equation are solved in a segregated manner (ie solver u-velocity, v-velocity, w-velocity as distinct equation). This approach again limit memory use as the system is not NxN -where N is the number of cells - in place of (nxN)x(nxN) - where n is the number of equations;
- compressible flows can be treated implicitly - as long as the flow physics you are interested allows for implicit treatment (i.e interaction of a pressure wave with a turbulent field would likely require an explicit algorithm);

cfdnewbie would need to refine his comments on pre-conditioning as it can refer to either pre-conditioning of the equation to reduce the stiffness of the system to solve (physic based such introduction of an artificial compressibility) or pre-conditioning of the system to solve (incomplete LU decomposition as a preconditioned to conjuguate gradient for example).

It is a very wide question and subject. And you need to keep in mind that an appropriate solution for the automotive industry may not be appropriate for the aerospace industry - get the right tool for the job.

Kind regards,
Julien

cfdnewbie · August 26, 2011, 04:20

Hi Julien,
thank you very much for your insightful comments!

Quote:

Originally Posted by julien.decharentenay

Hi Amid/cfdnewbie,

I agree with most comments from cfdnewbie but would like to add a few more.

There are more than one way to do implicit time-stepping:
- iterative solver (conjuguate gradient and the like) can be used to keep memory down and they scale reasonably well in parallel - also quite good for sparse matrix (which most CFD solver require);

Could you give a rough idea of the scaling percentage? Strong and weak maybe? Just a rough figure would be nice, I would like to get a feeling for what an implicit solver could do.....
Another question: Is there a clever way to use the sparse matrix to your advantage? I know that people store just the non-zero matrix entries plus their matrix indices, but this mapping is pretty timeconsuming, right?

Quote:

- simple/piso like algorithm where the implicit equation are solved in a segregated manner (ie solver u-velocity, v-velocity, w-velocity as distinct equation). This approach again limit memory use as the system is not NxN -where N is the number of cells - in place of (nxN)x(nxN) - where n is the number of equations;

so you just build the matrix for each variable at a time and solve it? Is that how it is done?

Quote:

- compressible flows can be treated implicitly - as long as the flow physics you are interested allows for implicit treatment (i.e interaction of a pressure wave with a turbulent field would likely require an explicit algorithm);

have you a reference for a turbulent compressible flow treated implicitly? I has seen some weakly compressible implicit stuff, but not yet full compressible implicit solution - at least none which seemed efficient to me...

However, one should forget the mixed approach: treating terms in your equation according to their physics either explicitly or implicitly...RKIMEX and such... that seems to be pretty interesting, but I haven't looked into it yet.

Quote:

cfdnewbie would need to refine his comments on pre-conditioning as it can refer to either pre-conditioning of the equation to reduce the stiffness of the system to solve (physic based such introduction of an artificial compressibility) or pre-conditioning of the system to solve (incomplete LU decomposition as a preconditioned to conjuguate gradient for example).

I was talking about the last one, making your matrix more diagonal, so to speak. Isn't it true that the right (or wrong) combination of solver and preconditioner can make a huge difference in speed? A friend of mine did his PhD on some of this, and always complained that choosing with P to take was a pain in the neck....it seemd pretty arcane to me...

Quote:

It is a very wide question and subject. And you need to keep in mind that an appropriate solution for the automotive industry may not be appropriate for the aerospace industry - get the right tool for the job.

Also true....and maybe I mislead the guy who asked the questions...I was talking from a compressible turbulence researchers perspective, which may be totally different from what sbd would need to get a job done in an automotive setting....

It's not a question which one is better - in general. Each has its uses and disadvantages, but it's good to be aware of them....

Cheers (explicitly

)
Cfd newdbie

julien.decharentenay · August 26, 2011, 07:09

I will do my best to answer your question.

Quote: