Return to home page Professional (resume, work samples, etc.) Personal (interests, photos, etc.) Student Resources (advice, assignments, etc.) Current contact info (in new window)

 

> Introduction
> Advice
> Helpful Files

> Lessons
> NoskeWiki

> postgrad - UQ:
> PhD Project

> undergrad - JCU:
> Tutored Subjects
> JCU Work
> Honours Project

> high shool - SSHS:
> High School Work

> Links

A new support project I've started - think of it as a giant notepad.

 

Efficient Algorithms for Molecular Dynamics Simulations and Other Dynamic Spatial Join Queries

Honours Thesis by Andrew Noske

Last updated: 17-Jun-2010


Introduction:

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.


Downloads:

Final product:

  • >> 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 (.doc) 74kB - 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 (.doc) 100kB - Final seminar we had to deliver shortly after submitting our thesis and summarize all our discoveries/achievements.

More resources:

  • Guide 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.

Project Details:

  • 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
  • Supervisors:

Abstract:

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


Screenshots:

[see all images]


Simple demonstration of grid layer


MFC Application allowing you to set up simulation parameters.


Console application allowing you to determine optimal values for number of cells per side and verlet radius


"TechDemo_OpenGL" showing pretty spiral pattern


"TechDemo_OpenGL" showing a hilbert space-filling curve.

 

 

 
| Home | Professional | Personal | Student Resources | Contact | {back to top} |
copywrite Andrew Noske