[petsc-dev] Deflated Krylov solvers for PETSc

[Matthew Knepley]

On Wed, Feb 27, 2013 at 12:20 AM, Jed Brown <jedbrown at mcs.anl.gov> wrote:

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

I think the problem with that approach to deflation is preconditioning,
unless you use injection as Vuik does. You can easily get
this kind of projection by using MatShell.

I tried Ronald Morgan's stuff when I was in grad school and it never made a
bit of difference. Is there any situation where deflation
is useful and cannot be phrased as our current MG?

    Matt


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


-- 
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20130227/1a57bcc0/attachment.html>