  We have performed a detailed analysis of the fast multipole method (FMM) in
the adaptive case, in which the depth of the FMM tree is non-uniform. Previous
works in this area have focused mostly on special types of adaptive
distributions, for example when points accumulate on a 2D manifold or
accumulate around a few points in space. Instead, we considered a more general
situation in which fractal sets, e.g., Cantor sets and generalizations, are
used to create adaptive sets of points. Such sets are characterized by their
dimension, a number between 0 and 3. We introduced a mathematical framework to
define a converging sequence of octrees, and based on that, demonstrated how to
increase $N \to \infty$.
  A new complexity analysis for the adaptive FMM is introduced. It is shown
that the ${\cal{O}}(N)$ complexity is achievable for any distribution of
particles, when a modified adaptive FMM is exploited. We analyzed how the FMM
performs for fractal point distributions, and how optimal parameters can be
picked, e.g., the criterion used to stop the subdivision of an FMM cell. A new
subdividing double-threshold method is introduced, and better performance
demonstrated. Parameters in the FMM are modeled as a function of particle
distribution dimension, and the optimal values are obtained. A three
dimensional kernel independent black box adaptive FMM is implemented and used
for all calculations.
