[petsc-dev] Deflated Krylov solvers for PETSc

[Barry Smith]

On Mar 3, 2013, at 12:52 AM, Jie Chen <jiechen at mcs.anl.gov> wrote:

> Barry,
> 
> Putting P_{A} either to the left or to the right of A means the same thing: we avoid touching the subspace spanned by W. This is why the orthogonality condition b-Ax_0 \perp W is needed. What the condition says is that the initial residual should have no components on W, presumably the troublesome part of A. Then in a Krylov method, all later residuals have no components on W. In other words, the part of the solution on the subspace W is already fully computed even in the 0-th step. Getting such an x_0 is not difficult; the difficult part is to define/compute W.

   Exactly.
> 
> When one adds another preconditioner M to the system, presumably W should be the troublesome part of AM instead of A (I am always confused about the notation M and M^{-1} but it does not affect my reasoning here).

    The beauty of the composing precondition preconditioners approach is that if one has a good preconditioner for "part" of the solution space then all one needs is to find good preconditioners for the other "parts" of the solution space.  One doesn't need to worry about finding a good preconditioner for the troublesome part of AM, one only needs a good preconditioner for the part of the solution space that M does not handle well. Is it different for deflation?

  Barry

> In the aggressive way W can consist of eigenvectors of the pencil (A,M) corresponding to the smallest eigenvalues in magnitude. On the other hand, if one already found a good W for A and he/she is lazy and does not want to re-figuring out W, then just use the old W. I guess the beauty of the deflation theory is that W can be arbitrary but does not depend on A or M.
> 
> I sense that you want a preconditioner appearing in (4) and the formula for x_0? I will add something there later.
> 
> Jie
> 
> 
> 
> 
> 
> ----- Original Message -----
> From: "Barry Smith" <bsmith at mcs.anl.gov>
> To: "For users of the development version of PETSc" <petsc-dev at mcs.anl.gov>
> Sent: Saturday, March 2, 2013 10:33:05 PM
> Subject: Re: [petsc-dev] Deflated Krylov solvers for PETSc
> 
> 
>  Jie,
> 
>   Thanks. I think you know this but it is worth writing in the notes: 
> 
> For symmetric positive definite problems you can write the preconditioned operator (ignore the right hand side) as
> right preconditioning
> 
> A[I − W(W^{H}AW)^{−1}W^{H}A] x   = A P_{A} x 
> 
> and see exactly what the deflation is doing. It is projecting any vector x onto the subspace spanned by W (in the A inner product) and removing it from the vector before applying A. Hence A (and the Krylov method) never "sees" that part of the space ( in other words that troublesome part of A). Similarly if you  write it as left preconditioning you have 
> 
> P_{A}^{H} A x 
> 
> Hence the Krylov space does not contain the null space of P_{A}^{H}. Again, presumably removing some troublesome part of A. 
> 
>  In my book, top of page 17 is the statement: 
> 
> "The procedure of restriction, (approximately) solving a small linear system, and interpolation lies at the heart of all domain decomposition and multigrid/multilevel algorithms. As indicated above and … this procedure calculates the projection of the unknown error onto a subspace and uses the result as a correction term. An effective domain decomposition algorithm will generate the appropriate subspaces that provide a good representation of the solution".
> 
>  This is why I am interested in understanding EXACTLY the relationship of deflation and preconditioning and the subspaces used. Another way to phrase it is does one (1) augment the preconditioner with another subspace to generate the Krylov space (composing preconditioners in the DD/Multigrid sense) or (2) does one remove those certain "modes" from ever getting into the Krylov subspace?  Or are the two different things actually more or less one and the same?
> 
>  I don't know the answer but if we knew the answer it would help us understand how/where deflation might belong in PETSc (or maybe multiple places).
> 
>  Barry
> 
> 
> 
> On Mar 2, 2013, at 9:43 PM, Jie Chen <jiechen at mcs.anl.gov> wrote:
> 
>> Mark, Barry, Jed,
>> 
>> You guys raised quite a few questions, meanwhile I found a mistake in my note. I think I should rewrite the note to incorporate a more comprehensive view. Hopefully the new note will answer you questions (at least to a certain degree). I have something very important to finish before Wednesday, so my participation in the discussion may delay. See the new note in the old place:
>> 
>> http://www.mcs.anl.gov/~jiechen/tmp/deflate.pdf
>> 
>> Jie
>> 
>> 
>> 
>> 
>> ----- Original Message -----
>> From: "Mark F. Adams" <mark.adams at columbia.edu>
>> To: "For users of the development version of PETSc" <petsc-dev at mcs.anl.gov>
>> Sent: Saturday, March 2, 2013 12:54:34 PM
>> Subject: Re: [petsc-dev] Deflated Krylov solvers for PETSc
>> 
>> 
>> On Mar 2, 2013, at 12:45 PM, Barry Smith <bsmith at mcs.anl.gov> wrote:
>> 
>>> 
>>> On Mar 2, 2013, at 11:16 AM, "Mark F. Adams" <mark.adams at columbia.edu> wrote:
>>> 
>>>>> 
>>>>> An alternative description for the method in the paper is "two-level unsmoothed aggregation applied to the ASM-preconditioned operator".
>>>>> 
>>>> 
>>>> Isn't this paper just doing two level unsmoothed aggregation with a V(0,k) cycle, where k (and the smoother) is K in the paper?
>>>> 
>>>> It looks to me like you are moving the multigrid coarse grid correction (projection) from the PC into the operator, in which case this method is identical to two level MG with the V(0,k) cycle.
>>> 
>>> Well, its not "identical" is it?
>> 
>> My thinking is that with Q = P (RAP)^-1 R, and smoother S, then a two level V(0,1) PC (M) looks like: S (I - Q). (I think I'm missing an A in here, before the Q maybe) The preconditioned system being solved looks like:
>> 
>> MAx = Mb
>> 
>> with MG PC we have:
>> 
>> (S (I-Q)) A x = …
>> 
>> Move the brackets around
>> 
>> S ((I-Q)A)  x = ..
>> 
>> S is K in the paper and (I-Q)A is the new operator.  The preconditioned system does not have a null space and thats all that matters.
>> 
>> Anyway, I'm sure its not identical, I'm just not seeing it in this paper and don't have the patients work through it … and maybe I'm having a bad arithmetic day but on page 935, the definition of P (first equation on page) and Pw (last equation on page) don't look consistent.
>> 
>> 
>>> In the deflation approach it introduces a null space into the operator, in the multigrid approach it does not. So identical only in analogy? So what I am interested in EXACTLY how are they related, relationship between eigenvalues or convergence rate.
>>> 
>>> Barry
>>> 
>>>> 
>>>> I'm sure I'm missing something.  Jie's writeup has an orthogonality condition on the restriction operator, which I don't see in the Vuik paper.
>>> 
>>> 
>> 
>