00:00:00 / 00:00:00

Detection and correction of silent errors in the Conjugate Gradient algorithm

By Gérard Meurant

Appears in collection : Numerical Methods and Scientific Computing / Méthodes numériques et calcul scientifique

There are more and more computing elements in modern supercomputers. This increases the probability of computer errors. Errors that do not stop the computation are called soft errors or silent errors. Of course, they could have a negative impact on the output of the code. So, it is of interest to be able to detect these silent errors and to correct them. In this talk we are concerned with the detection and correction of silent errors in the conjugate gradient (CG) algorithm to solve linear systems Ax = b with a symmetric positive definite matrix A. Silent errors in CG may affect or even prevent the convergence of the algorithm. We propose a new way to detect silent errors using a scalar relation that must be satisfied by CG variables, $\alpha_{2 k-1}\tfrac{\left(A p_{k-1}, A p_{k-1}\right)}{\left(r_{k-1}, r_{k-1}\right)}=1+\beta_{k},(1)$ where rj's are the residual vectors, pj's the descent directions and $\alpha_{k-1}=\tfrac{\left(r_{k-1}, r_{k-1}\right)}{\left(\mathrm{p}_{\mathrm{k}-1}, \mathrm{Ap}_{\mathrm{k}-1}\right)}$, $\beta_{\mathrm{k}}=\frac{\left(\mathrm{r}_{\mathrm{k}}, \mathrm{r}_{\mathrm{k}}\right)}{\left(r_{k-1}, r_{k-1}\right)}$ are the coefficients computed in $\mathrm{CG}$. We study how relation (1) is modified in finite precision arithmetic and define a criterion to detect when this relation is not satisfied. Checking relation (1) involves computing an additional dot product, but, as it was shown some time ago in [1] and more recently in [2], relation (1) can be used to introduce more parallelism in the algorithm. Assuming that the input data $(A, b)$ is not corrupted, we model silent errors by bit flips in the output of some CG steps. When an error is detected in some iteration $\mathrm{k}$, we could restore the CG data from iteration $k-2$ to be able to continue the computation safely. Numerical experiments will show the efficiency of this approach.

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.19829403
  • Cite this video Meurant Gérard (11/9/21). Detection and correction of silent errors in the Conjugate Gradient algorithm. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19829403
  • URL https://dx.doi.org/10.24350/CIRM.V.19829403



Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow


  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
  • Get notification updates
    for your favorite subjects
Give feedback