Iterative Solvers Based on Domain Decomposition

This chapter concerns iterative solution techniques for linear systems of equations arising from the discretization of elliptic boundary value problems. Very often huge systems are obtained, with condition numbers which depend on the meshsize h of the triangulation, which typically grow in proportion to h-2. Then, classical iteration schemes like Jacobi-, Gauß-Seidel or SOR-type methods result in very slow convergence rates. Fig. 2.1 shows the convergence rates and the number of iteration steps versus the number of unknowns, for a simple model problem in 2D. In the left, the convergence rates are given, and in the right the number of iteration steps to obtain an error reduction of 10-6 are shown. For the Jacobi and the Gauß-Seidel method, the asymptotic convergence rates are 1 — O(h2). The optimal SOR-method is asymptotically better and tends with O(h) to one. However, the optimal damping parameter is, in general, unknown. The number of required iteration steps reflects the order of the method. For the Gauß-Seidel and the Jacobi method, the number of required iteration steps grows quadratically with one over the meshsize. In case of the optimal SOR-method, the increase is linear. Moreover, the numerical results show that the Jacobi method requires two times the number of Gauß-Seidel iteration steps.