CFD Online Discussion Forums (http://www.cfd-online.com/Forums/)
-   Main CFD Forum (http://www.cfd-online.com/Forums/main/)
-   -   Doubt on Implicit Methods (http://www.cfd-online.com/Forums/main/12968-doubt-implicit-methods.html)

 analyse In India February 12, 2007 23:17

Doubt on Implicit Methods

Dear All, I have a doubt related to Implicit Methods in CFD? What does this implicit means?

As per my understanding when you want to solve the set of linear equations implicitly, you would end solving the matrix using any one the direct methods. If my understanding is correct does the solver user "direct solver" while solving the problem implicitly.

If the solver is using implicit methods, then why still it is going on in ieterations ...

with all these confusions I have assumed the following steps in the solver, I need to know whether my understnading is correct

1. The solver goes iterative because of to convert the non liner problem to linear problem, thus each iteration will become a linear problem. The set of algebric equations formed for this linear problem (one iteration) can be solved implicitly (direct matrix inversion) or explicitly ( iterative method eg : Gauss Jacobi) ..

is my understanding is correct ....

 Gustavo February 14, 2007 11:04

Re: Doubt on Implicit Methods

OK...first let me say that I'm a student then what I write is my understanding of the stuff....

Using method of lines in finite volume approach makes it possible to separate time from space integration. Explicit time approaches uses properties that you already have (let's say on step n) to calculate properties on next time step (n+1). We could do (theoreticaly) this also without marching on steps, using just the properties we know in the begining (initial conditions) but that would mean solving analitically the NS equations what as far as I know no one managed to do (for any case I mean). Then we linearize them from step to step in time; the smaller the step the better the linearization... The difference to implicit methods is that these (implicit) need not only information from the step n to advance; i also needs information from the surrounding control volumes on the following step to advance the solution on the control volume you are in; but on step n we do not have that information yet...then we write the solution for that point implicitly as a function of the properties of the others on the following time; but when you do this for all points you get to a closed system, from where you get the system matrix; the algoritm you are using to invert this matrix (LUSGS, ADI, krylov subspaces or whatever) is another problem; but this is still a implicit approach; the necessity for iterations is the same as for the explicits....the bigger the advance the bigger the error linearizing....

that's my view...

 Paolo Lampitella February 15, 2007 08:39

Re: Doubt on Implicit Methods

Hi, i'm just a student but the following is absolutely right.

For example, consider the incomp. N.S. eqns. in their conservative form dropping out the pressure term (this is another story) and take on the left just the time derivative. Considering V as the vector variable for the velocity field, they will have the form(d/dt denoting partial derivative in time):

where the secon equality is just for convenience.

If we now integrate in time for a single time step from t to t+dt we obtain:

V(t+dt)-V(t)=Int(c1,t,t+dt)-Int(c2,t,t+dt)

which is still an exact relation. Now we'll introduce the approximation, that is, we have to express the two integrals numerically. Two simple examples:

1st order Explicit Euler scheme

V(t+dt)=V(t)+dt*c1(t)-dt*c2(t)

this means that for every point in the flowfield the velocity vector at the next time can be expressed only in terms of known quantities, so no system of equations to be solved, no iterations involved, just a simple algebraic relation.

1st order Implicit Euler scheme

V(t+dt)+dt*c2(t+dt)-c1(t+dt)=V(t)

As you can see, two problems arised in this new approach:

1)You have to solve a system of equations to obtain the velocity field at the next time step because in the left side of the equation ( the time t+dt) appeared the discretized form of the spatial derivatives involved in c1 and c2, both expressed in term of V(t+dt).

2)The system is nonlinear due to the presence of c2=Div(VV)

So, to obtain the new velocity field you have to linearize the equations and solve the system, at each time step, iteratively.

So, why to use a so much complicated scheme instead of a very simple explicit one? This is due to the stability costraints of the explicit schemes which are much more severe than those of the implicit ones (that is how much small must be the time step dt in function of the grid size dx).

Obviously this was just an example, i think that the most widely used scheme is the Crank-Nicholson, that is an implicit 2° order scheme.

Note that, due to its easy stability costraints, the implicit scheme is also used for steady calculations (it must be used!) because you can choose a very large time step to reach in the fastest way the steady solution.

 Venkatesh V March 5, 2007 17:41

Re: Doubt on Implicit Methods

Thanks to Gustavo and Paolo.

My doubt is related to steady state problem. Any CFD commercial software will have to options Explicit and Implicit. I have doubt on the implicit scheme. If we want to implement 100% implicit scheme for solving set off algebric linear equations, we will endup in inverting the matrix. Which is computationaly expensive and requires more memory.?

My doubt is really the copmmercial softwares do invert the matrix? If they do so? why there is huge difference between the number of "discretization points" handled by FEA based codes and FVM based codes.

FEA based codes cannot handle large number of "discretization points" (whether cell center or node) handled by FVM based codes. I thought this may be due to FEA based solvers does matrix inversion at each iteration. If FVM based code also does matrix inversion for implicit method, the maxumum number of "discretization points" handled by both codes on a same hardware should be of same order even though not same. But why there is difference

 Paolo Lampitella March 6, 2007 05:27

Re: Doubt on Implicit Methods

Hello Venkatesh, i don't really know how the FEA works in CFD but for FVM i'm sure: no matrix inversion occur in any commercial solver and this should be avoided in any ownmade code too. The reason is a simple one, the number of operations grows up more then linearly with the number of unknowns of the system. Moreover, with an iterative solver you have some control on the error but with an exact solver and 1 million unknowns, even if there is the time to solve it (and this is NOT the case), there is no control on the error growth with the enormous number of operations required, so just don't has any sense to TRY to solve exactly a big system of equations.

But, we have to distinguish the cases in which could there be the necessity to solve a system of equations in incompressible CFD.

1)Poisson eqn. for pressure: this is always the case. It can be a pressure correction in a steady solution; in this case you will solve it different times per each iterationand because you are just trying to reach the steadyness it not necessary to solve exactly the system every iteration. Or it can be an exact one as in the projection method, in this case (usually unsteady) you will solve it once per time step and ...yes, you will solve it iteratively.

2)Implicit approach: in this case you will have to solve a system to obtain the velocity unknowns per each time step. The implicit approach is nearly always used: in unsteady cases for stability constraints or in steady cases too, in which you have to drive the solution, as fast as you can, to the steady state, so stability constraints too. If the discretization is Fully Implicit, that is convective and diffusive terms are both discretized implicitly, than the system will be nonlinear and you will not have choice: some kind of linearization and solve iteratively. If the convective terms are discretized explicitly and the diffusive terms implicitly, you still have to solve a system, but it is linear. Differents approachs emerges in the fully implicit cases, depending if the equations are solved in a coupled or uncoupled manner, but these are the main features of the problem.

About the FEA, if it stands for Finite Element, i don't really know. In structural mechanics, an uncoupled system of linear equations, i'm not sure but, i think that depending of the number of unknowns the system switch between exact and iterative solver. Usually, if the number of equations to be solved is less than 2000, an exact solver could be a good choice.

I hope i've been useful.

 Venkatesh V March 6, 2007 10:02

Re: Doubt on Implicit Methods

Hi Paolo,

Still I am not sure what does implicit solvers means in Commercial Solvers. Let as assume we will explicitly discretize the convective terms and implicitly dizcretize diffusive terms for Steady state X-momentum equations.

But if you solve the set of algeberic liner equations iteratively, then when you solve the equation Ui(U velocity at i th cell) you will use the Uin (U velocity of i the cells neighbours) from previously. THat means you are solving the equation explicitly. This is equivalent to discretizing the equation explicitly.

For make it simpler(to remove nonlineraity) we can take only steady state heat conduction equations (poisson equation). If you solve iteratively then it becomes explicit method. How can we have implicit iterative method.for steady state heat conduction equation???

 Paolo Lampitella March 6, 2007 11:49

Re: Doubt on Implicit Methods

Ok maybe i understand what you mean. Let me show you an example; consider the classical 1-D heat equation.

Explicit discretization:

U(i,n+1) - U(i,n) = (k*dt/dx^2)*(U(i+1,n) - 2U(i,n) + U(i-1,n))

Implicit discretization:

U(i,n+1) - U(i,n) = (k*dt/dx^2)*(U(i+1,n+1) - 2U(i,n+1) + U(i-1,n+1))

In the first case you have:

U(i,n+1) = U(i,n) + (k*dt/dx^2)*(U(i+1,n) - 2U(i,n) + U(i-1,n))

so, for every point in the domain (i index) you can obtain "explicitly" the solution at the next time step (n+1) just knowing the solution at the previous time step (n). This is what is called an "Explicit advance method" or "Explicit integration method".

In the second case you have:

-(k*dt/dx^2)*U(i+1,n) + (1+2k*dt/dx^2)*U(i,n+1) - (k*dt/dx^2)*U(i+1,n) = U(i,n)

for every point in the domain (so except the boundaries), which is a system of equations for the solution at the next time-step (n+1) with the Right Hand Side given by the solution at the previous time step (n). Now this is what is called an "Implicit advance method" or "Implicit integration method", because you can express the solution only implicitly, in fact you have to solve a system per each time step until you reach the final time.

These are the explicit and implicit approach of an advance or integration method. Nothing else (not considering the stability or other stuff that is unimportant for now).

The next step is: if i want to proceed with an implicit method, how i can obtain the solution of my system? You have two choices again:

1) Exact solvers; for example the gauss elimination method or most probably the Thomas algorithm for tridiagonal matrix, which perfectly applies to the previous example.

2)Iterative solvers; SOR, Conjugate Gradient family, Multigrid...there are a lot of.

Now, if you choose the implicit approach and an iterative solver, and you want to simulate in time until a defined T time, this is what you have to do:

define an initial condition, per each time step form the matrix of the system, give an attempt to the solution at the next time step (all zeros or the solution at the previous time step) and correct the solution of the system iteratively (the way you correct it makes the methods differents) until some control parameter is small enough. Now, what you have obtained from the solution of the system is the solution at next time step (n+1). The solution method proceed like this until the final time T is reached.

Now let's do the final consideration that, i hope, will clarify all your doubts. Suppose, as previously stated, that we choose an implicit method to advance in time the solution to our heat equation and that we choose an iterative solver for the system of equations. Because the implicit approach has the special feature that nearly always is possible to choose a dt (time step) as big as you want, suppose that we don't want to follow the entire time history of the solution so we put dt=T. Now, what is happened is that we have to solve the system just one time and we'll get the final state solution. Now, if your question was : "Is possible in this case to assimilate the iterative solver to an explicit time advance method in respect to the fact that we don't solve any system effectively and that per each iteration the solution ATTEMPT at the next ITERATION step is just function of the solution ATTEMPT at the previous ITERATION step?"

the answer is "Yes", it is very similar to an explicit advance method but the difference is that at each iteration the solution attempt does not verify the boundary condition so you can't follow the time history and that the iterative solvers works like an explicit (two-step) solver but with a local time step, that is, for every index i you have a different time step.

I hope i've been useful. Let me know if this was your question.

 Venkatesh V March 6, 2007 15:37

Re: Doubt on Implicit Methods

Hi Paolo, It looked like I was getting clear finally I aam confused. Thanks for your efforts.

I will pose the question from different angle ..

* I am interested in "STEADY STATE" linear equation. That is equivallent of "One step" linearzied non-linear problem.

As per your previous explanation, if I have chosen Implicit Discretization and And I have some how got some initial guess( it may be random guess or solution in previous iteration or solution).

Now I have end up in system of linear equation. If I chosen to solve using SOR, I will use the values from previous iteration or initial guess. This is explicitness in the solution procedure.

On the other hand if you solve gaussian elimination you will never use values from previous time step or initial condition. This is implicitness of the solution procedure.

So whenever I think of some iterative method, some explicitness is entering into the solution procedure. So how can commercial softwares have implicit iterative solver

 Paolo Lampitella March 8, 2007 14:44

Re: Doubt on Implicit Methods

Ok, first just few statements to better distinguish the arguments we are talking about:

1)The one-step linearized nonlinear problem is equivalent to a steady problem just under the mathematical procedure, that is if you make just a step with a linearized nonlinear problem you will NOT obtain the exact steady solution because you have frozen the coefficients of the equations at some time that is not the final one so at the next step they will be different; this is the reason to iterate until "nothing changes".But this is not what you're interested in so let's stop talk about nonlinear problems.

2)Just to be more clear, the only things about which you can correctly talk of "explicit" or "implicit" is the advance method; that is, you have an INITIAL VALUE/BOUNDARY VALUE PROBLEM and from a specified initial condition you have to go forward along a "characteristic line" which is called time-like coordinate. This coordinate can be just the time or, like in the boundary layer equations, a spatial one. It is not wrong to talk about "implicit" or "explicit" about other kinds of stuff but, because in all the books on numerical analysis this is the current terminology and because it seems that me and you have mother languages different from English (Italian and Indian) i suggest to follow this terminology to better understand each other.

3)Following the latter suggestion, talking about the STEADY solution of the UNSTEADY heat equation is different from talking of the solution of the Laplace equation (the steady version of the heat equation) that doesn't have time-like derivatives and will admit just a one-time solution. So, saying

"if I have chosen Implicit Discretization and And I have some how got some initial guess"

has no sense because if you choose an implicit discretization this mean that you have a time-like advancement so you need an initial SOLUTION not an initial guess. That is, the solution that you initially supply MUST fit the boundary conditions of the problem and somehow is going to influence the time evolution of the solution.

Now, let's go to your question. As stated in the previous post, it is not wrong to think at the iterative solvers as a time advancement to a steady state. This mean that if you have to solve the Laplace equation in a square you can introduce a fitticious time derivative (the equation is so trasformed in the heat equation) and, using an explicit discretization, drive the solution to the steady state and this is somehow equivalent to use an iterative solver.

But, going to the core of the question (i hope), i think you are making confusion with

"implicit iterative solver"

that you are translating as:

"Gaussian elimination method + iterative solver"

and whose real meaning is

"Iterative solver used on the system of equations which arise from the implicit time advancement for an UNSTEADY problem"

On the other hand it could also be possible that exists a procedure called "Implicit iterative solver" but, if this is the case, i don't really know it...but i would exclude this. I hope i've finally understood what was your question.

 analyse In India March 8, 2007 21:01

Re: Doubt on Implicit Methods

Hi Paolo, That is great. My doubt is clear now. Thank you very much.

Thanks Venkatesh V

 Paolo Lampitella March 9, 2007 04:01

Re: Doubt on Implicit Methods

You're welcome.

Paolo

 All times are GMT -4. The time now is 09:30.