Journal

May 3

I am finished with the talk, what remains to be done is tweak a few parts of the code and add some comments.

The website I used for my talk can be found here

April 30

I have spent most of my time on the final presentation and the final paper, I also did a bit of debugging, my init function was giving me some trouble but it seems to be fine now after a quick fix.

My new interface can be found here

April 28

I have been looking into some Java optimization with no luck. I have tried running the applet on the apple cluster in the E&I lab just to see how much faster it would run, and it behaved as I expected, there was no dramatic increase in performance.

April 24

I have expanded the code to include oct-trees for a possible 3d simulation. I have been working on the final presentation slides.

April 20

April 17

Finished my treForce function, I am now working on setting up a basic demo of the project to show next week, it will probably resemble my first demo, this time using the tree structure and a variable number of bodies.

My Todo list is looking good, everything is on track and I should be fine with the time that is left. The only thing that worries me is having realistic conditions so that I can get results that resemble the evolution of a real galaxy. I will be working on that after my demo.

Here is a look at what is done and needs to be done from my todo list:

Decide topics of interest
Project Web Log
Bibliography
Research for survey
Decide on specific project topic
Research integration schemes
Code integration schemes
Survey presentation
Code CM calculator & use in demo
Write project proposal
Body.java class implementation
Code quadrant data type
Code tree data type
Code QuadtreeBuild function
Research initial conditions
Hardcode initial conditions
Code TreeForce function
Integrate code modules
GUI development (part of it is done)
Testing/Debugging
Write final paper
Prepare final presentation
Colloquium

April 10

Started coding the TreeForce function: This function will compute gravitational force on a particle through a post-order traversal of the quadtree. I am having to look back to the work I did in my Algorithms and Data Structures class to remember how to write a post order tree traversal. It is actually quite fun.

April 3

Have been researching initial conditions for the galaxy simulator. I have lots of papers which describe the initial velocities and rotations they used, so I am basing my simulation off of these results. In order to model a galaxy, one needs to set up the particles in such a way as to most resemble a configuration in a real disk galaxy. This means that particles need to be started on a circular orbit, with some comparatively small radial velocity distributions.

March 29

Coded the basic tree data type: The tree data type forms the base of this simulation; it contains some data (a body and a quadrant), plus four references to other quad-trees. At the moment I am respresnting it as a Java class:

public class QTree {
private Body body; // body or aggregate body stored in this node
private Quad quad; // square region that the tree represents
private QTree NW; // tree representing northwest quadrant
private QTree NE; // tree representing northeast quadrant
private QTree SW; // tree representing southwest quadrant
private QTree SE; // tree representing southeast quadrant
}

March 26

March 24

Finished implementing the basic body class. The Body data type represents both individual bodies and groups of bodies . I had a older version that I used for my PP demo, so I just updates it to include CM's and groups of bodies.

March 12-21

I have been coding the Runge-Kutta integration scheme as well as the Euler method. An essential part of the algorithm will be that of the integrator, so I have put special care in coding these pieces. The integrator of the galaxy simulator should be able to advance particles in a specified potential field. This potential can result of a combination of self- gravitating system and an analytic background potential. Several schemes can be employed, ranging from minimal computational cost and poor accuracy to high computational cost and high accuracy.

Refined a piece of code that calculates centers of mass of the particles.

March 10,2004

In order to model a galaxy, one needs to set up the particles in such a way as to most resemble a configuration in a real disk galaxy. This means that particles need to be started on a circular orbit, with some comparatively small radial velocity distributions.

I have put a good deal of effort in researching possible initial conditions for the galaxy simulator. There are a number of good papers out there that I will be using as a starting point.

March 8, 2004

Started writing project proposal. Working on the gant chart has really helped me decompose my project into modules. It has also made me confident in that the bulk of the project is already done.

March 1, 2004

I am planning on reporting the following information for next weekend.

Gravitational N-body Problems
An N-Body problem attempts to determine the motion over time of bodies (particles) due to forces from other bodies. Gravitational N-body problems restrict the forces in question to the gravitational forces between bodies. The basic approach is a simulation: loop forever, stepping discretely through time and do the following at each time step:
1.Update positions using velocities (xi+1 = xi + ?t vi )
2.Calculate forces F
3.Update velocities (vi+1 = vi + (1/m) ?t Fi)

Particle-Particle (PP): The simplest and naive method. Accumulate forces by finding the force F(i,j) of particle j on particle i, integrate the equations of motion (including accumulated forces), update the time counter and repeat for the next time step.

I have set up a simple demo as java applet of a particle-particle 3 body problem.

My functions are:

void init()
set up random positions velocoties and masses within a set scale
void start()
start threads and mouse listener

calcDistance(int idx_i, int idx_j)
calculates the distance between two particles
sqrt ((x1 - x2)^2 + (y1 -y2)^2)
public void paint (Graphics g)
paint the planetoids acording to their x and y position
draw text of labels
public final synchronized void update(Graphics g)

public void run() {
double vx_old; //save old velovity values in temporary variables
double vy_old;

for (int i = 0; i < masses; i++) {
vx_old = vx[i];
vy_old = vy[i];
for (int j = 0; j < masses; j++) {
if (i != j) {
R = calcDistance(i, j);
Rm = Math.max(RMIN, R); //is it smaller than the smalest distance=40
vx[i] += DELTA_T * G * m[j] * (x[j] - x[i]) / (Rm * Rm); #update velcities
vy[i] += DELTA_T * G * m[j] * (y[j] - y[i]) / (Rm * Rm);
}
}
x[i] += DELTA_T * vx_old; #update positions with previews velocities
y[i] += DELTA_T * vy_old;
}
repaint();
}
}

*My time step is the same throughout the simulation. There are times when bodies are far away and don't need such a tight time step; there are also times when bodies are really close and it would be good to have this trigger a decrease in time step.

*I am toying with the idea of having a RMAX as well for when objects are to far.

Although this is straight-forward, a constant time-step in the integration could lead to overflow errors - this can be avoided with a numerical integration scheme that uses variable time-steps that cuts down the time-step when the particles are near each other and increase the time-step when they are far away from each other. Computationally it is also expensive: O(N2) operations are required to evaluate the forces on all N particles.

Particle mesh:
This reasoning or algorithmic improvement still has nothing to do with parallelism. It is just a method that exploits knowledge about the system, knowledge about the behavior of the particle-particle interaction. If the interaction does not exactly vanish at distances larger than Rc, one has to decide whether the introduced errors are acceptable or not. In general the behavior of a many-particle system is chaotic anyway, and the smallest change in initial conditions (or algorithmic precision) may eventually lead to large differences in the trajectories of individual particles.

February 25, 2004
I have finished the survey paper and presentation. I felt like I needed more time for the presentation, and although I prepared extensively for it, I felt nervous and it reflected on my talk. I am a little disappointed.

February 17, 2004

I continue to work on survey. Frustrated with some bibliographic information that I lost.

February 10, 2004

Have spent most of my time writing the survey paper. Having to put down all my research on paper has cleared up my thoughts and information I have learned.

February 2, 2004

Worked on my Bibliography

February 1, 2004

Working on organizing my bibliographic information so that I can present next meeting.

Yesterday I spent a good 4 hours reading a book that I had ordered on Amazon.com: The Gravitational Million-Body Problem : A Multidisciplinary Approach to Star Cluster Dynamics. The book describes the gravitational million-body problem as a model for understanding the dynamics of rich star clusters. The author describes the theory astronomers need for studying globular star clusters. After introducing the million-body problem from various view-points, the book seems to systematically develop the tools needed for studying the million-body problems in nature, and introduces the most important theoretical models. I think the book will be of use to me in that it introduces me to the broad issues in the field I am working in.

January 26, 2004

After having looked at several projects that involved n-body simulations, I am a bit worried at the fact that I don't count with the computation power that these projects had at their disposal. Most of these projects executed their code in parallel or on super computers:

The evolution of dark-matter dominated cosmological halos. By: Alvarez, Marcelo; Shapiro, Paul R.; Martel, Hugo. AIP Conference Proceedings, 2001, Vol. 586 Issue 1, p143, 3p; (AN 6178836)

The equilibrium structure of cosmological halos. By: Iliev, Ilian T.; Shapiro, Paul R.. AIP Conference Proceedings, 2001, Vol. 586 Issue 1, p146, 3p; (AN 6178835)

I might find that simulating a galaxy with 300,000 points will end up being to complicated. Perhaps I need to find a better way to abstract the galaxy or drastically reduce the number of points.

January 23, 2004

Have looked into projects that seem related to what I am interested in (simulating a cosmological phenomenon using a n-body technique). There seems to be a good amount of literature in the area yet at the same time there seems to be many things that remain unexplored.

January 20, 2004

Have been reading articles in both Physics and Computer science related journals that describe problems and projects concerning n-body simulation techniques. Following are the articles I have found interesting:

The n-centre problem of celestial mechanics for large energies. By: Knauf, Andreas. Journal of the European Mathematical Society, 2002, Vol. 4 Issue 1, p1, 114p; (AN 6446828)

Stratified reduction of many-body kinetic energy operators. By: Iwai, Toshihiro; Yamaoka, Hidetaka. Journal of Mathematical Physics, Oct2003, Vol. 44 Issue 10, p4411, 25p; DOI: 10.1063/1.1602160; (AN 10876394)

Molecular dynamics simulations of Hg[sup 2+] in aqueous solution including N-body effects. By: Kritayakornupong, Chinapong; Rode, Bernd M.. Journal of Chemical Physics, 3/15/2003, Vol. 118 Issue 11, p5065, 6p; (AN 9208485)

Periodic Solutions of the N-Body Problem (Book). By: Easton, Robert; O'Malley Jr., Robert E.. SIAM Review, Sep2002, Vol. 44 Issue 3, p486, 2p; (AN 7264723)

January 18, 2004

January 17, 2004
Responding to Jim's advice to start thinking about our projects I have started narrowing down my interests. I now know that the project will be based on the fact that in order to account for the observable Universe, any comprehensive theory or model of cosmology must draw from many disciplines of physics, and although it is difficult to incorporate all these physical elements into a single complete model of our Universe, advances in computing methods and technologies have contributed significantly towards our understanding of cosmological models, the Universe, and astrophysical processes within them.
Although at the moment I am not clear on which specific subject in cosmology I would like to simulate and the method I will use for simulating it, I am quite sure that my project will respond to these issues.

January 15, 2004
Senior Seminar has officially started. During our first meeting Jim explained the structure of the class and encouraged us to start thinking about our project and to start delving into its field.