Admittedly, I'm new to the subject, so this is probably a really simple question.

Let's assume I want to solve the (large sparse) linear system Ax = b multiple times with algebraic multigrid and b changes (slightly) every time. As I understand it, AMG selects its coarse grid based on the smoothness of the error, which depends on b, so this would have to be done anew every time b changes, although A stays the same.

Is this correct? And isn't this a huge bargain compared to geometric multigrid (when applicable)?


1 Answer 1


In algebraic multigrid there are usually two steps:

1) Setup: Here we compute the $A$ matrices and interpolation matrices ($W$, $W'$) at each grid level. This is based on computing c-points and f-points which are entirely derived from information from the matrix $A$ at each level. We do not need the right hand side $b$ vector to complete this setup step.

2) Solve: Once we have our A matrices and interpolation matrices at each level we perform the recursive multigrid algorithm:

  • do $n_{1}$ smoothing steps on $Ax=b$
  • compute residual $r=b-Ax=Ae$
  • compute $W'r$
  • set $e = 0$
  • recursively solve $A_{c}e_{c}=W'r$ ($A_{c}$ and $e_{c}$ are the coarse level $A$ matrix and error vector)
  • correct $x = x + We_{c}$
  • do $n_{2}$ smoothing steps on $Ax=b$

In summary the setup step can be done once for many different choices of right hand side vector $b$ because finding the $A$ matrices and interpolation matrices ($W$, $W'$) at each level does not involve the right hand side vector, but rather only information from the $A$ matrix.


Your Answer

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

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