Complexity of fast multipole method

Question

I am trying to implement the Fast multipole Method on Matlab. But i have a question: if we call N the number of source point we need (in the FMM algorithm) to sort the data points. Such a procedure require O(NlogN) complexity in the best case (the quicker sorting algorithm are O(NlogN) i believe). I don't understand how we can perform FMM in O(N) complexity ?

Answer 1

Sorting in general is not defined in dimensions more than 1.

Just to expand on the comment a bit. In Matlab it is practical to represent things using vectors and matrices. What you can do is to create a distance matrix $\bf D$, with all pairwise distances of points in $\bf v$. $${\bf D}_{ij} = \|{\bf v}_i-{\bf v}_j\|$$ Then we define an affinity matrix $\bf A$, which is a measure of pairwise "closeness": $${\bf A}_{ij} = \exp(-{\bf D}_{ij}/\sigma)$$

We see that since $\bf D$ and $\bf A$ will be symmetric, we are sure to by the spectral theorem have a basis of eigenvectors with real non-negative eigenvalues. If we take a look at the eigenvalues of $\bf A$, sorted by modulus (absolute value) and normalized, we get something like:

Here we can see large maximum at 5. Meaning the algorithm has found 5 "clusters" of values. If we project onto these clusters, we get: What we can do then, is to factor our matrix into a block-matrix $M = \left[\begin{array}{ccccc} M_1&0&0&0&0\\ 0&M_2&0&0&0\\ 0&0&M_3&0&0\\ 0&0&0&\ddots&0\\ 0&0&0&0&M_b \end{array}\right]$ Where each matrix-block is related to it's own cluster. So far we have found a way to create reasonable clusters. What remains to do is to derive and express the update equations in terms of matrices and vectors.