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

[Mark F. Adams]

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.

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.

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.)
> 
>