Multilevel Projection-Based Nested Krylov Iteration for Boundary Value Problems

• Published in: SIAM journal on scientific computing 2008-01, Vol.30 (3), p.1572-1595
• Main Authors: Erlangga, Yogi A., Nabben, Reinhard
• Format: Article
• Language: English
• Subjects: Approximation; Boundary value problems; Eigenvalues; Eigenvectors; Methods
• ISSN: 1064-8275; 1095-7197
• DOI: 10.1137/070684550

We propose a multilevel projection-based method for acceleration of Krylov subspace methods. The projection is constructed in a similar way as in deflation but shifts small eigenvalues to the largest one instead of to zero. In contrast with deflation, however, the convergence rate of a Krylov method combined with this new projection method is insensitive to the inaccurate solve of the Galerkin matrix, which with some particular choice of deflation subspaces is closely related to the coarse-grid solve in multigrid or domain decomposition methods. Such an insensitivity allows the use of inner iterations to solve the Galerkin problem. An application of a Krylov subspace method to the associated Galerkin system with the projection preconditioner leads to a multilevel, nested Krylov iteration. In this multilevel projection Krylov subspace method, information about small eigenvalues to be projected is contained implicitly in the Galerkin system associated with the matrix of the linear system to be solved. These small eigenvalues, from a Krylov method point of view, are responsible for slow convergence. In terms of projection methods, this is conceptually similar to multigrid but different in the sense that in multigrid the projection is done by the smoother. Furthermore, with the only condition being that the deflation matrices are full rank, we have in principle more freedom in choosing the deflation subspace. Intergrid transfer operators used in multigrid are some of the possible candidates. We present numerical results from solving the Poisson equation and the convection-diffusion equation, both in two dimensions. The latter represents the case where the related matrix of coefficients is nonsymmetric. By using a simple piecewise constant interpolation as the basis for constructing the deflation subspace, we obtain the following results: (i) $h$-independent convergence for the Poisson equation and (ii) almost independent of $h$ and the Péclet number for the convection-diffusion equation.