Block preconditioning for the conjugate gradient method

In this paper we study some preconditioning techniques for the conjugate gradient method to solve the linear systems of equations that arise from the discretization of partial differential equations. The techniques that we describe are suitable for standard finite-difference discretizations of equations. Such equations can arise also from finite element discretizations with node groupings that form a tree. The prototype model problem in two dimensions is the Dirichlet problem. The goal of this study is to devise good preconditioning matrices. For this purpose we exploit the structure of certain symmetric positive definite block tridiagonal linear systems in constructing some block preconditioning, one special case of which is the one introduced by R.R. Underwood. In Section 2 to motivate the use of our block techniques we recall some results on block Cholesky factorization. Section 3 deals with the main problem - finding good approximate inverses for tridiagonal matrices that are diagonally dominant. New block techniques for two-dimensional problems are introduced in Section 4. Three-dimensional problems will be discussed in detail in a subsequent study. In Section 5 we present numerical experiments for several test problems. As comparisons are made with point preconditioning techniques, some of them are recalled briefly there. We compare the methods on the basis of number of iterations and the number of floating point operations required. Also, we illustrate graphically the spectral properties of the matrices corresponding to the various preconditioning. (author)