Krylov subspace acceleration method for nonlinear multigrid schemes

Takumi Washio

C\&C Research Laboratories, NEC Europe Ltd., D-53757 Sankt Augustin, Germany


C. W. Oosterlee

GMD, Institute for Algorithms and Scientific Computing, D-53754 Sankt Augustin, Germany


It is well-known that multigrid solution methods are the optimal O(N) solvers, when all components in a method are chosen properly. For difficult problems, like for certain systems of nonlinear equations, however, it is far from trivial to choose these optimal components. The influence on the multigrid convergence of combinations of complicated phenomena, like convection-dominance, anisotropies, nonlinearities or non M-matrix properties is often hard to predict. Problems might then occur with the choice of the best under-relaxation parameter in the smoother, with the choice of the coarse grid correction, or with the transfer operators. In this talk, we are concentrating on nonlinear problems, and aim to construct a nonlinear acceleration equivalence to GMRES for linear problems.

Another (more known) research direction is to construct efficient nonlinear solution methods on the basis of a global Newton linearization. The resulting linear system is then solved with a linear multigrid method, or with Krylov-type methods (Newton-Krylov methods). A disadvantage of these methods is that every linearization step a matrix of Jacobians must be evaluated and stored. Since the basis of our method is nonlinear multigrid, Jacobians are only evaluated locally (point- or linewise) in the smoother on every grid level. The nonlinear Krylov acceleration is performed on the finest grid level, and can be seen as an outer iteration for the multigrid preconditioner. Therefore it is very easy to implement it in already existing codes with a nonlinear multigrid variant as a solver, like Navier-Stokes or Euler codes. Another advantage of the nonlinear acceleration scheme presented is the cheapness in computational cost of our method, with respect to the multigrid preconditioner. The (nonlinear) search directions are constructed from available intermediate solution vectors. Jacobians are approximated by the residual vectors for the intermediate solutions, so that they are not recomputed explicitly in our Krylov acceleration technique. In this sense the method suits very well to the nonlinear multigrid method.

Numerical results with this approach are presented for nonlinear elliptic scalar PDEs, like for the Bratu problem, where the convergence difficulty to obtain the second solution for certain parameters with FAS is nicely improved by the Krylov acceleration technique. Also results are presented for systems of the incompressible Navier-Stokes and Euler equations, where the discretization is based on the primitive variables.