Fast multipole


    For certain kinds of simulations, e.g. clusters in vacuum, gas in a periodic box, it would be useful to have an implementation of a parallel fast multipole algorithm for calculation of Coulomb and Lennard-Jones forces. It has also been suggested that fast multipole algorithm is more efficient for Coulomb interactions in periodic systems than PME for very large systems.

    -- This will certainly be true, with FMA scaling as O(N) and smooth PME as O(N log N)Mabraham 04:28, 2 July 2007 (CEST)

    But note that the prefactor is large. Petersen (J. Chem. Phys. 103, pp. 3668-3679, 1995) estimates that FMA is only competetive above 100,000 atoms. And that was without the fast GROMACS innerloops. Nevertheless, I might someday want to do a Virus particle in the gas-phase and then scaling will be important.--Spoel 11:12, 2 July 2007 (CEST)

    In addition it would be fun to be able to use GROMACS for computation of gravity forces: simulate galaxies. With just a minus sign to remove in the Coulomb interaction it would be pretty fast.

    -- That would be cool, but there are other factors to consider - The original octal tree formulations of FMA were not completely satisfactory for MD because our densities have both positive and negative signs. (FMA was fine for astronomical simulations where everything has positive mass.) Charges crossing cell boundaries were noisy in the same way that they are with RF without group-based cut-offs. See below. Mabraham 04:28, 2 July 2007 (CEST)


    Points to consider

    • Accuracy: is single precision sufficient? -- possibly if you use charge groups Mabraham 04:28, 2 July 2007 (CEST)
    • Parallellization issues: can it be fit like a drop-in replacement for e.g. PME? -- Yes, as far as I can see Mabraham 04:28, 2 July 2007 (CEST)
    • License of the code if taken from somewhere else.
    • Using periodic vs non-periodic long-range potentials in periodic systems (e.g. RF is a non-periodic potential in a periodic system)


    Existing implementations

    • There's an attractive implementation of FMA in 2003 from Tavan's group (J Chem Phys 118(24):10847-10860) that uses charge groups as its smallest tree element, and a non-periodic electrostatic potential through the use of RF. This is implemented in EGO MMIV, which according to my correspondence with Tavan ages ago ought to have been available about a year ago... but there's no sign of it on the webpage. Mabraham
      • Also cool is the kernel-independent parallel adaptive fast multipole algorithm in 2004 from Zorin's group at NYU (J Comp Phys 196:591-626) inasmuch as it generalizes the FMA concept to other elliptic PDE potentials, and there is GPL code available. MD people don't care about this kernel-independence (i.e. potential-independence) feature, though. They use adaptive octal trees, though, which should suffer from noise as above (their test cases don't say whether they use distributions of varying charge, so I presume they don't). I think perhaps their approach could be adapted to use charge groups (or groups of them) as the base unit of the tree, but the assumption that the base units fill space in a non-overlapping way might be built into the algorithm in a way that I haven't yet perceived. On the other hand, it should work as a drop-in replacement for long-range LJ, for what that's worth... I will have some time to consider these issues tomorrow. Mabraham 04:28, 2 July 2007 (CEST)
    Page last modified 00:20, 13 Oct 2009 by JLemkul?