Some observations on the l2 convergence of the additive Schwarz preconditioned GMRES method

Additive Schwarz preconditioned GMRES is a powerful method for solving large sparse linear systems of equations on parallel computers. The algorithm is often implemented in the Euclidean norm, or the discrete l² norm, however, the optimal convergence result is available only in the energy norm (or the equivalent Sobolev H¹ norm). Very little progress has been made in the theoretical understanding of the l² behaviour of this very successful algorithm. To add to the difficulty in developing a full l² theory, in this note, we construct explicit examples and show that the optimal convergence of additive Schwarz preconditioned GMRES in l² cannot be obtained using the existing GMRES theory. More precisely speaking, we show that the symmetric part of the preconditioned matrix, which plays a role in the Eisenstat–Elman–Schultz theory, has at least one negative eigenvalue, and we show that the condition number of the best possible eigenmatrix that diagonalizes the preconditioned matrix, key to the Saad–Schultz theory, is bounded from both above and below by constants multiplied by h^?1/2. Here h is the finite element mesh size. The results presented in this paper are mostly negative, but we believe that the techniques used in our proofs may have wide applications in the further development of the l² convergence theory and in other areas of domain decomposition methods. Copyright © 2002 John Wiley & Sons, Ltd.