9

In the solution of sequences of linear systems $$A_ix_i=b_i\quad\text{for}\quad i=1,2,\dots$$ with Krylov subspace methods, data can be recycled from already solved linear systems in order to speed up the computation of subsequent linear systems (complementary to preconditioning). For the analysis of recycling strategies I developed in my PhD thesis and which are implemented in KryPy, I'm looking for interesting cases of sequences of linear systems that satisfy the following conditions:

  1. The (possibly preconditioned) matrices exhibit only a few eigenvalues close to zero that are separated from the remaining spectrum. Often, the presence of a few eigenvalues of small magnitude is responsible for an initial slow convergence of CG, MINRES or GMRES.
  2. The matrices are sparse.
  3. The problem can be boiled down to small scale (dim<1000).
  4. The matrices and/or the right hand sides of the linear systems may change but the difference should be within limits.
  5. The problem can be implemented in a few lines of code, preferably based on well-known Python packages such as NumPy, SciPy, FEniCS, PyAMG, ...
  6. Symmetric/Hermitian matrices would be nice but are not a must.

Candidates for such sequences are time-dependent problems, nonlinear problems (e.g. with Newton's method), parameter-dependent problems, shifted linear systems, ...

One application that satisfies the above criteria and benefits from recycling Krylov solvers are nonlinear Schrödinger equations, see this paper on arxiv. I'm now looking for a simpler model problem in order to demonstrate the mathematical idea without being computationally cumbersome.

andrenarchy
  • 231
  • 1
  • 2
  • Do you need the actual matrices, or is it enough to be able to compute the matrix-vector product? Deblurring, denoising and medical image reconstruction would all fit the bill. – LKlevin Apr 04 '14 at 16:03
  • 1
    Nonlinear diffusion problems (or generally nonlinear PDEs) is a good source of sequences of systems. – Algebraic Pavel Apr 04 '14 at 17:05
  • In general, the matrices are not needed in the setting of Krylov subspace methods. However, it would be nice to have them available for analyzing several properties, e.g., differences between the matrices. Anyway, thanks for your hints so far! – andrenarchy Apr 04 '14 at 21:11
  • The approach described in your arxiv paper seems interesting. I would like to learn more about the subject. Would it be possible to point me some documentation on how to implement this idea in GMRES please ? – Christine Darcoux May 21 '14 at 20:40
  • 1
    The recycling strategy consists of 2 components: a deflated Krylov subspace method and the extraction of vectors for deflation. For GMRES, the deflated method consists of applying GMRES to a projected linear system $PAx=Pb$ and the iterates are corrected afterwards, see http://epubs.siam.org/doi/abs/10.1137/110820713. The extraction of Ritz vectors for use as deflation vectors works analogous to the one in the arxiv paper. Only minor modifications have to be made for non-Hermitian matrices. You can also check the implementation in https://github.com/andrenarchy/krypy. – andrenarchy May 22 '14 at 08:44

0 Answers0