The Convergence Rate of Block Preconditioned Systems Arising from LMF-based ODE Codes

The solution of ordinary and partial differential equations using implicit linear multistep formulas (LMF) is considered. More precisely, boundary value methods (BVMs), a class of methods based on implicit formulas will be taken into account in this paper. These methods require the solution of large and sparse linear systems M̂x = b. Block-circulant preconditioners have been proposed to solve these linear system. By investigating the spectral condition number of M̂, we show that the conjugate gradient method, when applied to solving the normalized preconditioned system, converges in at most O(log s) steps, where the integration step size is O(1/s). Numerical results are given to illustrate the effectiveness of the analysis.