It is well known that, when a system of linear equations is obtained from discretization of partial differential equation, the solution process can be accelerate significantly by multigrid technique. In the smoothing step of a multigrid cycle, relaxation method, such as Gauss-Seidel or Jacobi, is used. However, for relaxation method, convergence is only guaranteed for a limited class of matrices. For instance, the Gauss-Seidel Method only converges when the coefficient matrix is positive definite of diagonally dominant. My question is, if the coefficient matrix doesn't satisfy convergence requirement of relaxation method, is it still possible to perform multigrid technique? And, how to perform?


1 Answer 1


It is true that if the smoother is not convergent for high frequencies, that multigrid will not converge. Note that this is weaker than being globally convergent: a relaxation method that is unstable for low frequencies can be used with "compatible relaxation" to yield a stable smoother that is only convergent when combined with a coarse-grid correction.

General convergence statements often use Kaczmarz relaxation because it can be shown to always converge, although it is usually slower when methods such as Jacobi, Gauss-Seidel, or a polynomial smoother are convergent.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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