source: proiecte/NBody/Tree codes/README.txt @ 170

                                                                        Tree code - README

1. Agorithm description

        The tree code approach provides a fast general integrator for collisionless systems. The idea a tree code is based on is grouping bodies that have similar positions into groups of bodies that have similar interaction lists.  The main steps of the algorithm are building the tree and computing the forces.
        When building the tree, three main data structures were used: node, body and cell. A cell represents a structure that contains one or more bodies. It's actually a group of bodies. The "body" structure represents the particles that can be found in the system at a certain time. The "node" structure contains information commun to bodies and cells. The tree is constructed from the root by splitting the simulated volume into rectangular cubes. The tree structure is therefore called octal-tree or simply oct-tree. The division is accomplished by splitting each of the Cartesian dimension to a half. This repeatedly continues until the cube contains more than one body. If there is only one body in the cube left, it is stored as a leaf in the tree structure. When the cube is empty, it is ignored. The tree is composed of a hierarchical arrangement of leaves, nodes and the root. Using our data structures the bodies are the leaves of the tree and the cells are internal branches.
        Forces on bodies are computed during a single recursive scan of the entire tree. The forces calculated are the gravitational force and the potential energy. Optionaly the Kynetic energy and the initial and total energy of the system can be calculated in order to check that the results of the program are correct.

2. Run and compile

Compilation of the program can be made using the makefile in the archive issuing the console command:
        make treecode

The running of the program can be done with or without parameters. The program computes the initial conditions using the Plummer model if no initial paramateres are set in the command line
Example of running command with parameters
        treecode in=input.data out=output.data dtime=0.001 tstop=10 dtout=1.0 nbody=1000
The parameters used in the line above are:
                in              Input file with the initial conditions
                out             Output file
                dtime   Integration time step
                tstop   Time to stop the integration
                dtout   Data output timestep
                nbody   Total number of bodies during the simulation            

For finding out the time necessary for the program to run we can use:
        time ~p treecode in=input.data out=output.data dtime=0.001 tstop=10 dtout=1.0 nbody=1000


3. Input file example

N
t
m1 r1_x r1_y r1_z v1_x v1_y v1_z
.....
mN rN_x rN_y rN_z vN_x vN_y vN_z

N is the total number of particles in the systems
t represents the total time for the simulation
mi - represents the mass of the particle
ri_y, ri_x, ri_z - the position of the particle
vi_y, vi_x, vi_z - the velocity of the particle
Even though the total time of the simulation can be given through the command line parameters I chose this type of input file because it was the one used in the original Nbody simulation source code.

4. Output file example

N
dt
m1 r1_x r1_y r1_z v1_x v1_y v1_z
.....
mN rN_x rN_y rN_z vN_x vN_y vN_z

N is the total number of particles in the systems
dt represents the time step in which the output was produced
mi - represents the mass of the particle
ri_y, ri_x, ri_z - the position of the particle
vi_y, vi_x, vi_z - the velocity of the particle

This is just one sequence of the output file.  The number of sequences included in an ouptut file is equal to tstop/dtout. We need dtout to be very small in comparison to tstop in order to have as many frames as possible to use in the OpenGL representation of the results.