[petsc-dev] do all MIS algorithms require a symmetric structure?

[Mark Adams]

On Sun, Sep 18, 2022 at 6:19 PM Barry Smith <bsmith at petsc.dev> wrote:

>
>   Mark,
>
>     Some how your changes to GAMG in June slowed down the time to compute
> the MIS dramatically. I cannot figure out what options to use to
> get the exact same performance as an older branch. -mat_coarsen_type mis
> -pc_gamg_threshold 0 result in longer times than the older code with its
> default options.
>

The new MIS-2 folds in the square graph with the MIS. Before the square
graph was in a separate method that created an squared graph explicitly.
So don't use aggressive coarsening (you will see a PtAP if you use
aggressive coarsening in the new code)
And -pc_gamg_threshold 0 will filter (zeros only). Use < 0 for no filtering.
The old code also had this optimization to not create a graph for bs==1 and
no filter,

Mark


>
>
>
> On Sep 18, 2022, at 4:21 PM, Mark Adams <mfadams at lbl.gov> wrote:
>
>
>
> On Sun, Sep 18, 2022 at 4:02 PM Barry Smith <bsmith at petsc.dev> wrote:
>
>>
>>   Mark,
>>
>>    Do all MIS algorithms  in PETSc require a symmetric graph structure?
>> And parallel ones can hang if not structurally symmetric?
>>
>
> Yes,
>
>
>>
>>    When used sequentially I guess it never hangs but it may not produce a
>> "correct" MIS if the matrix structure is not symmetric?
>
>
> It is fine in serial and it is not necessarily an MIS of the
> symmetrized graph.
> If there is a one way edge between two vertices and the order of the
> greedy MIS process picks the root of the edge it is an MIS of the
> symmetrized graph, otherwise both vertices could get selected.
>
>
>> But like the MIS is fine for GAMG in this circumstance?
>>
>
> It will be fine for GAMG. The MIS is just a heuristic.
>
>
>>
>>   Barry
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20220918/80bae659/attachment.html>