A block-parallel conjugate gradient method for separable quadratic programming problems

For a large-scale quadratic programming problem with a separable objective function, a variant of the conjugate gradient method can effectively be applied to the dual problem. In this paper, the authors consider a block-parallel modification of the conjugate gradient method, which is suitable for implementation on a parallel computer. More precisely, the method proceeds in a block Jacobi manner and executes the conjugate gradient iteration to solve quadratic programming subproblems associated with respective blocks. The authors implement the method on a Connection Machine Model CM-5 in the Single-Program Multiple-Data model of computation. They report some numerical results, which show that the proposed method is effective particularly for problems with some block structure.