2
$\begingroup$

Naive restriction operators in geometric multigrid that I have seen are typically implemented as a convolution and a subsequent averaging of every two entries in a vector $v^h$. For example:

$$\tilde{v}^{h} = g*v^{h}, \quad v^{2h}_{1+i} = \frac{\tilde{v}^h_{2i+1}+\tilde{v}^h_{2i+2}}{2}, \, i\in\{0,\ldots,N/2-1\}$$

What is a good way to perform the restriction if $N$ happens to be odd? The only thing I could think of is extending the signal through reflecting boundary conditions, e.g. adding an entry $v^{h}_{N+1} = v^{h}_N$ or $v^{h}_0 = v^{h}_1$. What bothers me is that either of those do not treat the vector symmetrically. Is there a standard way to deal with this? And generally speaking, how are grids that are not of a size that is a power of 2 handled?

Edit: I guess I could also extend $v^{h}$ to a continuous function through interpolation and then sample that at $N/2$ equidistant points.

$\endgroup$
3
  • $\begingroup$ This is the wrong perspective. You should be thinking about what restriction means geometrically: You are moving from a finer grid to a coarser grid. For each coarse grid node, you have to identify which fine grid nodes you want to average. If you know how that should happen geometrically, you will know what that means for the indices in the vector. $\endgroup$ Dec 1, 2021 at 2:36
  • $\begingroup$ @WolfgangBangerth The geometric part is me rediscretizing the PDE at each level in order to get a matrix free application of $A^{2^kh}$ instead of using Petrov-Galerkin: $A^{2h}=I^{2h}_hA_hI^h_{2h}$, and an appropriate geometric treatment of the boundary conditions (i.e. $A^{2h}$ is not produced through the restriction operator). I require the restriction operator to fulfill $I^h_{2h} = c(I^{2h}_h)^T$ and to be of high enough order/smooth enough to match my PDE and thus not introduce much aliasing. Geometrically I am smoothing and downsampling the residual. Note that this is FDM and not FEM. $\endgroup$
    – lightxbulb
    Dec 1, 2021 at 6:58
  • $\begingroup$ That's fine, but you still have a coarse mesh and a fine mesh. Use these to figure out how indices match. $\endgroup$ Dec 1, 2021 at 15:28

1 Answer 1

3
$\begingroup$

I have found what I was looking for in Wesseling's book: An introduction to multigrid methods. For vectors with an even number of elements, a cell-centered approach is employed where coarser grid points are given as: $p^{2h}_i = \frac{p^h_{2i} + p^h_{2i+1}}{2}, \, i=1,\ldots, N/2$. For vectors with an odd number of elements, a vertex-centered approach is employed where coarser grid points correspond to every other point on the fine grid: $p^{2h}_i = p^h_{2i-1}, \, i=1,\ldots,\lceil N/2\rceil$. The standard linear interpolation kernels used are:

$$K_{odd} = \begin{bmatrix}\frac{1}{2} & 1 & \frac{1}{2} \end{bmatrix}, \quad K_{even} = \begin{bmatrix}\frac{1}{4} & \frac{3}{4} & \frac{3}{4} & \frac{1}{4}\end{bmatrix}$$

It is never mentioned in the book, but one option to construct a hierarchy of transfer operators would be to choose one or the other depending on whether the vector at the current scale is even or odd.

One way to construct $D$-dimensional analogues is to take $D$ tensor products of the kernel with itself. The restriction operator uses the same kernel but with a scaling factor $2^{-D}$. The elements of $K_{odd}$ are derived as the sum of the coefficients of the Lagrange basis polynomials linearly interpolating: $p^{2h}_{i-1}, \,p^{2h}_i$ with samples at $p^h_{2(i-1)+1}, \, p^h_{2i}$, and $p^{2h}_i, \,p^{2h}_{i+1}$ with samples at $p^h_{2i}, \, p^h_{2(i+1)-1}$. Equivalently they are the samples of the interpolation synthesis function (in this case the tent function $1-|x|$) samples at $-\frac{1}{2},\, 0, \, \frac{1}{2}$. A similar derivation holds for $K_{even}$: we have the linear piece between $p^{2h}_{i-1}, \, p^{2h}_{i}$ with samples at $p^h_{2(i-1)}, \, p^h_{2(i-1)+1}$, and the linear piece betwenn $p^{2h}_i, \, p^{2h}_{2i}$ with samples at $p^h_{2i},\, p^h_{2i+1}$. Equivalently, the linear interpolation synthesis function $1-|x|$ may be sampled at $-\frac{3}{4}, -\frac{1}{4}, \frac{1}{4}, \frac{3}{4}$.

I have a more detailed derivation here: Constructing $C^{k−2} and $C^{k−1} splines on a regular grid through convolution.

$\endgroup$

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.