Previous ToC Up Next

7. Efficiency

7.1. Pure Thought

Bob: There is one thing we haven't checked yet. The whole motivation for going to variable time steps was to improve accuracy, for the same amount of computer time. Or to put it differently, to save computer time, if the goal is to reach a certain accuracy.

Alice: Good idea. Let's check that.

Bob: It is pretty clear, on general grounds, that an adaptive algorithm must be more accurate, but I like to see by how much.

Alice: I don't think it is always clear, since there are algorithms that do a lot better for constant time steps than for variable time steps. The leapfrog is an example of an algorithm that is almost unreasonably accurate in energy conservation, basically because it is time symmetric. But that symmetry property is lost when you allow the time steps to become variable, unless you make sure that your time step criterion is again time symmetric, something we haven't done here.

Bob: That may be, but in general, adaptive algorithms should do better, as a rule of thumb.

Alice: Well, yes, in the limit of many particles and relatively large time steps you must be right, for sure. And most importantly, an adaptive time step scheme is safer, since particles are guaranteed not to suddenly run into each other. If you don't have softening, and you choose a fixed time step, you can never guarantee that you don't accidentally step on another particle. I mean, you could reach another particle in one time step, which would result in a huge energy error.

Bob: With all this pure thought, let's do a hard-nosed test. I think we've done something like this already, but let's run it again, from the same initial conditions:

 |gravity> kali mkplummer.rb -n 4 -s 1 | kali nbody_set_id.rb > test
 ==> Takes an N-body system, and gives each body a unique ID <==
 value of @body_id for 1st body : n = 1
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 ==> Plummer's Model Builder <==
 Number of particles            : N = 4
 pseudorandom number seed given : 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
              actual seed used  : 1

7.2. Concrete Results

Alice: And we may as well start with the same type of accuracy requirements as we did before.

Bob: Here is the shared time step version:

 |gravity> kali nbody_sh1.rb -t 1 -c 0.01 --exact_time -o 2 < test.in
 ==> Shared Time Step Code <==
 Integration method             : method = hermite
 Parameter to determine time step size: dt_param = 0.01
 Interval between diagnostics output: dt_dia = 1.0
 Time interval between snapshot output: dt_out = 2.0
 Duration of the integration    : t = 1.0
 Force all outputs to occur at the exact times
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 at time t = 0, after 0 steps :
   E_kin = 0.25 , E_pot =  -0.5 , E_tot = -0.25
              E_tot - E_init = 0
   (E_tot - E_init) / E_init = -0
 at time t = 1.00035, after 1927 steps :
   E_kin = 0.312 , E_pot =  -0.562 , E_tot = -0.25
              E_tot - E_init = -2.26e-10
   (E_tot - E_init) / E_init = 9.03e-10
And here is the constant time step version:

 |gravity> kali nbody_cst1.rb -c 0.001 -t 1 -o 2 < test.in
 ==> Constant Time Step Code <==
 Integration method             : method = hermite
 Softening length               : eps = 0.0
 Time step size                 : dt = 0.001
 Interval between diagnostics output: dt_dia = 1.0
 Time interval between snapshot output: dt_out = 2.0
 Duration of the integration    : t = 1.0
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 at time t = 0, after 0 steps :
   E_kin = 0.25 , E_pot =  -0.5 , E_tot = -0.25
              E_tot - E_init = 0
   (E_tot - E_init) / E_init = -0
 at time t = 1, after 1000 steps :
   E_kin = 0.248 , E_pot =  -0.613 , E_tot = -0.365
              E_tot - E_init = -0.115
   (E_tot - E_init) / E_init = 0.461
Alice: Well, the constant time step version seems to do a somewhat better job! I suggest you increase the timestep a bit, to bring out the difference more clearly.

Bob: Okay, I'll make the timestep 0.00125 time units:

 |gravity> kali nbody_cst1.rb -c 0.00125 -t 1 -o 2 < test.in
 ==> Constant Time Step Code <==
 Integration method             : method = hermite
 Softening length               : eps = 0.0
 Time step size                 : dt = 0.00125
 Interval between diagnostics output: dt_dia = 1.0
 Time interval between snapshot output: dt_out = 2.0
 Duration of the integration    : t = 1.0
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 at time t = 0, after 0 steps :
   E_kin = 0.25 , E_pot =  -0.5 , E_tot = -0.25
              E_tot - E_init = 0
   (E_tot - E_init) / E_init = -0
 at time t = 1, after 800 steps :
   E_kin = 0.219 , E_pot =  -0.706 , E_tot = -0.487
              E_tot - E_init = -0.237
   (E_tot - E_init) / E_init = 0.948
Alice: With nearly the same number of time steps, the constant time step is scheme is more accurate by almost a factor two.

Bob: Hmmm. So much for all that hard work, to make the time step adaptive!

7.3. More is Different

Alice: Well, we are dealing only with five particles, and we are running at relatively high accuracy. I sugest we increase the number of particles and decrease the accuracy. At some point the adaptive time step scheme should win out from the constant time step scheme.

Bob: Okay, five times more particles:

 |gravity> kali mkplummer.rb -n 25 -s 1 | kali nbody_set_id.rb > test2.in
 ==> Takes an N-body system, and gives each body a unique ID <==
 value of @body_id for 1st body : n = 1
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 ==> Plummer's Model Builder <==
 Number of particles            : N = 25
 pseudorandom number seed given : 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
              actual seed used  : 1
And a ten times longer time step. The shared time step code should be able to handle that gracefully.

 |gravity> kali nbody_sh1.rb -t 1 -c 0.1 --exact_time -o 2 < test2.in
 ==> Shared Time Step Code <==
 Integration method             : method = hermite
 Parameter to determine time step size: dt_param = 0.1
 Interval between diagnostics output: dt_dia = 1.0
 Time interval between snapshot output: dt_out = 2.0
 Duration of the integration    : t = 1.0
 Force all outputs to occur at the exact times
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 at time t = 0, after 0 steps :
   E_kin = 0.25 , E_pot =  -0.5 , E_tot = -0.25
              E_tot - E_init = 0
   (E_tot - E_init) / E_init = -0
 at time t = 1.00125, after 2418 steps :
   E_kin = 0.212 , E_pot =  -0.462 , E_tot = -0.25
              E_tot - E_init = -9.92e-05
   (E_tot - E_init) / E_init = 0.000397
Alice: Indeed. I'm not so sure about the constant time step scheme.

Bob: Perhaps less gracefully, we have to see:

 |gravity> kali nbody_cst1.rb -c 0.01 -t 1 -o 2 < test2.in
 ==> Constant Time Step Code <==
 Integration method             : method = hermite
 Softening length               : eps = 0.0
 Time step size                 : dt = 0.01
 Interval between diagnostics output: dt_dia = 1.0
 Time interval between snapshot output: dt_out = 2.0
 Duration of the integration    : t = 1.0
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 at time t = 0, after 0 steps :
   E_kin = 0.25 , E_pot =  -0.5 , E_tot = -0.25
              E_tot - E_init = 0
   (E_tot - E_init) / E_init = -0
 at time t = 1, after 100 steps :
   E_kin = 0.245 , E_pot =  -0.363 , E_tot = -0.118
              E_tot - E_init = 0.132
   (E_tot - E_init) / E_init = -0.527
Indeed, quite a bit less. Let's bring the number of time steps in line with that of the shared time step code:

 |gravity> kali nbody_cst1.rb -c 0.005 -t 1 -o 2 < test2.in
 ==> Constant Time Step Code <==
 Integration method             : method = hermite
 Softening length               : eps = 0.0
 Time step size                 : dt = 0.005
 Interval between diagnostics output: dt_dia = 1.0
 Time interval between snapshot output: dt_out = 2.0
 Duration of the integration    : t = 1.0
 Screen Output Verbosity Level  : verbosity = 1
 ACS Output Verbosity Level     : acs_verbosity = 1
 Floating point precision       : precision = 16
 Incremental indentation                : add_indent = 2
 at time t = 0, after 0 steps :
   E_kin = 0.25 , E_pot =  -0.5 , E_tot = -0.25
              E_tot - E_init = 0
   (E_tot - E_init) / E_init = -0
 at time t = 1, after 200 steps :
   E_kin = 410 , E_pot =  -0.31 , E_tot = 410
              E_tot - E_init = 410
   (E_tot - E_init) / E_init = -1.64e+03
Good. The shared time step code is a lot better now, by orders of magnitude.

Alice: So all the hard work did pay off, after all!
Previous ToC Up Next