May 2012 - petsc-dev - mailman3.cels.anl.gov

Re: [petsc-dev] Multigrid is confusing
by Mark F. Adams 25 May '12

25 May '12

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

1 0

Re: [petsc-dev] Multigrid is confusing
by Jed Brown 25 May '12

25 May '12

On Fri, May 25, 2012 at 4:59 PM, Mark F. Adams <mark.adams(a)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(a)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(a)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. >> >> >> > >

1 0

Re: [petsc-dev] Multigrid is confusing
by Mark F. Adams 25 May '12

25 May '12

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

1 0

Re: [petsc-dev] ctetgen into its own repository
by Barry Smith 25 May '12

25 May '12

On May 25, 2012, at 4:02 PM, Matthew Knepley wrote: > On Fri, May 25, 2012 at 4:03 PM, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > Because of the tetgen license we cannot include ctetgen directly in the PETSc tarball. Thus we have forked it off into its own repository and it is available for users as --download-ctetgen Developers may choose to hg clone the repository directly into petsc-dev/externalpackages if they have any need to work on the ctetgen source code. > > How can the fucking license say that we cannot include ASCII code is our goddamn release. What if I > take a picture of the code and include the JPG? I already put in a configure option to turn it on. This is > ridiculous. Are you sure that we can include the letter P. I think Sesame Street has rights to that. Sarcastic answer: I broke into Microsoft headquarters last week and took a copy of the Windows 8 source code. As a convenience to some of our users I have added it to the PETSc source code tree and it will be included in the future releases. Unsarcastic answer: Yes we can include ctetgen in our release but then we need to change our license to be much more restrictive (non-MIT etc) which we do not want. The tetgen license doesn't say anything about allowing it under more general license if the compiling of it is "optional" Barry > > Matt > > > Barry > > > > > > -- > 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

1 0

Re: [petsc-dev] ctetgen into its own repository
by Matthew Knepley 25 May '12

25 May '12

On Fri, May 25, 2012 at 4:03 PM, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > Because of the tetgen license we cannot include ctetgen directly in the > PETSc tarball. Thus we have forked it off into its own repository and it > is available for users as --download-ctetgen Developers may choose to hg > clone the repository directly into petsc-dev/externalpackages if they have > any need to work on the ctetgen source code. How can the fucking license say that we cannot include ASCII code is our goddamn release. What if I take a picture of the code and include the JPG? I already put in a configure option to turn it on. This is ridiculous. Are you sure that we can include the letter P. I think Sesame Street has rights to that. Matt > > Barry > > > -- 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

1 0

Re: [petsc-dev] Multigrid is confusing
by Jed Brown 25 May '12

25 May '12

On Fri, May 25, 2012 at 3:16 PM, Mark F. Adams <mark.adams(a)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. > > 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(a)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. > > >

1 0

Re: [petsc-dev] Multigrid is confusing
by Mark F. Adams 25 May '12

25 May '12

Yes your are right, simply scaling the PC will result in scaling the eigenvalues and hence the Cheby factors. 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(a)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.

1 0

ctetgen into its own repository
by Barry Smith 25 May '12

25 May '12

Because of the tetgen license we cannot include ctetgen directly in the PETSc tarball. Thus we have forked it off into its own repository and it is available for users as --download-ctetgen Developers may choose to hg clone the repository directly into petsc-dev/externalpackages if they have any need to work on the ctetgen source code. Barry

1 0

ctetgen into its own repository
by Barry Smith 25 May '12

25 May '12

Because of the tetgen license we cannot include ctetgen directly in the PETSc tarball. Thus we have forked it off into its own repository and it is available for users as --download-ctetgen Developers may choose to hg clone the repository directly into petsc-dev/externalpackages if they have any need to work on the ctetgen source code. Barry

1 0

Re: [petsc-dev] Multigrid is confusing
by Jed Brown 25 May '12

25 May '12

On Fri, May 25, 2012 at 9:06 AM, Mark F. Adams <mark.adams(a)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.

1 0