[petsc-users] Parallel Graph Coloring

[Gaetan Kenway]

I'm not aware of the difference between a distance-2 coloring and a
1-coloring. What is the difference? Yes, I mean that my Jacibain stencil
has 33 entires; it is a 3x3x3 cube with 6 extra cells on the middle of each
of the 6 faces. For that stencil you can find an analytic coloring that
requires 35 evaluations. The issue I have arises from the application of
boundary conditions; The normal residual evaluation extrapolates values to
halo cells and then these halo values are communicated. I am assembling the
matrix using forward mode AD and in a fashion that doesn't require
communication; the idea is to peturb "halo" cells in addition to the "real"
cells and this eliminates the communication for the halo exchange. However,
I didn't have a way of relating the extrapolated values from a different
processor with the real cell on the other processor. It's a little
confusing and fairly specific to the CFD solver I'm using.

If I could get a global coloring that was somewhat close to what I can get
analytically, I'd use that since it is simpler and requires less
modification.

Gaetan


On Tue, Nov 5, 2013 at 4:08 PM, Peter Brune <prbrune at gmail.com> wrote:

>
>
>
> On Tue, Nov 5, 2013 at 11:07 AM, Gaetan Kenway <gaetank at gmail.com> wrote:
>
>> Hi Peter
>>
>> Thanks for the info. I actually already have a coloring that is done
>> through the discretrization that is near optimal. The issue is that I have
>> a funny interprocessor dependence that is tricky to do my own sequential
>> coloring. So I was looking at doing it in a global, parallel sense. For
>> interest, I tried using the matGetColor() on my assembled matrix just to
>> see how many colors it would take. My discretrization coloring has 35
>> colors (for a stencil with 33 cells) and the matGetColor() resulted in
>> approximately 78 colors or about twice as many.
>>
>
> Jacobian coloring requires a column, or distance-2 coloring of the matrix.
>  The distance-2 colorings we get from the serial algorithms aren't that
> bad, so I suspect that you might be doing a 1-coloring from your mesh; I
> assume that you mean that your residual/Jacobian stencil has 33 entries
> rather than some distance-2 thing?  How did the problems with your coloring
> manifest themselves?
>
> - Peter
>
>
>>
>> Thanks,
>>
>> Gaetan
>>
>>
>> On Tue, Nov 5, 2013 at 11:39 AM, Peter Brune <brune at mcs.anl.gov> wrote:
>>
>>>
>>>
>>>
>>> On Tue, Nov 5, 2013 at 10:29 AM, Gaetan Kenway <gaetank at gmail.com>wrote:
>>>
>>>> Hi
>>>>
>>>> I have a quick question regarding the MatGetColoring() function.
>>>> According to the documentation,
>>>>
>>>>  "For parallel matrices currently converts to sequential matrix and
>>>> uses the sequential coloring on that."
>>>>
>>>>
>>> The meaning of this is that it transfers the parallel matrix to a single
>>> processor and does the coloring there, not that it only considers
>>> on-processor entries.  What comes out is therefore a valid column coloring
>>> of the whole matrix.  Parallel matrix coloring is in development but is not
>>> quite ready for public consumption.  Anecdotal evidence suggests that the
>>> serial coloring does not become a bottleneck on small parallel runs.
>>>
>>> A good option is to provide the coloring through your discretization.
>>>  This will often be more efficient than the matrix colorings, as you know
>>> the structure of your problem.
>>>
>>> - Peter
>>>
>>>
>>>> I am wondering does this give actually give a valid parallel coloring?
>>>> My application is a cell centered multi-block finite volume code, (with
>>>> block-based decomposition)  and the communications are done using a two
>>>> level exchange of halo cells. I would like to use FD (actually forward mode
>>>> AD to compute the jacbian matrix). So, what I'm wondering is, if a cell
>>>> with color 0 is perturbed on processor 0, is it guaranteed that a residual
>>>> on processor 1, that is influenced by the 0-colored cell on proc zero is
>>>> *only* influenced by the color 0 from proc 0 and not a 0-colored cell on
>>>> proc 1?
>>>>
>>>> I hope that is clear
>>>>
>>>> Thank you,
>>>>
>>>> Gaetan Kenway
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20131105/c54ef3cd/attachment.html>