[petsc-dev] Multigrid is confusing

[Mark F. Adams]

On May 25, 2012, at 7:16 PM, Jed Brown wrote:

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

Yes, I forgot what we were arguing about there for a minute :)

My thinking was that Cheby _could_ degrade performance over Richardson (for G-S in particular).  That is that I could construct a smoother/operator for which Cheby would not pick the correct damping (so if the PC/operator was damped perfectly Richardson could win).

I'm not sure if that is true now.

Regardless, I do want to get true G-S in PETSc this summer.  For very unsymmetric problems its a nice thing to have in your tool box.  

> 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/b895d1dd/attachment.html>