• Create Account

# Implicit/Explicit Integration

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

39 replies to this topic

### #21 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 05 May 2005 - 06:05 AM

Can you point to some documents that explain the derivation of this “semi-implicit hot hotch method for diffusion”

I would like to ready it so I can get rid of my ignorance. Because what you describe is just an empirical application method for calculating and explicit integration method.

And implicit method will have to consider the coupling effect of neighbored nodes in the lattice by taking partial derivatives of the function that describe the phenomenon. You can not under any circumstance estimate the values of the derivatives by using and explicit step, what you describe is some sort of RK or Predictor corrector method.

You can not describe a mathematical theory or method by and example, you need to start by a premised and then submitted to a rigorous mathematical probe.

### #22Dmytry  Members   -  Reputation: 1144

Like
0Likes
Like

Posted 05 May 2005 - 07:01 AM

Quote:
Original post by TheFatGecko
Quote:
 Finally I hear the turn semi-implicit integration, which I have no idea what it means, as far as I know there are only two ways for numerical integration of differential equation, explicit and implicit

An example of a true semi-implicit method is the "hop hotch" method for diffusion. Basically, you use an explicit method to calculate the effect of diffusion at every ODD position for time step n+1. Then at all the EVEN positions (at time step n+1) you use the neighbouring elements and the ODD elements at time step n.

I know that explanantion might not make immediate sense, but basically every ODD element has been calculated explicitly and every EVEN element has been calculated implicitly. As you advance in time you swap between ODD and EVEN, giving you a semi-implicit method which is highly stable

I were doing something like that for some water simulation... and yes, it works quite well.

Also, when doing this "update even based on odd, then update odd based on even" you can enforce really strict energy conservation (or small damping), instead of just damping everything alot to keep it stable.

Of course such "hacks" have certain drawbacks, but when you have to deal with big timestep, you 'll have errors anyway.

### #23TheFatGecko  Members   -  Reputation: 206

Like
0Likes
Like

Posted 05 May 2005 - 08:26 AM

Quote:
 Can you point to some documents that explain the derivation of this “semi-implicit hot hotch method for diffusion”

"hop hotch" should have been "hop scotch", sorry about that.

There's plenty of stuff to be found with google

### #24John Schultz  Members   -  Reputation: 807

Like
0Likes
Like

Posted 05 May 2005 - 10:54 PM

ODE is an open source implicit integrator for game physics.

You can find executable demos in the binary releases.

Dynamics with Coulomb Friction
.

### #25 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 06 May 2005 - 01:26 AM

That is what i mean there is a lot of talk about this topic almost all of it wrong. ODE clim in the docs it has an implicit or simi-implicit integration but the is totally incorrect. in reality ODE and for that used the more error prone euler integrator there is.

### #26 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 06 May 2005 - 01:42 AM

The second paper is also misleading. It is called implicit time stepping because it does not uses an instantaneous point of view, instead it used impulsive momentum-equation. What ever that means.
But nowhere in the paper it shows that the derivative of the state vector is at time t + 1, meaning and the end of the time step, which is impossible which out backtracking.

Not it is wrong with the paper but the work implicit is not related to implicit integration in any way or form. It is just in the title of the paper.

### #27Eelco  Members   -  Reputation: 183

Like
0Likes
Like

Posted 06 May 2005 - 06:45 AM

Quote:
 Original post by Anonymous PosterCurrentely the only things implicit methods are good for is writing turn papers, research, and some sort of cloth and soft body simulations. But they can not be extended beyond that area or at least no body had come up with a method beyond springs suitable for the generalized dynamics formulation.

im using an implicit integrator for structural dynamics, and there simply is no contest. implicit is a clear winner whatever way i look at it.

the only slight concern i have with it is the damping of rotations. then again the things like bridges i intend to simulate will never get even close to such rotational velocities, and a simple trapezoid is already much better in this regard than the backwards euler that gave implicit its bad name.

on top of that: if i were to write a simulator where rotations were a concern, id want to add damping/drag to the system anyway to prevent overly fast rotations, since those would undoubtly compromize the stability of collision detection and such.

in any case an explicit integrator wouldnt even be able to convincingly simulate the speed of rotation were talking about without significant deformations because the required stiffnesses wouldnt be stable.

as for constraints: read baraff. its even better and just as simple as the constrained verlet stuff.

right now floatingpoint precision is my biggest worry for rediculously stiff systems, something i couldnt even have dreamt of with an explicit integrator.

so yeah id say there are definitly applications besides research papers.

### #28John Schultz  Members   -  Reputation: 807

Like
0Likes
Like

Posted 06 May 2005 - 09:16 AM

Quote:
 Original post by Anonymous PosterThat is what i mean there is a lot of talk about this topic almost all of it wrong. ODE clim in the docs it has an implicit or simi-implicit integration but the is totally incorrect. in reality ODE and for that used the more error prone euler integrator there is.

ODE solves a system of simultaneous equations (from the docs, "big matrix" and "fast iterative" solvers), Ax = b, etc.

See the ODE source, lcp.cpp (Convex optimization, Dantzig's algorithm), fast*.cpp. See quickstep.cpp (uses Conjugate Gradient (CG) (with Jacobi preconditioner, experimental), Successive Over-Relaxation (SOR) with LCP). See also step.cpp, stepfast.cpp (code from David Whittaker, iterative relaxation proposed by Sergi Valverde).

Where in the ODE source code do you find an explicit Euler integrator?

GameTech04.

Semi-implicit integrator (I believe Erin Catto (the author) posts on this forum):

Slides.
PDF.

Here is a paper that proposes:

Ingredients to achieve high-performance:

Velocity-based complementarity formulations.
Leap-frog like time-stepping scheme.
Iterative LCP solver.
Error-correction by projection.
Shock-propagation, followed by a smoothing correction
phase.

Paper here.

[Edited by - John Schultz on May 6, 2005 4:16:52 PM]

### #29Dmytry  Members   -  Reputation: 1144

Like
0Likes
Like

Posted 06 May 2005 - 09:30 PM

Looks like terminology there(what is explicit and what is implicit) is completely borked for anything except Euler. Maybe my bad English, tho.

What if I do that: update all even vertices in grid, then update all odd vertices in grid, then all even again? This way it is rather easy to enforce energy conservation and/or physically accurate damping. Also, if I use knowledge about system of equations (e.g. that energy must conserve), instead of blindly dropping generic solver onto problem, will it become "implicit"?

I'd adwise against "using implicit" or "using explicit", better use what suits your problem. (tho, usually it's "implicit" [grin], because explicit methods is typically a generic solvers that is used on everything) For example, leapfrog is good for n-body. Update-even-update-odd methods is good for simulating grid when energy conservation is necessary. And so-on.

### #30John Schultz  Members   -  Reputation: 807

Like
0Likes
Like

Posted 07 May 2005 - 06:14 AM

Quote:
 Original post by DmytryLooks like terminology there(what is explicit and what is implicit) is completely borked for anything except Euler.

The use of implicit implies a simultaneous coupling of the variables, with a simultaneous solution step. The use of explicit implies the variables are decoupled for the solution step, and are not solved simultaneously. As Graham Rhodes stated:

Quote:
 The implicit solver works by computing M, C, K, then using a matrix solver or iterative (Jacobi, Gauss-Siedel, SOR) solver to compute new values of A, V, and X at the same time for all of the particles.It turns out that by solving the particles as a coupled system, the potential for instability usually goes away and the simulator almost always works without instabilities and blow-ups.

I think it's fair to say:

• If the variables are completely decoupled during the solution step, it's an explicit method.
• If some variables are coupled and some uncoupled, it's a semi-implicit method.
• If all variables are coupled, it's an implicit method.

For example:
Quote:
 Explicit Euler:x += v*dtv += a*dt // Velocity and position are completely uncoupled.

Be changing the order, we can make a simple coupling (the following methods have the same behavior):
Quote:
 "Semi-implicit" Euler (also known as Symplectic Euler):v += a*dtx += v*dt // Velocity and position are now coupled.

Quote:
 Verlet:v = xc - xo + a*dt*dtxo = xcxc += v

Quote:
 ""Euler-Verlet":v += a*dt*dtx += v

Thus, we went from completely uncoupled to a coupling of position and velocity for one element.

More and more subset groups of elements could be coupled using a variety of methods, making the solution more and more implicit, until at the limit all elements are totally coupled, giving a completely implicit method.

Again:

• Totally uncoupled = explicit
• Totally coupled = implicit
• Partially coupled: semi-implicit

In order for a method's implementation to be more clear, a statement would have to be made regarding the amount and location of coupling (and perhaps range: local (single element) to global (entire system)), or perhaps a percentage or other metric could be given.

### #31Eelco  Members   -  Reputation: 183

Like
0Likes
Like

Posted 07 May 2005 - 06:42 AM

i thought a method was called implicit when the state at t+dt is used to solve for that same state. that this implies coupling of the equations just happens to be so.

### #32Dmytry  Members   -  Reputation: 1144

Like
0Likes
Like

Posted 07 May 2005 - 07:03 AM

What's about RK4 ? You can't say that variables is decoupled during solution step. After each step of RK4, value depends not only to derivative for that value.

I agree that you can define what is "explicit Euler", and never doubted it; but can you give some other examples of "explicit methods" of higher order so bolded part
Quote:
 * If the variables are completely decoupled during the solution step, it's an explicit method. * If some variables are coupled and some uncoupled, it's a semi-implicit method. * If all variables are coupled, it's an implicit method.

holds true?

With this definition strictly applied, Euler (i mean "true Euler") and "explicit method" becomes just synonims. That's because any methods with higher order have variables somehow "coupled" during solution step, or uses information from previous steps, coupling things again. I just try to understand what you really mean by "explicit", especially because English is not my native language. The problem is actually not that it is not defined, but that with such definition "explicit" becomes completely equivalent to "true Euler".

I sure see that you mean something more general than "true Euler".

Mayber you mean that when "compute ALL derivatives" and "update ALL values" are not mixed with each other, it's explicit. That is, when there is separate function F in
dA/dt=F(A)
where A is state vector(btw, it could contain time) and F is a function that computes derivatives. Function doesn't know anything about dt. Then, RK4 and friends becomes explicit too, and "implicit Euler" is still implicit.
In this case, I would adwise against basing your code on that F can't know previous states and dt; with knowing dt, you can apply some analitic integration techniques inside function, for example use
position=velocity*dt+0.5*acceleration*dt^2
(if I understand you right, by your definitions, it makes method be implicit.)

[Edited by - Dmytry on May 7, 2005 1:03:20 PM]

### #33John Schultz  Members   -  Reputation: 807

Like
0Likes
Like

Posted 07 May 2005 - 11:11 AM

Quote:
 Original post by Eelcoi thought a method was called implicit when the state at t plus dt is used to solve for that same state. that this implies coupling of the equations just happens to be so.

When the term coupled is used here, it implies using the derivative at the end of the step (t plus dt) using some kind of coupling between the variables to update state: this is what makes it a coupled system (and thus implicit, as defined by the literature).

Quote:
 Original post by DmytryI agree that you can define what is "explicit Euler", and never doubted it; but can you give some other examples of "explicit methods" of higher order so bolded part

Three common explicit methods from my codebase: explicit Euler, Midpoint (RK2), and RK4 (Runge-Kutta):

template <class T>class EulerODEI : public TGODEI<T> {public:  void update(void) {    *current = *current + h*current->derivative(time);  } // update};template <class T>class MidpointODEI : public TGODEI<T> {protected:  flt h2;public:  MidpointODEI() {}  void setTime(flt deltaTime,flt currentTime=0) {    h  = deltaTime;    h2 = h*.5f;    time = currentTime;  } // setStepSize  void update(void) {    T k = *current + h2*current->derivative(time);    *current = *current + h*k.derivative(time+h2);  } // update};template <class T>class RK4ODEI : public TGODEI<T> {  flt h2,h6;  T k1,k2,k3,k4;public:  RK4ODEI() {}  void setTime(flt deltaTime,flt currentTime=0) {    h  = deltaTime;    h2 = deltaTime*.5f;    h6 = deltaTime*(1.f/6.f);    time = currentTime;  } // setStepSize  void update(void) {    flt time2 = time+h2;    k1 = current->derivative(time);    k2 = (*current + k1*h2).derivative(time2);    k3 = (*current + k2*h2).derivative(time2);    k4 = (*current + k3*h).derivative(time);    *current = *current + h6*(k1 + 2.f*(k2 + k3) + k4);  } // update};

The difference between these three explicit (forward) methods is the number of derivatives taken per step (and coefficients for the Taylor series). Each derivative step is completely uncoupled.

From Baraff and Witkin's paper, page 46 (see the paper for all info/characters missing from below):

Quote:
 The forward method requires only an evaluation of the functionf but the backward method requires that we solve for values of 1xand 1v that satisfy equation (4). Equation (4) is a nonlinear equation:rather than solve this equation exactly (which would requireiteration) we apply a Taylor series expansion to f and make the firstorderapproximation....The method is called “backward” Euler because starting from the outputstate .x0 C 1x; v0 C 1v/ and using a forward Euler step to run the systembackward in time (i.e. taking the step −h.v.t0Ch/; f.x.t0Ch/; v.t0Ch///brings you back to .x0; v0 /. What is the value in this? Forward Euler takesno notice of wildly changing derivatives (js: no coupling), and proceeds forward quite blindly.Backward Euler, however, forces one to find an output state whose derivativeat least points back to where you came from (js: for the system as a whole, and thus coupled), imparting, essentially, anadditional layer of consistency (or sanity-checking, if you will).

Based on the terms used in the literature, it is apparent that the level of implicit-ness is related to the level of coupling when determining the next state per integration step (and not necessarily reversible ("pointing back from where you came") in the semi-implicit cases).

From the slides:
Quote:
 • Explicit Euler: x(t+h) = x(t) + h f(x(t))–This is the version we already know about.• Implicit Euler: x(t+h) = x(t) + h f(x(t+h))–Evaluate the derivative at the end of thestep instead of the beginning.–Solve for x(t+h).–More work per step, but much bigger steps.–A magic bullet for many stiff systems.

It is clear that coupling is a requirement of an implicit method: in order to evaluate the derivative, the state must be coupled. If the system is coupled in this way, it must be at least semi-implicit.

See another description from these slides, page 36.

In the case of a single particle and the "Semi-implicit" Euler method, it's clear that we're using the velocity at the end of the integration step to update position. While this method is not very coupled (e.g. no coupling with other particles), it's not very implicit, but it does follow the implicit definition (uses a derivative at the end of the step to update state).

From the literature it is apparent that the more coupled the solution method, and thus the more the solution step depends on the derivative(s) at the end of the step, the more implicit the solution is considered.

[Edited by - John Schultz on May 8, 2005 12:11:44 AM]

### #34John Schultz  Members   -  Reputation: 807

Like
0Likes
Like

Posted 07 May 2005 - 11:47 AM

Quote:
 Original post by Dmytryposition=velocity*dt+0.5*acceleration*dt^2(if I understand you right, by your definitions, it makes method be implicit.)

The above method is not implicit. This method is considered semi-implicit:

velocity += acceleration*dt // update velocity with its derivative.
position += velocity*dt // end-of-step derivative of position used to update position.

### #35Dmytry  Members   -  Reputation: 1144

Like
0Likes
Like

Posted 07 May 2005 - 08:49 PM

Actually I expected that RK2 and such (RK4) is considered as explicit;(I also have code for it). Just it doesn't comply with your idea about no coupling = explicit, as there is coupling in step of integrator, and what you say about "derivative step"(there's really no such thing) is a calculation of derivative as in definition I suggested:
Quote:
 Mayber you mean that when "compute ALL derivatives" and "update ALL values" are not mixed with each other, it's explicit. That is, when there is separate function F indA/dt=F(A)where A is state vector(btw, it could contain time) and F is a function that computes derivatives. Function doesn't know anything about dt. Then, RK4 and friends becomes explicit too, and "implicit Euler" is still implicit.

- this definition naturally includes RK2 and friends without talking about "derivative step" and such. It's not "derivative step", it's computation of derivatives.

### #36Dmytry  Members   -  Reputation: 1144

Like
0Likes
Like

Posted 07 May 2005 - 08:53 PM

Quote:
Original post by John Schultz
Quote:
 Original post by Dmytryposition=velocity*dt+0.5*acceleration*dt^2(if I understand you right, by your definitions, it makes method be implicit.)

The above method is not implicit.

again, there is coupling of _derivative of velocity_(acceleration) and _position_, just written in not so obvious way. It should make method be at least semi-implicit(there are no totally implicit methods probably anyway) if definition means something at all.
Why:
Quote:
 velocity += acceleration*dt // update velocity with its derivative.position += velocity*dt // end-of-step derivative of position used to update position.

is totally equivalent to
position += velocity*dt+acceleration*dt^2
velocity += acceleration*dt
I instantly see such things.

### #37John Schultz  Members   -  Reputation: 807

Like
0Likes
Like

Posted 07 May 2005 - 10:18 PM

Quote:
Original post by Dmytry
Quote:
Original post by John Schultz
Quote:
 Original post by Dmytryposition=velocity*dt+0.5*acceleration*dt^2(if I understand you right, by your definitions, it makes method be implicit.)

The above method is not implicit.

again, there is coupling of _derivative of velocity_(acceleration) and _position_, just written in not so obvious way. It should make method be at least semi-implicit(there are no totally implicit methods probably anyway) if definition means something at all.
Why:
Quote:
 velocity += acceleration*dt // update velocity with its derivative.position += velocity*dt // end-of-step derivative of position used to update position.

is totally equivalent to
position += velocity*dt+acceleration*dt^2
velocity += acceleration*dt
I instantly see such things.

That's true, but it's not what you initially posted.

Please keep in mind these are not my definitions, but an accounting of the literature: it makes sense to me.

Do you have a better or simpler means of describing the differences between explicit and implicit integration?

Do you believe that ODE has (at the least) a semi-implicit integrator, or do you believe that it implements explicit Euler?

### #38Dmytry  Members   -  Reputation: 1144

Like
0Likes
Like

Posted 07 May 2005 - 11:46 PM

It's not a matter of belief, also I don't use ODE library anyway.

"That's true, but it's not what you initially posted."
initially there was
a)
position=velocity*dt+0.5*acceleration*dt^2
velocity+=acceleration*dt
and while it is not exactly that
b)
position += velocity*dt+acceleration*dt^2
velocity += acceleration*dt
It is same except for constant in polynomial(0.5 vs 1).
Actually it may be reasonable to use something inbetween in some tasks, e.g. 0.75 or such.

I think that both (a) and (b) should be considered semi-implicit if definitions makes any sense. Don't sure what's your point, though. That (a) is explicit and (b) is semi-implicit?

As about references to literature, they talk about Euler. I understand that terminology is quite clear when you talk about Euler, and already said that several times. Just, these papers do not contain (and shouldn't contain) definitions.

"Do you have a better or simpler means of describing the differences between explicit and implicit integration?"

yup. That's exactly my point. (now, please keep in mind that these papers do not contain definitions at all. It is research papers, they talk about specific things, and so-on). I already have posted how I would define this differencies in way that a: does not requir to invent new terminology (derivative step(what's that?)), b: defines what kind of coupling makes it be implicit or semi-implicit.

Again, definition with F implies kind of "no coupling", just I try to avoid adding things such as "derivative step". Again, this F is a computation of derivatives, what you would call "derivative step".

Example: for 2 gravitationally attracted bodies, we have system of first order ordinary differential equations [ dA/dt=F(A) ]
dv1/dt = (p2-p1)*G*m2/(|p2-p1|3)
dp1/dt = v1
dv2/dt = (p1-p2)*G*m1/(|p2-p1|3)
dp2/dt = v2

Then, explicit Euler is essentially equivalent to
// there goes F that is separate, knows nothing about dt, and such.dv1_dt = (p2-p1)*G*m2/(|p2-p1|<sup>3</sup>)dp1_dt = v1dv2_dt = (p1-p2)*G*m1/(|p2-p1|<sup>3</sup>)dp2_dt = v2// there goes update that doesn't know about Fv1+=dt*dv1_dt;v2+=dt*dv2_dt;p1+=dt*dp1_dt;p2+=dt*dp2_dt;

and semi-implicit is equivalent to
dv1_dt = (p2-p1)*G*m2/(|p2-p1|<sup>3</sup>)v1+=dt*dv1_dt;// note: update inside F. We can not separate F out.dp1_dt = v1dv2_dt = (p1-p2)*G*m1/(|p2-p1|<sup>3</sup>)v2+=dt*dv2_dt;// note: update inside F. We can not separate F out.dp2_dt = v2p1+=dt*dp1_dt;p2+=dt*dp2_dt;

Any method where this F(A) could be really separated out of method(that knows nothing about what F does internally) is explicit. This way, RK4 is explicit, as well as "explicit Euler", or Mlines method and such. Semi-implicit methods are still semi-implicit.

edit: examples.

[Edited by - Dmytry on May 8, 2005 7:46:26 AM]

### #39John Schultz  Members   -  Reputation: 807

Like
0Likes
Like

Posted 08 May 2005 - 08:23 AM

Quote:
 a: does not requir to invent new terminology (derivative step(what's that?)), b: defines what kind of coupling makes it be implicit or semi-implicit.Again, definition with F implies kind of "no coupling", just I try to avoid adding things such as "derivative step". Again, this F is a computation of derivatives, what you would call "derivative step".

"Derivative step" refers to code executed in the derivative() function in the example code I posted. When referring to code, "force step" would refer to code in the force computation function, "constraint step" would refer to code in the constraint computation, etc. I find it helpful to include small/simple and tested code examples so that anything not clear in the text description will become clear after examining working code.

With respect to:

Quote:
 "That's true, but it's not what you initially posted."initially there wasa)position=velocity*dt+0.5*acceleration*dt^2velocity+=acceleration*dtand while it is not exactly thatb)position += velocity*dt+acceleration*dt^2velocity += acceleration*dt

Quote:
 position=velocity*dt+0.5*acceleration*dt^2

Which doesn't really make sense until you add a += and show how you update velocity. In any case, I agree that your updated version matches this form:

velocity += acceleration*dt // update velocity with its derivative.
position += velocity*dt // end-of-step derivative of position used to update position.

which is commonly referred to as "semi-implicit" Euler.

With respect to ODE being implicit or semi-implicit (which appears to have sparked this part of the discussion): I also do not use ODE, however I have examined the source code, and it appears to be at least semi-implicit, and does not appear to implement explicit Euler. "believe" can be substituted with "perceive" or "understand". Given the information in this thread (and if you have the time, from the ODE source code), how do you define ODE's integrator? Explicit, semi-implicit, or implicit?

### #40Dmytry  Members   -  Reputation: 1144

Like
0Likes
Like

Posted 08 May 2005 - 08:51 AM

ops... that was blindly-copypasted typo.

I'm not talking about ODE.... it's quite likely that ODE is semi-implicit, but archives with sources looks rather big and I'd rather reread some of my own code in hope to find bugs[grin]. I just think that with more clear definitions there would not be such discussion "is ODE explicit or not". Also, I thought it's good practice to supply several different integration techniques in physics package...

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS