Fast Multipole Method
FMM is one of ten most important algorithm in 20 century, it reduce the calculate cost from 2N to N and is extremely efficient for large N.
The important Reading Materials for FMM:
- V. Rokhlin, Rapid Solution of Integral Equations of Classical Potential Theory, Journal of Computational Physics, 60, 187-207, 1983.
- Leslie Greengard, The Rapid Evaluation of Potential Fields in Particle System.
- J. Carrier, L. Greengard, and V. Rokhlin. A Fast Adaptive Multipole Algorithm for Particle Simulations, SIAM J. STAT. COMPUT. Vol. 9, No. 4, 1988.
- A. Dutt, M. Gu and V. Rokhlin, Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation, SIAM J. Numer. Anal, Vol. 33, No. 5, pp. 1689-1711, 1996.
- T. Hrycak and V. Rokhlin, An Improved Fast Multipole Algorithm for Potential Fields, SIAM J. Sci. Comput, Vol. 19, No. 6, pp. 1804-1826, 1998.
I write a note for Fast Multipole Method to explain most important details about FMM method. If you are confused by FMM method, this note may help you to catch the most important conceptions.
For our paper:
Order O(1) algorithm for first-principles transient current through open quantum systems
You also can refer this note for details:
Fast Calculate for Evolution Operators