Repository files navigation

Fast Multiple Method (FMM) is a fast technique to calculate forces in multiple positions of a n-body system. This project is an implementation of FMM in 1D. An brief introduction to this method can be found inthis short course.

FMM.h is the header containing necessary classes for implementing FFM in 1D. TheFMM1d gives a class to intialize a n-body system with an array of weights in differnt places, as well as a parameterh and maximal erroreps.

FMM1d(double *begin,double *end,double *weightBegin,double *weightEnd,double h,double eps)

This class has equipped with a methodFMM1d::evaluate(double x) to evalute the total force at positionx.

main.cpp contains test to meet the technical requirements in [RadialBasis.pdf](Radial Basis.pdf). It shows that the FMM has a run time complexity of$O(n\log(1/\varepsilon))$ with the maximal error$\varepsilon$, compared to a$O(n^2)$ of the brute force.

18_330_Final.pdf is a detailed report on how the algorithm is implemented and comparative results.

This project is inspired byMatthias Taus from MIT Mathematics in the 18.330 class during the fall term in 2017.