1
$\begingroup$

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction or checking orthogonality of residuals?

Note: here by error I mean error from floating point unit of CPU because of incorrect computation (which can be due to corrupt data in cache etc.) not due to rounding error. In some cases the errors can be due incorrect computation of matrix vector product (in cases where matrix A is not explicitly available).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Your definition of "error" seems unrelated to the conjugate gradient algorithm per se ("due to corrupt data in cache etc."). I see no reason to think there should be a CG specific way to "check" for errors of that kind. You may also be conflating hardware and software errors when you reference "incorrect computation of matrix vector product". Certainly a component module performing that task should be debugged with respect to its own specifications, as incorrect matrix-vector products cannot be useful for reliable implementation of a conjugate gradient solver. $\endgroup$ – hardmath Nov 28 '12 at 16:01
  • $\begingroup$ Think about this as follows: I give you a piece of "probabilistic" processor which gives you correct output for each operation for 95 times out of 100. But if error occurs at any iteration for CG, it will not converge. In that case I would redo the iteration if I detect the error has occured. But question is how do I know that error has occured? $\endgroup$ – piyush_sao Nov 28 '12 at 16:22
3
$\begingroup$

What you are looking for is called fault tolerant computing. For highly sensitive routines, one traditionally used redundant computation: Perform every elementary step twice, and if the results agree, continue; otherwise repeat again and choose the result which occurred twice (often on independent machines). There are more recent approaches which have less overhead, but except for very specific types of errors, some sort of extra computation (checksums, probabilistic repeats together with checkpointing) are required to catch errors. This is especially the case for iterative linear solvers, since these are quite vulnerable (they could fail to converge or even calculate wrong solutions). For conjugate gradients, this is addressed in detail in http://www.emcl.kit.edu/preprints/emcl-preprint-2011-10.pdf. Here, the conjugate gradient (in defect correction form) is frequently restarted, and iterations where the residual has failed to decrease are discarded as corrupted by errors.

On the other hand (and since you referred to this case in your question), the error due to incorrect computation of the matrix vector product has also been investigated; the keyword is inexact conjugate gradient. See, e.g.,

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your response. My understanding of inexact krylov subspace method work when there is a "bound" on the error that can be allowed for successful convergence. The "error" in this question can be unbounded. However, such errors are infrequent enough so that if you can figure out error has occurred and backtrack an iteration, iteration will eventually converge successfully. Hence, my question is specifically to, how to figure out if the error has occurred in any iteration. $\endgroup$ – piyush_sao Nov 28 '12 at 17:16
  • $\begingroup$ Thanks. It is a hardware fault. You're coming close to understanding the problem. I have to do this in software just because of 2 reasons I can't touch the hardware and I don't really know which hardware is responsible for the fault. Moreover, doing every step twice isn't energy/time efficient. So best possible way is to have check for fault is occured, if yes then the backtrack an iteration. $\endgroup$ – piyush_sao Nov 28 '12 at 21:12
0
$\begingroup$

If you try to use the CG to seek the least square solution of $Ax=b$, where $A$ is not symmetric or even square, you will solve the normal equation $A^TAx=A^Tb$.

In this case, from my experience, it's very important to check if $A^T$ is indeed the adjoint of $A$ by using the definition of adjoint (inner product), especially when you implicitly compute $A$ and $A^T$. Every time I found my CG didn't converge, it's due to the error from $A^T$, i.e. it's not the strictly adjoint of $A$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Let's just assume that input matrix $A$ is SPD. Most of the iteration go right until one of the operation in an iteration gives incorrect value due to probabilistic nature of processor $\endgroup$ – piyush_sao Nov 28 '12 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.