Multipole methods

Fast multipole methods were introduced in Greengard and Rokhlin's seminal paper in the Journal of Computational Physics in 1987, in which they reduced an O(N-squared) evaluation of the potential and force fields in N-body systems with Coulombic or gravitational potentials to an O(N) computation. They have since become a popular tool in many fields of computational science and modelling, having applications to N-body problems with various potential functions as well as electromagnetic scattering and incompressible fluid dynamics.

For queries about this topic, contact Neil O'Brien.

View the calendar of events relating to this topic.

Projects

A Fast Multipole Method for the Bessel potential

Marc Molinari, Simon Cox (Investigators), Neil O'Brien

The fast multipole method (FMM) proposed by Greengard and Rokhlin provides a method by which the O(N-squared) many-body problem can be reduced to O(N) complexity. In this project, a multipole method is developed to calculate the energy of a system of vortices in a high temperature superconductor, where the many-body interactions give rise to rich and complex physics. The method developed here is suitable for systems where the interactions are governed by a Bessel potential rather than the usual logarithmic potentials occurring in gravitational and electrostatic problems. We derive and apply vectorised forms of the Gegenbauer addition formulae in order to achieve the O(N) scaling associated with fast multipole methods.