Bulirsch–Stoer vs Runge-Kutta

357 views
Skip to first unread message

Daniel Carrera

unread,
Mar 2, 2011, 5:26:29 PM3/2/11
to
Hello,

I hope you'll forgive a completely non-Fortran question. I have been
unable to find useful information with Google. Does anyone know an
online reference that explains when Runge-Kutta is the best way to
solve an ODE and when the Bulirsch–Stoer works best?

All I can find is pages explaining how they work, but nothing that
compares them.

Thanks.

Daniel.

Dieter Britz

unread,
Mar 3, 2011, 6:12:34 AM3/3/11
to
Daniel Carrera wrote:

Well, Press et al write that B_S is the "best known way to obtain
high-accuracy solutions... with minimal computational effort". I
don't know how they reached that conclusion though.
--
Dieter Britz (dieterhansbritz<at>gmail.com)

Phillip Helbig---undress to reply

unread,
Mar 3, 2011, 7:51:52 AM3/3/11
to
In article <iknt7f$fi5$3...@news.eternal-september.org>, Dieter Britz
<br...@chem.au.dk> writes:

> > I hope you'll forgive a completely non-Fortran question. I have been
> > unable to find useful information with Google. Does anyone know an
> > online reference that explains when Runge-Kutta is the best way to

> > solve an ODE and when the Bulirsch-Stoer works best?


> >
> > All I can find is pages explaining how they work, but nothing that
> > compares them.

Why not just try them out with your own problem? It could be that what
works best for most people doesn't work best for you.

B-S can be a lot faster if the equation is reasonably well behaved, but
if not, R-K could be better. You really have to suck it and see.

Ian Gay

unread,
Mar 3, 2011, 1:41:35 PM3/3/11
to
Daniel Carrera wrote:

Why not ask in sci.math.num-analysis?
--
*********** To reply by e-mail, make w single in address **************

Daniel Carrera

unread,
Mar 3, 2011, 2:03:08 PM3/3/11
to
On Mar 3, 1:51 pm, hel...@astro.multiCLOTHESvax.de (Phillip Helbig---

undress to reply) wrote:
> Why not just try them out with your own problem?  It could be that what
> works best for most people doesn't work best for you.

I'll do that, but I also hoped to have a general sense of when each
method is likely to do best.

> B-S can be a lot faster if the equation is reasonably well behaved, but
> if not, R-K could be better.  You really have to suck it and see.

Thanks.

Daniel.

Daniel Carrera

unread,
Mar 3, 2011, 2:03:25 PM3/3/11
to
On Mar 3, 7:41 pm, Ian Gay <g...@sfuu.ca> wrote:
> Why not ask in sci.math.num-analysis?

Will do. Thanks.

none

unread,
Mar 4, 2011, 6:28:48 PM3/4/11
to

Years ago, when Numerical Recipes was recently out in its 1st edition, I
was modelling a sludge digester. The digester was operated as draw and
fill - i.e., a fraction of the volume was withdrawn, then fresh sludge
added to make up the volume. This resulted in a discontinuous aspect to
the equations. BS failed miserably, while the RK4 technique - using
step-halving for accuracy control - perfromed quite well. I had access to
the NAg library, and used their RK4 method - RK-Merson - and that also
failed. I have since used the RK23 code in Netlib, and RKF45, and both
have performed well.

So: BS failed for a problemwhere it should fail. BS is advised for the
case where the following holds:

1. Smooth differential equations. (I had many discontinuities)
2. High accuracy required. (Modelling sewage sludge moderate accuracy was
good enough)
3. Not too much output. (I wanted to track what was happening at c. 15
minute intervals for a period of several weeks to a year)

nm...@cam.ac.uk

unread,
Mar 5, 2011, 4:20:41 AM3/5/11
to
In article <pan.2011.03.04....@none.net>,

none <no...@none.net> wrote:
>
>Years ago, when Numerical Recipes was recently out in its 1st edition, I
>was modelling a sludge digester. The digester was operated as draw and
>fill - i.e., a fraction of the volume was withdrawn, then fresh sludge
>added to make up the volume. This resulted in a discontinuous aspect to
>the equations. BS failed miserably, while the RK4 technique - using
>step-halving for accuracy control - perfromed quite well. I had access to
>the NAg library, and used their RK4 method - RK-Merson - and that also
>failed. I have since used the RK23 code in Netlib, and RKF45, and both
>have performed well.

Rather longer ago that that, I was working on multi-dimensional
scaling, which has the property that it has a set of fairly
well-defined local minima, but where discontinuities are dense
(but in the same direction as the slope). Steepest descents
worked; little else did.

There is a fairly general rule that the less well-behaved the
problem you have, the cruder a method you must use, because all
fancy methods need to make more assumptions. Runge-Kutta is a
bit odd, but also blows up quite spectacularly given a hostile
enough function. For some, there is little option but simple
step-by-step approximation.

As a side-note, IBM SSP contained the only matrix inversion code
that I have ever seen that succeeded in inverting a singular 3x3
matrix - AND returning elements of the same order as the input!
Impressive. Harwell and NAG didn't like the matrix at all :-)


Regards,
Nick Maclaren.

Ron Shepard

unread,
Mar 5, 2011, 12:03:52 PM3/5/11
to
In article <iksv99$gff$1...@gosset.csi.cam.ac.uk>, nm...@cam.ac.uk
wrote:

> As a side-note, IBM SSP contained the only matrix inversion code
> that I have ever seen that succeeded in inverting a singular 3x3
> matrix - AND returning elements of the same order as the input!
> Impressive.

Yes, that does sound like a, umm, truly remarkable accomplishment.
:-)

$.02 -Ron Shepard

glen herrmannsfeldt

unread,
Mar 6, 2011, 4:18:29 AM3/6/11
to
nm...@cam.ac.uk wrote:
(snip on integration algorithms)

> Rather longer ago that that, I was working on multi-dimensional
> scaling, which has the property that it has a set of fairly
> well-defined local minima, but where discontinuities are dense
> (but in the same direction as the slope). Steepest descents
> worked; little else did.

> There is a fairly general rule that the less well-behaved the
> problem you have, the cruder a method you must use, because all
> fancy methods need to make more assumptions. Runge-Kutta is a
> bit odd, but also blows up quite spectacularly given a hostile
> enough function. For some, there is little option but simple
> step-by-step approximation.

I always liked Gaussian quadrature, though its assumptions
likely cause problems with some functions. With no prediction,
it shouldn't get too confused. The old trick of running with
different order and checking that the result isn't too different
should still work.



> As a side-note, IBM SSP contained the only matrix inversion code
> that I have ever seen that succeeded in inverting a singular 3x3
> matrix - AND returning elements of the same order as the input!
> Impressive.

The code is still around, if anyone wants to try it.

> Harwell and NAG didn't like the matrix at all :-)

-- glen

Marco Amarante

unread,
Aug 5, 2022, 7:50:10 AMAug 5
to
--


PRESERVE A NATUREZA, EVITE O DESPERDÍCIO DE PAPEL E PENSE ANTES DE
IMPRIMIR.

"Responsabilidade com o MEIO AMBIENTE"

Esta mensagem e
quaisquer arquivos em anexo podem conter informações confidenciais e/ou
privilegiadas. Se você não for o destinatário ou a pessoa autorizada a
receber esta mensagem, por favor não leia, copie, repasse, imprima, guarde,
nem tome qualquer ação baseada nestas informações. Por favor notifique o
remetente imediatamente por e-mail e apague a mensagem permanentemente.
Este ambiente está sendo monitorado para evitar o uso indevido de nossos
sistemas.

Marco Amarante

unread,
Aug 5, 2022, 7:51:03 AMAug 5
to
Em domingo, 6 de março de 2011 às 06:18:29 UTC-3, glen herrmannsfeldt escreveu:
I would like to present my article to the group:

https://brazilianjournals.com/ojs/index.php/BRJD/article/view/46840

Arjen Markus

unread,
Aug 5, 2022, 10:41:56 AMAug 5
to
On Friday, August 5, 2022 at 1:51:03 PM UTC+2, Marco Amarante wrote:
...
> I would like to present my article to the group:
>
> https://brazilianjournals.com/ojs/index.php/BRJD/article/view/46840
> --
>
You do not happen to have an English version of it? My understanding of Portuguese is rather limited, even though I can of course recognise the equations ;).

Regards,

Arjen

Marco Amarante

unread,
Aug 19, 2022, 12:23:55 PMAug 19
to

Marco Amarante

unread,
Aug 19, 2022, 12:24:43 PMAug 19
to
Em sexta-feira, 5 de agosto de 2022 às 11:41:56 UTC-3, arjen.m...@gmail.com escreveu:
Arjen

I can write an English version of it if participants are interested

Regards, ,

Marco Aurelio Amarante Ribeiro

Arjen Markus

unread,
Aug 22, 2022, 10:43:04 AMAug 22
to
On Friday, August 19, 2022 at 6:24:43 PM UTC+2, Marco Amarante wrote:
> Em sexta-feira, 5 de agosto de 2022 às 11:41:56 UTC-3, arjen escreveu:
> > On Friday, August 5, 2022 at 1:51:03 PM UTC+2, Marco Amarante wrote:
> > ...
> > > I would like to present my article to the group:
> > >
> > > https://brazilianjournals.com/ojs/index.php/BRJD/article/view/46840
> > > --
> > >
> > You do not happen to have an English version of it? My understanding of Portuguese is rather limited, even though I can of course recognise the equations ;).
> >
> > Regards,
> >
> > Arjen
> Arjen
>
> I can write an English version of it if participants are interested
>
> Regards, ,
>
That might be interesting indeed :).

Regards,

Arjen

Arjen Markus

unread,
Aug 22, 2022, 2:35:17 PMAug 22
to
On Monday, August 22, 2022 at 4:43:04 PM UTC+2, Arjen Markus wrote:

> >
> > I can write an English version of it if participants are interested
> >
> > Regards, ,
> >
> That might be interesting indeed :).
>
> Regards,
>
> Arjen

On Wikipedia I found a short description of the method with several caveats: according to some authors there is little to gain with the techniques that Bulirsch-Stoer depends on. Do you share that conclusion?

Regards,

Arjen

Phillip Helbig (undress to reply)

unread,
Sep 1, 2022, 4:28:55 AMSep 1
to
In article <bdfb06b3-90b3-40a8...@googlegroups.com>,
Arjen Markus <arjen.m...@gmail.com> writes:

> On Monday, August 22, 2022 at 4:43:04 PM UTC+2, Arjen Markus wrote:
>
> > >
> > > I can write an English version of it if participants are interested
> > >
> > > Regards, ,
> > >
> > That might be interesting indeed :).
> >
> > Regards,
> >
> > Arjen
>
> On Wikipedia I found a short description of the method with several
> caveats: according to some authors there is little to gain with the
> techniques that Bulirsch-Stoer depends on. Do you share that conclusion?

I once coded a real-world application where Bulirsch-Stoer worked better
than Runge-Kutta (though using polynomial rather than rational-function
extrapolation).

I think that Bulirsch-Stoer is one of the great ideas of numerical
analysis.

gah4

unread,
Sep 1, 2022, 5:07:41 AMSep 1
to
On Thursday, September 1, 2022 at 1:28:55 AM UTC-7, Phillip Helbig (undress to reply) wrote:

(snip)

> I think that Bulirsch-Stoer is one of the great ideas of numerical
> analysis.

I used to know some of this, but I forget now.

The only one I remember is that higher than 4th order Runge-Kutta
isn't better, in terms of step size and number of function evaluations.

With small enough step size, it doesn't make so much difference.

Robin Vowels

unread,
Sep 1, 2022, 5:42:03 AMSep 1
to
.
The algorithm Bulirsch–Stoer if far more complicated than Runge-Kutta.
Look in Numerical Recipes in C for the former.

Ron Shepard

unread,
Sep 1, 2022, 10:12:48 AMSep 1
to
I remember reading about Bulirsch–Stoer in Numerical Recipes (the first
edition in fortran, not the C version a decade later). The authors were
big proponents of the method.

$.02 -Ron Shepard

Thomas Koenig

unread,
Sep 1, 2022, 12:50:53 PMSep 1
to
gah4 <ga...@u.washington.edu> schrieb:
> On Thursday, September 1, 2022 at 1:28:55 AM UTC-7, Phillip Helbig (undress to reply) wrote:
>
> (snip)
>
>> I think that Bulirsch-Stoer is one of the great ideas of numerical
>> analysis.
>
> I used to know some of this, but I forget now.
>
> The only one I remember is that higher than 4th order Runge-Kutta
> isn't better, in terms of step size and number of function evaluations.

This really depends.

If you are trying to integrate x'' + x = 0, as smooth as you can
get, then higher order will help.

If your function is less well behaved, then lower order will be
better, and if your system of equations is stiff, you will have
to use quite different solvers.

> With small enough step size, it doesn't make so much difference.

Unless you make it too small and get cancellation in your
difference quotients :-)
Reply all
Reply to author
Forward
0 new messages