Title:
N-Body Simulations and the Barnes-Hut Algorithm
Date:
Friday, March 1, 2013 at 1:30pm
Location:
E2-320 EITC Building, University of Manitoba Fort Garry Campus
Speaker:
Dr. Ian Jeffrey
University of Manitoba
Abstract:
The N-body problem arises when trying to predict the behaviour of a system of N particle-like bodies that interact with each other due to physical forces. These problems arise in astrophysical simulations and such engineering problems as simulating the performance of integrated circuit interconnects. Direct evaluation of the forces acting on each body scales quadratically with the number of particles in the system and becomes computationally intractable for many bodies.
In this lecture we will learn the Barnes-Hut algorithm, an elegant method that solves the static N-body problem in linearithmic time. The core concept of centre of mass makes it possible to solve systems involving millions of bodies on a single machine. The details of how this algorithm can be performed in parallel on distributed memory systems will also be given. To date, the largest N-body problem ever simulated involves in excess of one trillion particles that were dynamically evolved on more than eighty thousand computing nodes.
While you may never find yourself needing the Barnes-Hut algorithm, learning new ways of solving problems broadens our understanding and our perspective. With this in mind, this lecture has been constructed to be self-contained. A background in computer programming and tree data structures will be beneficial, but not necessary, while learning this clever approach for solving an interesting problem.
Cost:
This will be a free event.
Contact:
For questions or more information: Lorraine Coates at 474-9099
