Sunday, July 31, 2011

World-Record Algorithm Calculates Over 3 Trillion Particles In 11 Minutes

Computer simulations can be performed much faster with a method refined by Jülich scientists. During a test with the JUGENE supercomputer, researchers calculated a system comprising 3,011,561,968,121 particles in just over eleven minutes – a world record!

The method involves an optimized implementation of one of the top ten algorithms for scientific simulations, namely the fast multipole method (FMM). Scientists Ivo Kabadshow and Holger Dachsel at the Jülich Supercomputing Centre (JSC) are now making the source code available to interested users.

Comparison of the different methods. To calculate a system comprising three trillion particles directly, a normal PC would need a billion years. With the Jülich FMM, in contrast, it only needs 220 days. Germany's fastest computer JUGENE was finished in just over eleven minutes.
Complexity Overlay
Credit: Jülich Supercomputing Centre (JSC) 

Other applications, which are much smaller, can also benefit from the optimized algorithm. The fast multipole method is generally used to calculate spatially unlimited interactions between particles. These include what are often the most important forces in practical applications: gravitation and electromagnetic interaction. The latter is the basis for the propagation of light, electricity, chemical reactions and for the structure of solids, molecules and atoms. As each particle in such systems interacts with every other particle, the total number of interactions that have to be considered increases quadratically and quickly assumes huge proportions.

If you wanted to calculate the interactions between three trillion particles directly, a supercomputer such as JUGENE with 294,912 processors would require 32,000 years for a single run. A normal PC would take as long as a billion years. Using the fast multipole method, particles that are far apart can be combined in clusters described by multipole moments. This means that interactions no longer have to be calculated individually, which in turn shortens the computing time. Using the algorithm optimized in Jülich on Germany's fastest supercomputer, JUGENE, the time was reduced to 695 seconds.

In the past, large-scale simulations, such as those in astrophysics on the evolution of the universe, were limited to several hundred billion particles. In order to push this boundary back, the Jülich scientists "tinkered with" the storage requirements. "Supercomputers like JUGENE often have little storage per processor despite their huge computing power – often less than a PC. The number of particles therefore tends to be more limited by storage than by the processor performance," says Kabadshow.

In order to optimize the method, the Jülich team developed a new algorithm allowing automatic error checking and a reduction in the computing time. This also decreased the storage requirements and accelerated the calculation. "FMM was always considered a fast method. But up to now, it was almost impossible to optimally adjust it. The required computing time depends on three different parameters, which mutually influence each other and in principle have to be continuously readjusted.

If the parameters are not adequately adjusted, the computing time can quickly increase tenfold to a hundredfold," explains Jülich researcher Holger Dachsel. It is therefore the users who will specifically profit from the simplicity of this improved method. The Jülich FMM automatically adjusts all parameters continuously, thus allowing easier access to the algorithm. The library developed in cooperation with Argonne National Laboratory (ANL) and TU Chemnitz is now freely accessible.

Contacts and sources:

Jülich Supercomputing Centre (JSC)

More information:
Information on the Jülich Supercomputing Centre (JSC):

Information on the Jülich supercomputers:

Top 10 algorithms of the 20th century:

Dates for your diary:
Visit to find out about upcoming conferences and events organized in and by Forschungszentrum Jülich, including

CECAM - Jülich Summer School 2011, during which the fast multipole method optimized at Jülich will be presented.


  1. Functional Medicine KL that brings together conventional medicine, nutritional medicine, and bio-identical hormone therapy to restore health and enhance youth. Our doctors are here to educate, inspire & empower you to make better decisions regarding your health.

  2. GVS Malaysia
    was founded with a goal to advance positively alongside the local community and in tandem with the group’s strategic expansion plan that would serve both foreign industries and locals alike.