[petsc-dev] Deflated Krylov solvers for PETSc

[Jie Chen]

Well not surprising that there are a lot of equivalences between deflation from the Krylov point of view and restriction/prolongation from the multigrid point of view. And of course constructing/refining the deflation matrix can be a central piece of research work. Vuik's paper does something simple, yet effective: the deflation Z is a matrix of 0's and 1's, where the 1's correspond to each subdomain.

I do not exactly understand how to use PCComposite and PCGalerkin. But I suppose that you do not want them to appear in user's code (application code), right?

Jie




----- Original Message -----
From: "Jed Brown" <jedbrown at mcs.anl.gov>
To: "For users of the development version of PETSc" <petsc-dev at mcs.anl.gov>
Sent: Wednesday, February 27, 2013 12:20:49 AM
Subject: Re: [petsc-dev] Deflated Krylov solvers for PETSc



Interesting. I've always thought of deflation as being about the construction of the deflation vectors rather than application of the projection, which I think can be implemented by composing PCComposite and PCGalerkin (or with a degenerate Galerkin two-level multigrid cycle). Note that the DGMRES construction has some similarities to Bootstrap AMG in that low-energy eigenvectors are processed incrementally and used to define the new coarse grid. 

On Tue, Feb 26, 2013 at 11: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