Restriction in (geometric) multigrid for vectors of non-even length

Question

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.

Answer 1

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.