The conjugate gradient method suffers from an accumulation of errors as it continues. For this reason it is unwise to use it as a direct solver. My question is, would it help to recalculate the residual every 5 or so steps in an attempt to mitigate these sorts of errors even when used as an iterative solver? I've not heard of people doing this but it seems kind of obvious. If it wouldn't help, can you explain why?
2
-
$\begingroup$ Hi Cramer and welcome to scicomp! Could you give a little more detail on the problem you're solving and how you implemented the CG method? This will help us address your question more precisely. $\endgroup$– PaulNov 15, 2013 at 13:50
-
$\begingroup$ I'm working on structural optimisation and I've implemented it in a matrix free fashion using CUDA. But the question is more general, the residual is key to the method working, and it can be calculated at any time for a reasonable cost (although I can understand not calculating it every time if you don't have to). $\endgroup$– CramerNov 15, 2013 at 14:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Nobody does this. It seems like everyone who has thought about the issue has come to the conclusion that the error one incurs by not computing the residual exactly is small and that computing it every few iterations would be a waste of time.
The reason, I believe, is that even for large systems with hundreds of thousands or hundreds of millions of unknowns, we typically only do a few hundred or thousand iterations at most. This is not enough for errors to significantly accrue due to round-off.
answered Nov 15, 2013 at 15:52
-
4$\begingroup$ If you run CG for a long time (e.g. $n$ iterations), then the vectors in the CG algorithm can lose their orthogonality due to round-off errors. Sometimes the method is "restarted" after a large number of iterations to deal with this. For example,you might restart every $n$ iterations. As you've said, the CG method is most commonly used on very large scale problems and not run for even a significant fraction of $n$ iterations, and under those circumstances restarting isn't really necessary. $\endgroup$ Nov 15, 2013 at 16:20
$\begingroup$
$\endgroup$
This tutorial talks about recalculating the residual every 50 iterations to mitigate round-off errors.
