[petsc-dev] Should -pc_type mg be a linear preconditioner by default?

[Barry Smith]

On Oct 26, 2011, at 11:21 AM, Mark F. Adams wrote:

> 
> On Oct 26, 2011, at 11:29 AM, Barry Smith wrote:
> 
>> 
>> On Oct 26, 2011, at 10:19 AM, Mark F. Adams wrote:
>> 
>>> Two things:
>>> 
>>> 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.
>> 
>>  The Jacobian coloring algorithms work directly with A and do not need to compute A^{T}A 
>> 
> 
> 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.
> 
>>> 
>>> 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.
>> 
>>   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)
> 
> 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.
> 
> 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.
> 
> 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.
> 
>> 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?
>> 
> 
> 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.

   We had this discussion maybe the first time you were here where you explained to me that Chombo multigrid using red-black for their smoother and how it was a very good thing. What am I missing?

    Barry

> 
> Computing Dictionary
> munge definition
> /muhnj/ 1. A derogatory term meaning to imperfectly transform information. 
> 
> 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.
> 
> 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.
> 
> Mark
> 
>>  Barry
>> 
>> 
>> 
>>> 
>>> 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.
>>> 
>>> Mark
>>> 
>>> On Oct 25, 2011, at 11:02 PM, Barry Smith wrote:
>>> 
>>>> 
>>>> A graph coloring C(A)  is a division of vertices  so that two vertices of the same color do not share any common edges.
>>>> 
>>>> A suitable coloring for a  smoother  is simply C(A).
>>>> 
>>>> 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.
>>>> 
>>>> 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.
>>>> 
>>>> Barry
>>>> 
>>>> 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.
>>>> 
>>>> 
>>>> On Oct 25, 2011, at 8:54 PM, Jed Brown wrote:
>>>> 
>>>>> On Tue, Oct 25, 2011 at 20:50, Barry Smith <bsmith at mcs.anl.gov> wrote:
>>>>> 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.
>>>>> 
>>>>> Isn't this just the distinction between coloring a symmetric matrix and coloring a triangular matrix? (Maybe there are more consequences to the algorithm.)
>>>> 
>>>> 
>>> 
>> 
>> 
>