A parallel preconditioned inner product-free algorithm for sparse least squares problems

摘要

On modern architecture the performance of CGLS, a basic iterative method whose main idea is to organize the computation of conjugate gradient method applied to normal equations for solving sparse least squares problems is always limited because of the global communication required for inner products. Inner products often therefore present a bottleneck, and it is desirable to reduce or even eliminate all the inner products. Here we present an inner product-free conjugate gradient-like algorithm, that s imulates the standard conjugate gradient by approximating the conjugate gradient orthogonal plynomial by suitable chosen orthogonal polynomial from Bernstein-Szego class, with Chebsyshev polynomial preconditioner which is constructured based on the observation that good estimates for the eigenvalue distribution can be surprisingly derived after only a few steps of the conjugate gradient-type method. For the inner product-free algorithm, the parallel performance has been compared with the standard and modified approaches. For Chebyshev polynomial preconditioner, theoretically it is optimal for which the eigenvalue distribution is highly ill-conditioned. The experimental comparison results with other techniques are reported as well.