1

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 ?

curious
  • 295
  • Don't we need to sort only once in the beginning? – mathreadler Sep 01 '15 at 11:56
  • If you want to do this in Matlab I would suggest using something along the lines of this http://www.cscamm.umd.edu/programs/fam04/duraiswami_gumerov_fam04_t.pdf – mathreadler Sep 01 '15 at 12:14
  • Or you could just calculate an affinity matrix, do a spectral clustering and then factor into a block matrix. Then switch into considering forces within blocks separately from forces between blocks. – mathreadler Sep 01 '15 at 12:30
  • I.e. you actually don't need to "sort" all the points, you just need to find a way to split them into different "blocks" or "clusters". – mathreadler Sep 01 '15 at 12:38

1 Answers1

0

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:

enter image description here 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: enter image description here 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.

mathreadler
  • 25,824