[petsc-dev] Multigrid is confusing

[Jed Brown]

On Fri, May 25, 2012 at 4:59 PM, Mark F. Adams <mark.adams at columbia.edu>wrote:

>
> On May 25, 2012, at 4:20 PM, Jed Brown wrote:
>
> On Fri, May 25, 2012 at 3:16 PM, Mark F. Adams <mark.adams at columbia.edu>wrote:
>
>> Yes your are right, simply scaling the PC will result in scaling the
>> eigenvalues and hence the Cheby factors.
>>
>
> But that isn't the significant result, it's that even if a preconditioner
> selectively and perfectly damps the highest eigenvalues (without rescaling
> other modes), this Cheby configuration will also damp those modes well
> since the polynomial "keeps" 95% of that damping.
>
>
> This is a very soft argument Jed, this may not be differential geometry
> but it is still math ...
>

I was summing up the argument I made in the earlier email. It sounded like
you were suggesting that there was a setting where some smoother would be
fine with standard Richardson relaxation, but not with Chebyshev. In that
vein, suppose that

S = (1 - P^{-1} A)

is a *stable* smoother, therefore it must not amplify any error components.
>From this, we know that the largest eigenvalue of P^{-1}A is less than 2.
Modes with eigenvalues near 1 can be considered "well damped". Let's
consider only real eigenvalues for the moment.

If there is at least one well-damped mode, we have a maximum eigenvalue of
at least 1. Targetting [0.1,1.1]*emax gives Chebyshev(2) roots between
{0.246, 0.954} for emax=1 and {0.493, 1.91} for emax=2, leading to new
damping factors for that lambda=1 mode (on which Richardson was "perfect")
of 0.035 (for emax=1) to -0.46 (for emax=2).

Note that Chebyshev(2) is always stable and damps all modes, including any
possible emax=2 mode that would not be damped at all by the Richardson
relaxation. If we had emax=1.5, the damping factor for all high frequency
modes is around 0.25 or better, which is at least as good as two steps of
Richardson (but with much better damping in the upper and lower ends of the
target spectrum.


> You bring up a good point, if your PC kills the highest modes then they
> are gone because you only ever work with the preconditioned system.
>
> But you can never kill a mode completely and because Cheby blows up out of
> its range, on the high end, then even if there a little high stuff left you
> need to include it in the range of Cheby.
>
>
>
>>
>> On May 25, 2012, at 11:54 AM, Jed Brown wrote:
>>
>> On Fri, May 25, 2012 at 9:06 AM, Mark F. Adams <mark.adams at columbia.edu>wrote:
>>
>>> On May 25, 2012, at 9:42 AM, Jed Brown wrote:
>>>
>>> The high end of the GS preconditioned operator is still high frequency.
>>> If it wasn't, then GS would be a spectrally equivalent preconditioner.
>>>
>>>
>>> Huh?  If I damp Jacobi on the 3-point stencil with 0.5 then the high
>>> frequency is _not_ the "high end of the preconditioned operator". It is
>>> asymptotically 0. Does that mean it is spectrally equivalent?
>>>
>>
>> When I said "high" frequency, I didn't mean "highest" frequency.
>>
>> The low end of the spectrum (that you can't capture) is relatively
>> unperturbed by local smoothers.
>>
>> So let's look at a damped Jacobi preconditioner. Suppose D =
>> [diag(A)]^{-1}. If you weight it by w=0.5 or whatever, the Chebyshev(2)
>> error propagation operator still looks like
>>
>> (I - a w D A) (I - b w D A)
>>
>> where a and b come from the target interval and we build eigenvalue
>> estimates using K = w D A, so we'll produce exactly the same polynomial as
>> w=1.
>>
>> We need better visualization for modes, but if the preconditioned
>> operator K = P^{-1}A has maximum eigenvalue of 1, the second order
>> Chebyshev polynomial targeting [0.1, 1.1] is about (1 - 0.25 K) (1 - 0.95
>> K). Thus, if P^{-1} perfectly corrects the high energy mode, we will use
>> more than 0.95 of that correction.
>>
>>
>> Please correct the above reasoning if I've messed up.
>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20120525/c628395b/attachment.html>