The fast multipole method (FMM) is an efficient algorithm for calculating
electrostatic interactions in molecular simulations and a promising alternative to
Ewald summation methods. Translation of multipole expansion in spherical harmonics
is the most important operation of the fast multipole method and the fast Fourier
transform (FFT) acceleration of this operation is among the fastest methods of
improving its performance. The technique relies on highly optimized implementation
of fast Fourier transform routines for the desired expansion sizes, which need to
incorporate the knowledge of symmetries and zero elements in the input arrays. Here
a method is presented for automatic generation of such, highly optimized,
routines.
Carrier, J.
,
Greengard, L.
, and
Rokhlin, V.
(1988).
A fast adaptive multipole algorithm for particle simulations
, J. Sci. Stat. Comput. 9(4):
669-686.
2.
Cooley, J.W.
and
Tukey, J.W.
(1965).
An algorithm for the machine calculation of complex Fourier series
, Math. Comput.19: 47-64.
3.
Duhamel, P.
and
Hollmann, H.
(1984).
Split radix FFT algorithm
, Electronics Letters20: 14-16.
4.
Duhamel, P.
and
Vetterli, M.
(1990).
Fast Fourier transforms: A tutorial review and a state of the art
, Signal Process. 19(4):
259-299.
5.
Elliott, W.D.
(1995). Multipole algorithms for molecular dynamics
simulation on high performance computers. Ph. D. thesis, Duke University,
Department of Electrical Engineering,
Durham, NC.
6.
Elliott, W. D. and Board, J. A. Jr.
(1996).
Fast Fourier transform accelerated fast multipole algorithm
, SIAM J. Sci. Comput. 17(2):
398-415.
7.
Frigo, M.
(1999).
A fast Fourier transform compiler
. In Proceedings of 1999 ACM SIGPLAN Conference on Programming
Language Design and Implementation, ACM, Vol. 34, pp.
169-180.
8.
Frigo, M.
and
Johnson, S.G.
(2005).
The design and implementation of FFTW3
, Proceedings of the IEEE93(2): 216- 231.
Special issue on "
Program Generation, Optimization, and Platform Adaptation
."
9.
Good, I.J.
(1958).
The interaction algorithm and practical Fourier analysis
, J. Roy. Statist. Soc. B20(2):
361-375.
10.
Greengard, L.
(1987). The rapid evaluation of potential fields in particle
systems. Ph. D. thesis, Yale University, Department of
Computer Science, New Haven,
CT.
11.
Greengard, L.
and
Rokhlin, V.
(1987).
A fast algorithm for particle simulations
, J. Comput. Phys. 73(2):
325-348.
12.
Greengard, L.
and
Rokhlin, V.
(1988). On the efficient implementation of the fast multipole
algorithm. Technical Report RR-602, Yale University,
Department of Computer Science, New Haven,
CT.
13.
Greengard, L.
and
Rokhlin, V.
(1997).
A new version of the fast multipole method for the Laplace equation in
three dimensions
, Acta Numer. 6:
229-269.
14.
Heideman, M.T.
(1988). Multiplicative complexity, convolution, and the
DFT, Springer-Verlag, New York,
NY.
15.
Hrycak, T.
and
Rokhlin, V.
(1998).
An improved fast multipole algorithm for potential fields
, SIAM J. Sci. Comput. 19(6):
1804-1826.
16.
Kurzak, J.
and
Pettitt, B.M.
(2005a).
Communications overlapping in fast multipole particle dynamics
methods
, J. Comput. Phys. 203(2):
731-743.
17.
Kurzak, J.
and
Pettitt, B.M.
(2005b).
Massively parallel implementation of a fast multipole method for
distributed memory machines
, J. Parallel Distrib. Comput. 65(7):
870-881.
18.
Kurzak, J.
and
Pettitt, B.M.
(2006).
Fast multipole methods for particle dynamics
, Mol. Simul. 32(10/11):
775-790.
19.
Mirkovic, D.
and
Johnsson, S.L.
(2004).
Automatic performance tuning for fast Fourier transforms
, Int. J. High Perf. Comput. Applic.
18(1):
47-64.
20.
Mirkovic, D.
,
Mahasoom, R.
, and
Johnsson, S.L.
(2000).
An adaptive software library for fast Fourier transforms
. In Proceedings of the 2000 ACM/IEEE Conference on
Supercomputing, Dallas, TX, pp.
215-224.
21.
Rader, C.M.
(1968).
Discrete Fourier transforms when the number of data samples is prime,
Proc
. IEEE56(6):
1107-1108.
22.
Thomas, L.H.
(1963). Using a computer to solve problems in physics .
In Applications of Digital Computers, Ginn and
Co., Boston, MA.
23.
Tolimieri, R.
,
An, M.
, and
Lu, C.
(1989). Algorithms for discrete Fourier transform and
convolution, Springer-Verlag, New
York, NY.
24.
Tolimieri, R.
,
An, M.
, and
Lu, C.
(1997). Mathematics of multidimensional Fourier transform
algorithms, Springer-Verlag, New
York, NY.
25.
Van Loan, C.
(1992). Computational frameworks for the fast Fourier
transform, Society for Industrial and Applied
Mathematics , Philadelphia,
PA.
26.
Wang, H.Y.
and
LeSar, R.
(1996).
An efficient fast-multipole algorithm based on an expansion in the solid
harmonics
, J. Chem. Phys. 104(11):
4173-4179.
27.
White, C.A.
and
Head-Gordon, M.
(1996).
Rotating around the quartic angular momentum barrier in fast multipole
method calculations
, J. Chem. Phys. 105(12):
5061-5067.
