[petsc-dev] good partitioning packages?

[Jed Brown]

Fande Kong <fdkong.jd at gmail.com> writes:

> 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?

Theoretically no, but it isn't clear what data structure would be fast.

>
>> > 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?

The published results are promising.  We know ParMETIS scales poorly and
PTScotch is relatively slow.

>
>> 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/>
>> >>
>>