<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Sep 18, 2022 at 5:11 PM Barry Smith <<a href="mailto:bsmith@petsc.dev">bsmith@petsc.dev</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><br></div> Does the MIS you use, use the numerical values in the matrix? Looking at the code it looks like not, while hem does seems to use them.</div></blockquote><div><br></div><div>Yes. numerical values are used in the filtering.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><br></div><div> But MatCreateGraph() seems to always get the numerical values, makes them positive and then scales them by the diagonal even when no filtering will be done. Can this be optimized out for no filtering and not HEM (for scalar matrices it looks like even the MatDuplicate() is not needed since it just processes a copy of the original matrix?)</div></div></blockquote><div><br></div><div>Yes, it used to do that. There was code like if (Gmat1 != GMat2) Destroy(Gmat1)</div><div>etc,</div><div>It looks like that was lost in the refactoring.</div><div>Maybe at gamg.c:634 check for bs==1 and no filtering and set Gmat = Aarr[level];</div><div>Then check for this when Gmat is destroyed later.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><br></div><div> I think the current parallel symmetrization could be optimized especially when one doe not need numerical values. Probably can be done faster than MatTranspose() followed by MatMAXPY()</div></div></blockquote><div><br></div><div>OK. It seems to me that the values just piggyback on the column indices, but maybe.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><br></div><div> The MIS also seems to slow down with multiple MPI ranks.</div></div></blockquote><div><br></div><div>I have never profiled this code carefully, It just does a nearest neighbor exchange a few times, once for each iteration of the MIS.</div><div>That code and data structure is very old.</div><div>It could well be improved.</div><div>I have noticed that for the aggressive coarsening, with the square graph-like thing, 80% of the time is in the PtAP that I use to create an intermediate level matrix.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><br></div><div> These combine to make the total time to solution much slower in parallel than sequential for GAMG, while all the rest of GAMG gets good speedup. </div></div></blockquote><div><br></div><div>You could compare with hypre to get an idea of the relative speed and scaling.</div><div>The code uses a Fortran style linked list to collect selected vertices and the vertices that it "deleted". </div><div>Then sends all the processors that see the selected and deleted vertices the new state.</div><div>This code is 25 years old.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><br></div><div> Is there a parallel coarse grid point selector that would be faster and not have the parallel bottle necks that could be coded up relatively easily?</div></div></blockquote><div><br></div><div>I got a best student paper award at Copper '98. <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.3040&rank=8">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.3040&rank=8</a></div><div>This paper discusses the parallel algotithm.</div><div>The algorithm is fine, but I could see the implementations could be bad. Its not that much code.</div><div><br></div><div>Mark</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><br></div><div> Barry</div><div><br><div><br><blockquote type="cite"><div>On Sep 18, 2022, at 4:21 PM, Mark Adams <<a href="mailto:mfadams@lbl.gov" target="_blank">mfadams@lbl.gov</a>> wrote:</div><br><div><div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Sep 18, 2022 at 4:02 PM Barry Smith <<a href="mailto:bsmith@petsc.dev" target="_blank">bsmith@petsc.dev</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
Mark,<br>
<br>
Do all MIS algorithms in PETSc require a symmetric graph structure? And parallel ones can hang if not structurally symmetric?<br></blockquote><div><br></div><div>Yes,</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
When used sequentially I guess it never hangs but it may not produce a "correct" MIS if the matrix structure is not symmetric?</blockquote><div><br></div><div>It is fine in serial and it is not necessarily an MIS of the symmetrized graph.</div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> But like the MIS is fine for GAMG in this circumstance?<br></blockquote><div><br></div><div>It will be fine for GAMG. The MIS is just a heuristic.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Barry<br>
<br>
</blockquote></div></div>
</div></blockquote></div><br></div></div></blockquote></div></div>