<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Oct 26, 2011, at 12:27 PM, Matthew Knepley wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">On Wed, Oct 26, 2011 at 4:21 PM, Mark F. Adams <span dir="ltr"><<a href="mailto:mark.adams@columbia.edu">mark.adams@columbia.edu</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im"><br>
On Oct 26, 2011, at 11:29 AM, Barry Smith wrote:<br>
<br>
><br>
> On Oct 26, 2011, at 10:19 AM, Mark F. Adams wrote:<br>
><br>
>> Two things:<br>
>><br>
>> 1) Computing C(A^{T} A) is very similar to what I need in GAMG and is currently one of the big setup costs in GAMG. You need to do something different in the inner loop and it probably demands that it be considered from the beginning so keep me in the loop if someone starts implementing this.<br>
><br>
> The Jacobian coloring algorithms work directly with A and do not need to compute A^{T}A<br>
><br>
<br>
</div>That's why I want to piggyback on this, I compute A*A for convenience -- it is not a bottleneck if you can amortize the setup cost enough, but it would be nice, all things being equal, if it were faster. The parallel engine that you will probably use is a maximal independent set, in which case it can be modified slightly to produce aggregates for me.<br>
<div class="im"><br>
>><br>
>> 2) It is really stupid to do graph coloring for multiplicative smoothers. I have not though about triangular solves but I suspect at least some of the same issues apply. Unlike the "coloring" needed for Jacobians, coloring is not needed in serial for G-S -- this make a big difference. You just need a mechanism to adjudicate conflicts between processors -- processor IDs (colors if you will) are fine for this. You could get fancier if you insist.<br>
><br>
> This statement always confusing me. You are so keen on the red-black coloring for smoothers (stating it is better in multigrid than regular G.S. smoother)<br>
<br>
</div>G-S is better *mathematically* (barely for SPD problems), and red-black is not too bad because it has just two colors, but G-S has many *computational* problems (I insist on separating math from computer science, convolving the two leads to all sorts of confusion and bad algorithms for iterative solvers at least). There are several cache problems with G-S, eg, red-black has pretty much the same "memory movement complexity", if you will, as two lexicographical G-S iterations. The biggest problem of G-S, as Jed pointed out, is that you cannot reuse MatVec but need special code -- this is a big disadvantage.<br>
<br>
As Jed also pointed out Cheb is not as nice, read terrible, for highly asymmetric problems and that's where G-S might have a shot at being useful.<br>
<br>
I also like that G-S has no global parameters like the damping parameter (which is a function of the highest eigenvalue) so if you have, say, a hard and soft material, G-S does not need to over-damp in the soft region.<br>
<div class="im"><br>
> but now you say doing coloring for real problems makes no sense? It sounds like you don't really use a "real graph color" as defined below by C(A), just some munge?<br>
><br>
<br>
</div>Generic graph coloring make no sense for distribute memory domain decomposed discretized PDEs because there is structure here that can be exploited to great advantage.<br>
<br>
Computing Dictionary<br>
munge definition<br>
/muhnj/ 1. A derogatory term meaning to imperfectly transform information.<br>
<br>
No, it is a perfect transformation of the G-S algorithm in distributed memory environment, that has pretty good (I think optimal) communication reducing / parallel complexity properties. And other communication reducing strategies could be easily added to the core algorithm.<br>
<br>
It is probably better if you don't think about coloring at all, apparently, just look at the algorithm and call it what you like. There are lots of cartoons in the paper; its an easy read. I relate it to coloring algorithms because that's what everyone know about and it does reduce to the standard coloring algorithm with one vertex per processor. The algorithm also gracefully degrades in serial to whatever (cache optimized) ordering you do locally.</blockquote>
<div><br></div><div>Barry, I think I understand what Mark means:</div><div><br></div><div> A generic coloring of the matrix graph would disentangle the dofs of one color from all others. This is exactly</div><div> what we want in serial.</div>
<div><br></div></div></blockquote><div><br></div><div>You mean *not* what we want in serial. In serial we can forget about coloring and just process vertices in whatever order we like for cache performance, for instance.</div><br><blockquote type="cite"><div class="gmail_quote"><div> In parallel, we only need to separate dofs on one process from those on another, so we only need a number of</div><div> colors equal to the number of ranks.</div><div><br></div><div>To me, this seems like a two-level coloring, where we have a real graph coloring on the bottom level, and a</div>
<div>(really simple) coloring of the process graph on the top level.</div><div><br></div></div></blockquote><div><br></div><div>Yes, that is a good way to look at it -- coloring between processors and whatever fast local/serial method you want for the sets of vertices that come out of the algorithm. These sets are actually topological like things: "interior" (3D) vertex sets, "surface" (2D) vertex sets, and the rest (1 and 0 D). The processor "coloring" is trivial, and it may not be obvious, and there is no need to think about it.</div><div><br></div><div>Mark</div><div><br></div><br><blockquote type="cite"><div class="gmail_quote"><div> Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<font color="#888888"><br>
Mark<br>
</font><div><div></div><div class="h5"><br>
> Barry<br>
><br>
><br>
><br>
>><br>
>> If you apply a generic coloring algorithm to G-S you will get lots of colors for 3D problems and the code will be slow as a dog. This is compounded by the terrible cache properties of multi-colored G-S. These problems can be greatly reduced (but not eliminated, that's why I like Cheb) by exploiting the nature of graphs from discretized PDEs and the good data locality that we demand for the rest of the code anyway. There is a surface to volume ratio aspect and simple neighbor communication that can be exploited in our problems that can make G-S tractable and even attractive, perhaps, for some problems.<br>
>><br>
>> Mark<br>
>><br>
>> On Oct 25, 2011, at 11:02 PM, Barry Smith wrote:<br>
>><br>
>>><br>
>>> A graph coloring C(A) is a division of vertices so that two vertices of the same color do not share any common edges.<br>
>>><br>
>>> A suitable coloring for a smoother is simply C(A).<br>
>>><br>
>>> A suitable "coloring" for efficient Jacobian computation is a division of the columns so that two columns of the same color do not share any common rows. This corresponds to C(A^{T} A). This is what MatGetColoring() computes.<br>
>>><br>
>>> People who write/talk about colorings for Jacobian computations are sloppy bastards and generally are not careful to distinguish between the two cases and thus confuse everyone.<br>
>>><br>
>>> Barry<br>
>>><br>
>>> To make life more complicated there are tricks to do Jacobian evaluations with fewer function operations and then do some arithmetic to recover the Jacobian entries; I never bothered to understand these.<br>
>>><br>
>>><br>
>>> On Oct 25, 2011, at 8:54 PM, Jed Brown wrote:<br>
>>><br>
>>>> On Tue, Oct 25, 2011 at 20:50, Barry Smith <<a href="mailto:bsmith@mcs.anl.gov">bsmith@mcs.anl.gov</a>> wrote:<br>
>>>> The coloring the INL guy need is for efficient computation of Jacobians; it is a different coloring than needed for smoothers. Of course we should have both in PETSc, but have neither in parallel.<br>
>>>><br>
>>>> Isn't this just the distinction between coloring a symmetric matrix and coloring a triangular matrix? (Maybe there are more consequences to the algorithm.)<br>
>>><br>
>>><br>
>><br>
><br>
><br>
<br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>
-- Norbert Wiener<br>
</blockquote></div><br></body></html>