Multilevel projection-based Krylov subspace iteration

Yogi A. Erlangga

TU Berlin, Institute for Mathematics, Strasse des 17. Juni 136, D-10623 Berlin, Germany

Reinhard Nabben


Abstract

In this talk we discuss a multilevel projection-based method for acceleration of Krylov subspace methods. The projection is constructed based on shifting of small eigenvalues towards the largest eigenvalue. Compared to deflation, which shifts small eigenvalues to zero, both projections result in spectrally similar linear systems. The new projection method is however much more stable than deflation with respect to the coarse grid solves. This allows the use of inner iterations to solve the coarse grid problems. By constructing a sequence of coarse grid matrices, Krylov subspace iterations solve the projected coarse grid problem at each level. Different with multigrid, the success of multilevel projection Krylov subspace depends on the projection of small eigenvalues, which are responsible for slow convergence. The coarse grid problem is then solved by the same projected Krylov subspace method. This leads to a recursive (nested) iterations. Since our projection method is insensitive to the inaccurate coarse grid solves, only a few Krylov iterations required in the coarse levels. Multigrid transfer operators can be used for constructing the coarse grid matrices. In our case, however, the chosen intergrid transfer operators are simpler than multigrid transfer operators, and are applicable for general finite element triangulation. We present numerical results from solving the Poisson equation and the convection-diffusion equation, both in 2D. The latter represents the case where the related matrix of coefficients is nonsymmetric. Compared to standard multigrid V-cycle with one pre- and post Jacobi smoothing, our multilevel method converges faster. We also observe $h$-independent convergence. For the convection-diffusion equation, we present a case where standard multigrid methods fail to convergence. By using the diagonal scaling preconditioner, our multilevel method still converges.