UKC

A stab in the dark, but is anyone able to point me to a very basic explanation (i.e. few equations as possible) of how an implicit finite difference method works? A numerical model I'm using solves PDEs (or maybe just differential equations, i'm not sure) using an implicit method, which i need to explain in some work, apparently.

Information i've found online leaves me completely lost. And there is no information directly for the model i'm using (it's a 3-D diffusional stratigraphic forward model).

Any help seriously appreciated. I can give more details if required.
Apologies if this is not an appropriate post for the forum...

Thanks!

In reply to Geoboy:

How much detail do you need? The basic idea is very simple but the details can get very complicated.

Speaking very broadly, if you want to solve a differential (or partial) equation you need the equation itself and a variety of starting/boundary conditions. The starting/boundary conditions are necessary to get an exact solution (in the same way you need some more info to get rid of the constant of integration).

If you could solve the differential equation exactly, then it would essentially give you precise information about everything that happens between the starting/boundary conditions. Obviously that's not possible (otherwise you wouldnt be trying to approximate the solution) so what finite difference methods do is split the space between the boundary/starting conditions up in to a grid of points and try estimate the right values for each point in the grid.

The 'implicit' part is just the method that's used to estimate the value at the unknown points. There are several other possible methods, for example explicit and crank-nicholson.

This image shows a 2D example: https://lh3.ggpht.com/_3E_7nRJs1Mw/TDC7UNeZw9I/AAAAAAAAEMc/R2G2vKji3hs/s160...

Information is known about everything on the top boundary, the right boundary and the bottom boundary (your starting/boundary conditions). The implicit method uses information from the three points to estimate the next point along. It works it's way along each column, filling in estimate for the next column, until the whole next column has estimates. It then moves to the newly calculated column and starts using those values to fill in the next column again.

In reply to remus:

Ah excellent, thanks a lot remus. I'm reading away and finding more explanations. Yours above with the example is really helpful.

I think ideally I need to explain the basic point of a FDM. Then why an implicit method is used over explicit or crank-n method. i.e. what is the difference between them? Stability?
Then finally, as much as i can about how this relates to the way the model in question works.

Aside from not having a maths background, the problem I have is appreciating how this all relates to a particular diffusional model of sediment transport. I'm pretty sure the various parameters (e.g., random walk) of the model are included in an implicit finite difference solution which is the basis for most of the model's calculations, but surely there could be many different ways the developers wrote the implicit finite difference solution? Or is it generally consistent among mathematicians/numerical models?

Apologies if this comes across as totally ignorant! I'm a geologist

Thanks a lot!

In reply to Geoboy:

It's been a while since I did finite difference methods, but from memory each method (implicit, explicit, crank-nicholson etc.) each have different properties that make them more or less suited for certain applications.

From the FDM wikipedia article:
"Usually the Crank–Nicolson scheme is the most accurate scheme for small time steps. The explicit scheme is the least accurate and can be unstable, but is also the easiest to implement and the least numerically intensive. The implicit scheme works the best for large time steps."

As you said stability can also be an issue so that will have been taken in to account when choosing the scheme.

The wikipedia article also has a little more detail about the advantages/disadvantages of each, the bit on errors may be particularly helpful: https://en.wikipedia.org/wiki/Finite_difference_methods#Example:_The_heat_e...

Im in no way familiar with sediment transport, but presumably you're looking at fairly large time intervals which would make the implicit method a good choice as it's relatively accurate with long time steps (i.e. less computation needed to run the model for long time periods.)

Other than that finite difference methods are just a way of solving differential equations. The real magic will be in how the differential equation itself is put together, what assumptions are made, why those assumptions are reasonable etc. That'll be where all the parameters will come in to play (although they may then appear when you're solving with the FDM). Having said that there will be a certain amount of tuning step sizes to get the required accuracy while not having a crazy computation time.

You can think of implicit FDM as an algorithm for approximating the solution to differential equations. That is the precise implementation might vary a little but the answer should always be pretty similar (disregarding issues like the numerical precision of the variables used in the program of choice.)

In reply to remus:

superb, thanks again for your help.

In reply to Geoboy:

If you want an example of the different methods for a possibly related field (hydrology) have a look at some of papers published in Water Resources Research by Dmitri Kavetski which start at a basic level.

In terms ODEs and changes over time my way of thinking about it is:

Explicit: value at time (t + dt) = value at time t + dt * gradient at time t

Implicit: value at time (t + dt) = value at time t + dt * gradient at time (t + dt)

with other methods e.g. Rutta-Kunge (sp??) subdividing the time step dt and using (often explicit) methods between the intermediate points generated. The number of subdivision is in some schemes altered until there the value computed at t+dt does not change significantly.

to Geoboy: A slightly crude description would be an implicit scheme solves a time step in terms of itself, where an explicit one solves it in terms of previous time steps.

The biggest problem with an explicit scheme is stability. If the propagation of physical information (as determined by the local sound speed) travels faster than the 'computational' speed, the system is likely to be unstable - so if you're calculating results at one grid point based on the solution at neighbouring grid points at the previous time, but physically the wave front will have travelled further than the distance between them, you can see you will have a problem!

In practice this means the time step must be controlled such that it is linked to the size of the smallest elements. For smaller cells you need smaller time steps. This is called the CFL condition.

Implicit schemes can be shown to be unconditionally stable, so the time step can be arbitrarily large. If you're after long time scales or steady state values, they can be very useful. Though as a previous poster suggested they can be more tricky to formulate and solve efficiently.

They can have problems if you have conditions where your PDE is likely to become unbounded (singularities), but assuming your system is well behaved this isn't an issue.

In reply to Liam M:

Thanks scruff and Liam for the replies! This is all really helpful. Glad I posted on here.
Given the type of model and it's aim of representing physical processes interacting over time scales on hundreds of thousand or millions of years the implicit scheme sounds more appropriate than explicit.

In reply to Geoboy:

Implicit vs explicit is only really applicable to finite differences in time, not space. (For the spacial dimensions, the use of central differences is straightforward.) The explicit method expresses the value of a variable at the next time step t+1 in terms of its values at the current time step t, with extrapolation of rates at time t forward to time t+1. This is the intuitive way. The implicit method expresses the value at time t in terms of its values at time t+1, which mathematically it is not so easy and may require some iterations to provide sufficiently accurate values of dependent variables at time t+1. But the implicit method has the *massive advantage* (in software that is going to be used for a wide range of conditions) that it is unconditionally stable. The Crank-Nicholson method is a kind of compromise between the explicit and implicit methods, rather like a central difference in time. It used to be highly touted and works well for very simple problems, but in practice (I have found) it is a disaster - avoid it at all costs. In a wide range problems, the implicit method is by far the most reliable. One major issue is the time step size to use, and again across a wide range of heat and mass transfer problems I have found about 400 to 500 time steps, across an entire time evolution, is a good compromise, i.e., 200 or 300 is too little for accuracy, whereas 600 to 1000 is overkill.

In reply to John Stainforth:

cheers john! Really appreciate the help.