PREDICT-AND-RECOMPUTE CONJUGATE GRADIENT VARIANTS

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10420374" target="_blank" >RIV/00216208:11320/20:10420374 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=IWjwpu7em" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=IWjwpu7em</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/19M1276856" target="_blank" >10.1137/19M1276856</a>

Result language

angličtina

Original language name

PREDICT-AND-RECOMPUTE CONJUGATE GRADIENT VARIANTS

Original language description

The standard implementation of the conjugate gradient algorithm suffers from communication bottlenecks on parallel architectures, due primarily to the two global reductions required every iteration. In this paper, we study conjugate gradient variants which decrease the runtime per iteration by overlapping global synchronizations, and in the case of pipelined variants, matrix-vector products. Through the use of a predict-and-recompute scheme, whereby recursively updated quantities are first used as a predictor for their true values and then recomputed exactly at a later point in the iteration, these variants are observed to have convergence behavior nearly as good as the standard conjugate gradient implementation on a variety of test problems. We provide a rounding error analysis which provides insight into this observation. It is also verified experimentally that the variants studied do indeed reduce the runtime per iteration in practice and that they scale similarly to previously studied communication-hiding variants. Finally, because these variants achieve good convergence without the use of any additional input parameters, they have the potential to be used in place of the standard conjugate gradient implementation in a range of applications.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10102 - Applied mathematics

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

SIAM Journal of Scientific Computing

ISSN

1064-8275

e-ISSN

—

Volume of the periodical

42

Issue of the periodical within the volume

5

Country of publishing house

US - UNITED STATES

Number of pages

25

Pages from-to

"A3084"-"A3108"

UT code for WoS article

000600650100020

EID of the result in the Scopus database

2-s2.0-85094937014