Keywords: s-step iterative methods, gradient methods with retards, Barzilai-Borwein method, linear systems, parallel computing.

Classical iterative methods require data movement in each iteration, yielding a bottleneck in parallel processing. The s-step formulations, through s simultaneously formed directions, can reduce the global synchronizations. For example, we can break the data dependencies of inner products and perform other operations one after another within s iterations. The matrix-vector multiplications and the solutions of subsystems can be parallelized by basic routines such as gathering and reducing. This strategy was originally designed for the steepest descent method by minimizing the A-norm error over an s-dimensional plane. Then it has efficiently evolved over the years for other projection methods such as the minimal residual method and several Krylov subspace methods.
In this paper we are interested in the s-step formulations of the iterative methods with retards, which involve lagged coefficients during vector updates, thus resulting in a nonmonotone decreasing for the quadratic function. The pioneering work of lagged iterative methods was done three decades ago by Barzilai and Borwein, then leading to a framework called gradient methods with retards. In order to exploit such methods on parallel computers, the iterative scheme should be modified. Convergence results are given and numerical experiments are conducted on physical problems to illustrate the efficiency.

purchase the full-text of this paper (price £22)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £25 +P&P)