[petsc-dev] Deflated Krylov solvers for PETSc

[Barry Smith]

   Jie,

   Thanks.  How does one add a "regular" preconditioner to the deflation approach?

In the theory of domain decomposition methods one constructs preconditioners by composing (either additively or multiplicatively) solvers on subspaces of the entire solution space. For simplicity consider symmetric positive definite matrices. 

Now consider a bunch of subspaces defined by non-overlapping subdomains of the domain, from these one produces the block Jacobi or block Gauss-Seidel preconditioner. 

Now say we want to augment block Jacobi or block G.S. by using the solver on the subspace W = Z. 

Now for the question. How would that composed preconditioner relate to doing deflation with W and then block Jacobi preconditioning? Would it be better, worse, depends, identical? What are the formulas in the various cases?

  Barry

On Feb 28, 2013, at 4:59 PM, Jie Chen <jiechen at mcs.anl.gov> wrote:

> I guess viewing deflation as a preconditioner may destroy the symmetry of the system if it is originally symmetric? I wrote a one page technical details about deflation and it may help clarify my thoughts.
> 
> http://www.mcs.anl.gov/~jiechen/tmp/deflate.pdf
> 
> 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: Wednesday, February 27, 2013 2:32:38 PM
> Subject: Re: [petsc-dev] Deflated Krylov solvers for PETSc
> 
> 
>  The PETSc Krylov methods are supposed to be implemented using KSP_MatMult(), KSP_PCApply() etc instead of directly using MatMult() and PCApply() etc.   This means, in theory, one can add support for techniques that modify the application of the multiply or preconditioner in a single place and does not mean changing code in each method implementation.
> 
>   I've always had trouble wrapping my head around if deflation techniques should be viewed as modifications to the Krylov methods or modification (via composing) of the preconditioners. Having this completely clarified would help us understand how deflation could be added to PETSc in a systematic (and hence maintainable) way.
> 
>    Barry
> 
> 
> 
> On Feb 26, 2013, at 10:58 PM, Jie Chen <jiechen at mcs.anl.gov> wrote:
> 
>> To whomever is interested in deflated Krylov solvers:
>> 
>> Deflation is very useful technique for accelerating the convergence of Krylov iterations. It seems to me that deflation is not supported in PETSc, except for the special case DGMRES, where eigenvectors are used to deflate GMRES. As a matter of fact, one does not need to use eigenvectors for deflation, nor deflation is dependent on a specific choice of the iterative method.
>> 
>> Coincidentally, Kees Vuik pointed to me an earlier paper of his:
>> 
>> http://ta.twi.tudelft.nl/nw/users/vuik/papers/Vui01F.pdf
>> 
>> which claims that the convergence of using block Jacobi/ILU(0) [the default preconditioner for PETSc] becomes in general better if deflation is included. In his paper, deflation means "coarse grid acceleration"; see page 935, the paragraph of equation (2).
>> 
>> So I think (including my personal experience), deflation is a general enough technique that may benefit every user of the KSP solver. Implementation-wise, my personal take is that the library needs to change the A-multiply to (A-AZ(Z'AZ)^{-1}Z'A)-multiply, where Z is the deflation matrix: tall, skinny, and with a small number of columns. PETSc can ask the user to define Z, and it can also predefine several choices of Z, one example choice is from the above mentioned paper. In principle, deflation should be independent of the KSP types, but I don't see how exactly it can be implemented without touching the code of every krylov solvers. Perhaps adding one more layer of abstraction is needed.
>> 
>> So for anyone who is interested in implementing deflation, I can provide a more detailed tutorial. The design of PETSc is becoming more and more complicated for me to digest, thus I think it may be unrealistic for me to implement deflation myself for the moment.
>> 
>> Jie
>> 
>> 
>> 
>> -- 
>> Jie Chen
>> Mathematics and Computer Science Division
>> Argonne National Laboratory
>> Address: 9700 S Cass Ave, Bldg 240, Lemont, IL 60439
>> Phone: (630) 252-3313
>> Email: jiechen at mcs.anl.gov
>> Homepage: http://www.mcs.anl.gov/~jiechen
>