Multiple search direction conjugate gradient method I: methods and their propositions

Abstract

In this article, we proposed a new CG-type method based on domain decomposition method, which is called multiple search direction conjugate gradient (MSD-CG) method. In each iteration, it uses a search direction in each subdomain. Instead of making all search directions conjugate to each other, as in the block CG method [O'Leary, D. P. (1980). The block conjugate gradient algorithm and related methods. Lin. Alg. Appl., 29, 293–322.], we require that they are nonzero in corresponding subdomains only. The GIPF-CG method, an approximate version of the MSD-CG method, only requires communication between neighboring subdomains and eliminate global inner product entirely. This method is therefore well suited for massively parallel computation. We give some propositions and a preconditioned version of the MSD-CG method.

Keywords:

• Linear systems
• Conjugate gradient-type method
• Massively parallel computing
• Inner product
• Global communication

Acknowledgements

The project is supported partly by State Hi-Tech Research and Development Program (863) and Natural Science Fund of China (60373015) and the Foundation of National Key Laboratory of Computational Physics.