Graph layout w/ fast multipole method (FMM)
Timmy Wilson
I'm interested in getting a fast/parallel layout algo into python.
Taking Aric Hagberg's suggestion below, i spent some time researching
the fast multipole method (FMM)
This is from Aric:
> It might not be hard to modify/update the existing
> Fruchterman-Reingold layout code to include these other variants of
> force-based layouts.
> But what would really go great with that would be to implement a
> multiscale method (fast multi-pole, etc) to make it more efficient (n
> log(n) instead of n^2).
I found 2 c libraries aimed @ parallel FMM:
The following is from Matthew Knepley @ University of Chicago
> PetFMM: I wrote this with Felipe Cruz, and Rio Yokota.
> https://bitbucket.org/petfmm/petfmm-dev It is clearly alpha software,
> but has been used by a few people. It has a manual, examples, and
> installs itself.
> ExaFMM: https://bitbucket.org/exafmm/exafmm/overview This is Rio
> Yokota's new code. It is even more raw, but scales much better on
> multiple machines and GPUs.
The following is from Aron Ahmadia @ KAUST -- http://aron.ahmadia.net/
-- Aron's writing a layout algo using exaFMM:
> Yes, we ended up switching over to exaFMM because exaFMM's developer
> (Rio Yokota) was interested in doing some of the work in designing the
> layout kernels, but PetFMM would be equally suitable for FMM-based
> graph layout. We are submitting a conference paper next week.
PetFMM + ExaFMM are both parallel, and i believe both can run on CPUs
or GPUs -- the following is from Matt's site:
> The largest application run, with over 20 million atoms and one billion
> unknowns, required only one minute on 512 GPUs.
I'm going to devote some time working w/ Aron + Matt to wrap their
layout code w/ python
Thought i'd check to see if the community's interested in adding this
dependency?
Timmy Wilson
Aric Hagberg
> Hi networkx community,
>
> I'm interested in getting a fast/parallel layout algo into python.
>
>> The largest application run, with over 20 million atoms and one billion
>> unknowns, required only one minute on 512 GPUs.
>
> I'm going to devote some time working w/ Aron + Matt to wrap their
> layout code w/ python
>
> Thought i'd check to see if the community's interested in adding this
> dependency?
That sounds like a fun project. I doubt we'd want to completely
incorporate that code into the NetworkX package, but we can certainly
work on making the Python interfaces work together. Let us know how
it goes and check back when you have the Python wrappers read to try.
Aric