Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am currently using Euler method and it is 4-8 times too slow. Which method will be fastest? I need it to compute Turing's reaction-diffusion system.

share|improve this question
1  
Are you sure it is Euler's method that is slowing you down, and not the implementation? What language are you using? Is it a built-in or library function? What is your data set like? What sort of machine are you performing the calculation on, and with how much RAM? When you say it is 4-8 times too slow, what is this relative to and what timing benchmarks have led you to this conclusion? –  prpl.mnky.dshwshr Jul 21 '12 at 22:18
    
What do you mean it is '4-8 times too slow'? Compared with what? –  copper.hat Jul 21 '12 at 22:30
    
@EMS, cooper.hat: I run it on iPad and iPod. It is implemented in C. By the 4-8 times I mean: user can wait 1-2 seconds for computation of the result, but it takes 8-12 seconds with the Euler method. The data set is 256x256 array of doubles, being direct source of final image. If I do 100 iterations, then there are 100 * 256 * 256 loop executions. –  AllCoder Jul 21 '12 at 22:37
    
Forward Euler, backward Euler? Have you tried a large step size? –  copper.hat Jul 21 '12 at 22:41
    
Also, FYI this question is probably better suited for either SciComp or Stack Overflow. It's not clear that this is due to your chosen algorithm. It could easily be due to an inefficient C implementation. If you post some code along with the question at either of those other sites, you'll almost surely get better help... and folks on those sites will also be able to suggest other mathematical algorithms to try if indeed that is the right way to solve the problem. –  prpl.mnky.dshwshr Jul 21 '12 at 22:58

1 Answer 1

up vote 1 down vote accepted

Euler's method is the fastest possible single-step, explicit, non-adaptive method for a given fixed step size $h$.

If this is too slow, I would do the following things, in this order.

  1. Perform a fundamental analysis on your code. Insert breakpoints. Ensure that you're not doing things like repeatedly re-sizing arrays. Replace loops with better code (a first-order explicit ODE solver should have one "loop": one walk through the code, from $t=0$ to $t=T$.)
  2. Increase step size. Compute what your acceptable error tolerance is, and make $h$ be as large as possible to keep your solution within that error bound.
  3. Implement an adaptive-step size solver. These are usually faster for a given accuracy, but are more complicated. Dormand-Prince 4(5) pairs is a standard adaptive RK method.

I'm willing to bet that you can solve your speed problem with step (1) (hint: if you're iterating through 256x256 elements, you don't need to necessarily encapsulate the method in a double loop).

share|improve this answer
    
It is true that I do use two nested loops.. Code is on SciComp: scicomp.stackexchange.com/questions/2887/euler-method-too-slow –  AllCoder Jul 22 '12 at 0:47
    
Have you profiled the code? I have had many surprises with c++. (Try inlining set_torus, for example.) –  copper.hat Jul 22 '12 at 4:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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