[petsc-dev] good partitioning packages?

[Jed Brown]

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.

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

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