Efficient Algorithms for Molecular Dynamics Simulations
and Other Dynamic Spatial Join Queries
Honours Thesis by Andrew Noske
This page contains all resources (including code) for an honours thesis.
Details of the thesis and a copy of the abstract follow. Basically this
thesis investigated techniques to speed up pair-wise interaction simulations,
such as the Lennard-Jones potential pair model to simulate atoms in a
bulk liquid. This web site was mainly created as a resource for new students
(especially those at JCU) who are just starting honours and have no idea
what to expect.
- >> Thesis (.doc) <<
1.5MB, >> (.pdf) <<
860kB - Latest copy of the final thesis
in original word format and as a pdf.
- >> Complete code (.zip)
<< 11MB - Contains
all testing code used in project, and separate folders containing a
minimal efficient implementation of the code to be used as an engine
layer by students performing pair-wise interaction simulations. See
"about the code" below as you download.
Demo programs only (.zip) << 540kB
- I decided a the option to download just the executables from about
was in order.
Other assessment pieces:
- Project Proposal (.doc) 105kB
- Original project proposal (shows rough timetable and order of assessment)
- Literature Review (.doc) 865kB
- "Dynamic Range Queries in Vector Space"
- a literature review for solving proximity problems in vector space
which I had to do in first semester before getting started on coding.
Reviews many interesting data structures, techniques and concepts not
mentioned in the thesis (since fixed grid performs better than any hierarchical
structures unless data set is highly skewed).
- Seminar 1 (.ppt) 1.2MB
- First seminar/speech we had to deliver. Had to convey to all our IT
lecturers and peers what our project was, our goals and how we intended
to achieve these goals (scientific process).
- Seminar 2 (.ppt) 3.1MB
- Final seminar we had to deliver shortly after submitting our thesis
and summarize all our discoveries/achievements.
to honours course 2004 - Links to the web site which
outlined our assessment (2004).
- References (.enl) 77kB
- EndNote v8 library containing an exhaustive list of papers I found
useful (not just those I've referenced in the thesis). Includes many
good papers about spatial data structures, N-body problems and molecular
dynamics simulations - most include hyperlinks to the pdf's.
- Excel macros (.txt)
3kB - These excel macros were essential
for me to rearrange columns of results in excel in such a way it was
easy to make graphs. Without these arranging several set of results
into columns could take hours.
- Some results in excel (.zip)
6MB - Contains many excel documents with
results and graph - including most of those used in the thesis, and
numerous others. For every graph in the thesis there were probably 3
or more I left out.
- Thesis Title: Efficient Algorithms for Molecular
Dynamics Simulations and Other Dynamic Spatial Join Queries.
- Author: Andrew Noske
- Department of Information Technology
- James Cook University, Cairns Campus
This thesis investigates several methods of optimising molecular dynamics
simulations using a cutoff radius. The verlet neighbour list technique,
combined with a fixed grid to execute range searches, is accepted as the
most efficient method for performing such simulations, however building
a list of neighbour atoms within the cutoff radius of each other takes
the bulk of processor time. Optimising this self-spatial join query problem
is critical to improving simulation speed, and the primary focus of this
thesis. Some proposed techniques, such as selective checking of verlet
neighbours and using half range searches to execute self-spatial join
queries, produced good performance improvements. Several other techniques,
including space-filling curves and use of minimum bounding rectangles,
yielded poorer than expected results. The thesis also compares and evaluates
the traditional cell list, a minimum cell list and an atom list technique.
It is argued that the atom list is superior. Furthermore, the optimal
number of cells per side for the fixed grid and optimal verlet radius
for the verlet neighbour list are also analysed. Simple algorithms for
dynamically finding the optimal number of cells per side and optimal verlet
radius are tested. This thesis is valuable as a guide to implementing
and optimising molecular dynamics simulations, but also relevant to those
investigating dynamic self-spatial join queries or range queries in “real
world” vector space.
About the Project:
This project was half the assessment for my honours course. I wrote the
assignment in MS word, because I'm use to it, although I'm tempted to
put it into Lyx (Latex), because it will make the formatting much nicer.
I submitted this on the 22/11/2004, and have to bind it by the 16/12.
There are actually many more simulations I would like to perform and results
I would like to redo with larger number of atoms, however each simulation
I run takes approximately 5 minutes to get accurate results, and each
batch of simulations run over 50 of these so that I can obtain a nice
graph.... so obviously it takes hours to get a single set of results.
Another thing I would liked to have done is include a test of statistical
significance showing the deviation of results. Dr Chris Gaskett made this
suggestion when proofing my thesis only a week before it was due, so unfortunately
I had no time to perform an analysis. The accuracy of results was depended
primarily on how long I let the simulation run. He said graphs of statistical
significance were not necessary for a honours thesis, but would be essential
in a PhD thesis.
Dr Phil says that if we could only have a student take up the SIT Cairns
Cluster Computing project for cp3046/cp3047, we would have a better compute
engine for this type of work. See: http://mirriwinni.it.jcu.edu.au/~phillip/cp3046/project_2004.html
Simple demonstration of grid layer
MFC Application allowing you to set up simulation
Console application allowing you to determine optimal
values for number of cells per side and verlet radius
"TechDemo_OpenGL" showing pretty spiral
"TechDemo_OpenGL" showing a hilbert space-filling