Extrapolation Cascadic Multigrid Method

How to solve the linear system of equations derived by finite difference method or finite element method rapidly is an important issue in large-scale scientific and engineering computing. People's goal is to obtain the solution with required accuracy of N-order system through O(N) times multiplication and division operations. Multi-grid method(MG) achieves this goal for the first time, and becomes the most effective method to solve large-scale problems. Since 1970's, the multi-grid method has been in-depth study, and a systematic theory on MG has been developed. However, MG repeatedly uses three kinds of operations(interpolation, restriction and iterative) in coarse and fine grids, so its code looks complex. In 1996, Bornemann et al. proposed the so-called Cascadic Multi-grid method(CMG), which requires no coarse grid corrections at all and may be viewed as a "one way" multigrid method. Only the interpolation and iteration from coarse grids to refined grids are used in CMG, thus its code is easy to implement and more remarkable.This paper proposes a new Extrapolation Cascadic Multi-grid method, the main work and innovation points are as follows.An extrapolation cascadic multi-grid method(EXCMG) is proposed in the paper. Based on an asymptotic expansion of finite element, a new extrapolation formula is derived. Follows CMG's idea, the new algorithm uses new extrapo-lation and quadratic interpolation in place of the linear interpolation in coarse grids to provide a better initial value of fine grids. It reduces the initial error essentially, and plays a key role in the acceleration of convergence speed. The proposed algorithm converges with high-accuracy for functions and derivatives. The discrete elliptic problem with 4 million unknowns has been solved by EX-CMG on PC in 10 minutes. Errors on the finest grids attain the accuracy 10-8, which further confirms the advantages of CMG.This paper proves the l2-norm boundedness and convergence of conjugate gradient method(CG) for the first time. So far, the convergence of CG has been obtained only in the sense of energy norm; hence it is a new result. When mLβ-L-i is taken as the iteration number on grid Zt, we find that there is a "threshold" i0 about grid level for CG-based Multi-grid method. That is, the error on Zi will decay rapidly if i< i0, while i> i0 the role of CG is only smoothing. This feature plays an important role in proving the convergence of EXCMG in the sense of discrete L2 norm.For the solution u∈H3,we have proved the asymptotic expansion of bilin-ear element with O(h3) accuracy for all nodes in the sense of discrete L2 norm, thus EXCMG is still valid. Existing work on asymptotic expansion is about a smooth solution(such as u∈C3)in sense of point by point. The above results extend the application of EXCMG. Numerical experiments show that EXCMG is also valid for non-smooth solutions (u∈H3 or u∈H2).