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

[Mark Adams]

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

>
>   Right, but I want to run with the old options MIS (instead of MIS-2) and
> get the same times as before. But instead I am getting much larger times.
>

Yea, the new MIS is noticeably slower

New:
petsc/src/ksp/ksp/tutorials$ mpiexec -n 4 ./ex55 -ne 511 -ksp_type cg
-pc_type gamg -log_view -pc_gamg_square_graph 0 -mat_coarsen_type misk
PCSetUp_GAMG+          1 1.0 6.8526e-01 1.0 2.14e+08 1.0 1.2e+03 6.3e+03
7.3e+02 44 21 28 38 88 100100100100100  1242
 GAMG Coarsen          5 1.0 5.7050e-02 1.0 0.00e+00 0.0 3.0e+02 7.1e+02
1.5e+02  4  0  7  1 18   8  0 26  3 20     0
  GAMG MIS/Agg         5 1.0 5.0056e-02 1.0 0.00e+00 0.0 3.0e+02 7.1e+02
1.5e+02  3  0  7  1 18   7  0 26  3 20     0

Old:
petsc/src/ksp/ksp/tutorials$ mpiexec -n 4 ./ex55 -ne 511 -ksp_type cg
-pc_type gamg -log_view -pc_gamg_square_graph 0 *-mat_coarsen_type mis*
...
PCSetUp_GAMG+          1 1.0 6.7866e-01 1.0 2.14e+08 1.0 1.1e+03 7.1e+03
5.9e+02 43 21 26 39 85 100100100100100  1254
 GAMG Coarsen          5 1.0 1.3564e-02 1.0 0.00e+00 0.0 1.6e+02 9.6e+02
1.5e+01  1  0  4  1  2   2  0 15  2  3     0
  GAMG MIS/Agg         5 1.0 7.5110e-03 1.0 0.00e+00 0.0 1.6e+02 9.6e+02
1.5e+01  0  0  4  1  2   1  0 15  2  3     0

Same in serial:

(conda_env) 05:15 adams/landau-ex13-fixes=
~/Codes/petsc/src/ksp/ksp/tutorials$ mpiexec -n 1 ./ex55 -ne 511 -ksp_type
cg -pc_type gamg -log_view -pc_gamg_square_graph 0 *-mat_coarsen_type mis*
| g MIS
  GAMG MIS/Agg         5 1.0 *3.7858e-02* 1.0 0.00e+00 0.0 0.0e+00 0.0e+00
0.0e+00  1  0  0  0  0   2  0  0  0  0     0
(conda_env) 05:16 adams/landau-ex13-fixes=
~/Codes/petsc/src/ksp/ksp/tutorials$ mpiexec -n 1 ./ex55 -ne 511 -ksp_type
cg -pc_type gamg -log_view -pc_gamg_square_graph 0 -mat_coarsen_type misk |
g MIS
  GAMG MIS/Agg         5 1.0 *8.5015e-02* 1.0 0.00e+00 0.0 0.0e+00 0.0e+00
0.0e+00  3  0  0  0  0   5  0  0  0  0     0

I did find that there is an unneeded MatDuplicate in MISk with just one MIS
(MIS-1), but it is still slower than the old:

(conda_env) 05:31 adams/landau-ex13-fixes *=
~/Codes/petsc/src/ksp/ksp/tutorials$ mpiexec -n 1 ./ex55 -ne 511 -ksp_type
cg -pc_type gamg -log_view -pc_gamg_square_graph 0 -mat_coarsen_type misk |
g MIS
  GAMG MIS/Agg         5 1.0 *5.9566e-02* 1.0 0.00e+00 0.0 0.0e+00 0.0e+00
0.0e+00  2  0  0  0  0   4  0  0  0  0     0

MISk is organized differently and goes through some hoops that the old MIS
does not do that are not as easy as the MatDuplicate to avoid.

Mark


>
> On Sep 18, 2022, at 6:58 PM, Mark Adams <mfadams at lbl.gov> wrote:
>
>
>
> 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/20220919/8bc4b0b4/attachment.html>