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

Wed Oct 26 11:27:20 CDT 2011

On Wed, Oct 26, 2011 at 4:21 PM, Mark F. Adams <mark.adams at columbia.edu>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.
>
> 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.

Barry, I think I understand what Mark means:

  A generic coloring of the matrix graph would disentangle the dofs of one
color from all others. This is exactly
  what we want in serial.

  In parallel, we only need to separate dofs on one process from those on
another, so we only need a number of
  colors equal to the number of ranks.

To me, this seems like a two-level coloring, where we have a real graph
coloring on the bottom level, and a
(really simple) coloring of the process graph on the top level.

    Matt

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

-- 
What most experimenters take for granted before they begin their experiments
is infinitely more interesting than any results to which their experiments
lead.
-- Norbert Wiener
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20111026/52bf7418/attachment.html>