I have a Poisson equation with wildly varying material parameters (1 .. 1000), wildly varying element sizes (5 nm .. 100 um) and some quite anisotropic (tetrahedral) elements (100 nm x 100 um). I use (a C++ port of) Dan Spielman's approxChol as a preconditioner for a preconditioned CG method. It converges pretty fast (around 20 iterations), but the convergence test of the preconditioned CG method sometimes stops the iteration much too early, especially if I start the iteration with a "good" initial guess of the solution. The termination criterion is that the L2 norm of the residual is smaller than 1e-6 times the L2 norm of the right hand side. I looked around at some implementations of CG and some documents describing CG, and they all seem to use this as a termination criterion.

I wonder whether my trouble with the convergence test is caused by the bad condition of my matrix, and whether it would be a good idea to use the preconditioned residual instead as termination criterion. But why does nobody else does this? Perhaps because one would have to additionally compute $M^{-1}b$ in order to evaluate $b^TM^{-1}b$? Could one use $x_0^Tx_0 + r_0^TM^{-1}r_0$ instead ($r_0^TM^{-1}r_0$ gets computed anyway) to avoid that additional cost? (But the additional cost seems small anyway, so ...)

  • 1
    $\begingroup$ Checking the un-preconditioned residual norm against the norm of the original un-preconditioned RHS results in early termination? I would expect this behavior to happen for the preconditioned problem rather than what you've described. $\endgroup$ – sssssssssssss Aug 6 '19 at 11:04
  • $\begingroup$ @sssssssssssss Good point. I see now why I ended up with huge components in the right hand side at places where the cell size and the material constant are both huge: A strategy which normally successfully leads to small material constants especially in the region where cell sizes are big "intentionally" fails for the case that I am currently looking at. (And since 1000*1000 ~ 1e6, it is no surprise that the un-preconditioned residual based termination criterion now fails completely.) But still, what could go wrong if using the preconditioned residual as termination criterion? $\endgroup$ – Thomas Klimpel Aug 6 '19 at 19:03
  • $\begingroup$ Could you post plots of $\|b - Ax\|$ vs. $\|b\|$ ? might be interesting. Also, see Matrix balancing $\endgroup$ – denis Apr 18 at 10:33

Your Answer

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

Browse other questions tagged or ask your own question.