1
$\begingroup$

I have a system of 256 differential equations that I want to solve numerically. The system represents the Liouville equation, which is a first order, linear differential equation with complex numbers.

What's the best method to solve this equation in parallel? Please advise.

I'm a physicist, so I'm familiar with the basic solvers (Euler and Runge-Kutta), which are basically sequential by definition.

$\endgroup$
9
$\begingroup$

256 equations is a relatively small number. All of the usual integrators, such as those included in Matlab, Maple or Mathematica should have no real problem with equations of this size and should be able to return answers in a fraction of the time it would take an algorithm you would implement yourself, because they use sophisticated explicit/implicit and adaptive time stepping methods.

ODE solvers are, for the most part, a solved problem. Don't waste your time implementing one yourself -- just use what others have done before you.

$\endgroup$
  • $\begingroup$ Actually I tried solving them with mathematica, and the interpolator's time length was really embarrassing... it was like 10^-8 in 10000 steps, whil I need something like 100 seconds at least. I think writing my own Runge-Kutta with necessary tests on C++ wouldn't take more than 2 hours. Besides, this 256 equations is just the initial problem for F=3 and F=4 magnetic sublevels of the S angular momentum, when I include P, I'll have 48*48 equations... and perhaps more. So I need something which is parallelizable. $\endgroup$ – The Quantum Physicist Oct 25 '13 at 8:26
  • $\begingroup$ Are you using explicit Euler and explicit Runge-Kutta methods? I'm surprised that the step size is so small. Is your problem stiff? $\endgroup$ – Geoff Oxberry Oct 25 '13 at 9:53
  • 1
    $\begingroup$ Mathematica probably had a reason why it took such small time steps. What are the shortest time scales in your problem? If the smallest time scale is $10^{-12}$, then any code you write yourself isn't going to be able to take larger steps either. $\endgroup$ – Wolfgang Bangerth Oct 25 '13 at 12:29
4
$\begingroup$

I would disagree with your statement that Euler and Runge-Kutta have to be sequential. I know that you are saying this because you cannot parallelize across time steps (or across inner time steps in the case of something like RK4), however both can be parallel as long as you do so within a single time step. You would simply evaluate the derivatives of your 256 variables in parallel.

Depending on your system characteristics, it is possible that RK methods would be the best for you, or perhaps a simple stiff solver. I personally am not familiar with parallel implementations so I will leave the recommendations to others with much more experience than myself. Unless your system is something incredibly special though, you will be using algorithms that you are more than likely familiar with.

$\endgroup$
  • $\begingroup$ Actually I would like to parallelize in terms of time-steps, not the equations. Thanks though. $\endgroup$ – The Quantum Physicist Oct 24 '13 at 20:09
  • 2
    $\begingroup$ How can you be parallel in terms of time-steps when each step depends on the result of the previous one? $\endgroup$ – AlexE Oct 25 '13 at 8:52
4
$\begingroup$

From the comments, it sounds like your problem is stiff, and using an implicit integrator will help you a lot more than trying to parallelize. But in case someone comes here looking for information on parallel time integration, you can find a discussion of some simple parallel extrapolation and deferred correction methods in this preprint of mine. It's not a new topic; you can trace the references backward starting from the bibliography there. For more sophisticated methods, see answers to this question.

Parallelism in time is possible, but is only useful if you need high accuracy (relative to what a cheap stable integrator will give you).

$\endgroup$
2
$\begingroup$

You may want to look at parareal methods, that is, a parallel-in-time approach. There can be huge gains in speedup, but there are some issues with stability. The paper by Lions, Maday & Turinici (2001) would be a good place to start if you're not familiar with the method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.