[petsc-dev] good partitioning packages?

[Fande Kong]

On Fri, Jun 1, 2018 at 9:49 PM, Jed Brown <jed at jedbrown.org> wrote:

> Fande Kong <fdkong.jd at gmail.com> writes:
>
> > On Fri, Jun 1, 2018 at 5:40 PM, Matthew Knepley <knepley at gmail.com>
> wrote:
> >
> >> On Fri, Jun 1, 2018 at 7:09 PM, Smith, Barry F. <bsmith at mcs.anl.gov>
> >> wrote:
> >>
> >>>
> >>>    Fande,
> >>>
> >>>        This is a great question. I am forwarding it to Mike Heroux who
> >>> has a high level position in the ECP; because I have similar concerns
> and
> >>> also don't have a good answer. ParMetis does indeed have a poor
> license and
> >>> essentially no support. Perhaps Mike has some ideas.
> >>>
> >>
> >> Also, the parallel scalability is crappy (sorry George).
> >>
> >
> > Do we know the underneath reason why the parallels scalability is poor?
> > Poor algorithm? Poor implementation?
>
> My recollection is that the k-way refiner has an O(k^2) data structure.


 Theoretically speaking, does the data structure have to be O(k^2)? Any
existing algorithm to avoid that?


> > Here is a list of partitioning packages
> > https://en.wikipedia.org/wiki/Graph_partition#cite_note-patoh-16
> >
> > Anybody has experiences on any of the listed packages?
>
> Many of them are unmaintained.  KaHIP is the most interesting in my
> opinion.


Why KaHIP is the most interesting? The algorithm is novel or better than
ParMetis or PTScotch?



> It is GPLv2 which is an issue for some users, though I recall
> the lead developer might consider a more permissive license.  I chatted
> with John Peterson about this a few months ago, but I don't know if he
> installed and tested it.  I suspect there would be interest if you could
> contribute toward --download-kahip and a MatPartitioning implementation.
>

I definitely will take a try.


Fande,


>
> > Fande,
> >
> >
> >> Bill Gropp has proposed in the past developing a new
> >> partitioner along more scalable lines, such as the Teng algorithm used
> in
> >> Padma's 2013 SC paper
> >> (https://dl.acm.org/citation.cfm?id=2503280). Jed favors a multilevel
> >> approach which I do not understand.
> >> Its a shame that all the development time that went into PT-Scotch could
> >> not produce a scalable, open
> >> partitioner. Also, the label-push stuff seems only to work well for
> highly
> >> connected graphs, not meshes.
> >>
> >>    Matt
> >>
> >>
> >>>
> >>>    Barry
> >>>
> >>>
> >>>
> >>>
> >>> On Jun 1, 2018, at 5:46 PM, Kong, Fande <fande.kong at inl.gov> wrote:
> >>>
> >>> Hi Developers,
> >>>
> >>> I have introduced MatPartitioning interface to MOOSE. It is working
> >>> great, and we can use all external partitioning packages via a simple
> >>> interface.
> >>>
> >>> But here is a concern. Almost all the packages are not under
> development
> >>> any more. Does this make a bug fix more difficult in the future.  Also
> some
> >>> of them have bad licenses.
> >>>
> >>> I was wondering there is any other partitioning package in the
> community?
> >>>
> >>> Thanks,
> >>>
> >>> Fande,
> >>>
> >>>
> >>>
> >>
> >>
> >> --
> >> What most experimenters take for granted before they begin their
> >> experiments is infinitely more interesting than any results to which
> their
> >> experiments lead.
> >> -- Norbert Wiener
> >>
> >> https://www.cse.buffalo.edu/~knepley/ <http://www.caam.rice.edu/~mk51/>
> >>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20180601/f808b71a/attachment.html>