Computational & Technology Resources
an online resource for computational,
engineering & technology publications
PROCEEDINGS OF THE SIXTH INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED, GPU AND CLOUD COMPUTING FOR ENGINEERING
Edited by: P. Iványi and B.H.V. Topping
Parallel iterative methods with retards for linear systems
Q. Zou1 and F. Magoules1,2
1CentraleSupélec, Université Paris-Saclay, France
Q. Zou, F. Magoules, "Parallel iterative methods with retards for linear systems", in P. Iványi, B.H.V. Topping, (Editors), "Proceedings of the Sixth International Conference on Parallel, Distributed, GPU and Cloud Computing for Engineering", Civil-Comp Press, Stirlingshire, UK, Paper 31, 2019. doi:10.4203/ccp.112.31
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)