Convergence analysis and parameter choice for the iterated Arnoldi-Tikhonov method
De Lothar Reichel
Apparaît dans la 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.