Does algebraic multigrid reuse its coarse grids?

Question

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)?

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.