Interpolation schemes to move data between cells and nodes

Question

I work on non-graded quadtree grids where the entire grid is a hierarchy of cells specified using a quadtree data structure, where, in general, there is no constraint regarding the relative size of neighboring cells (or any cells for that matter).

My library is mainly based on finite difference schemes that sample the unknowns at each cell vertex, i.e. the "nodes". Recently, however, I have found that I need to switch to finite volume schemes (for mass conservation properties), for certain type of equations, where I sample the values at the cell centers.

However, I still like to reuse many of functions/class I've written for vertex-based values so I need to be able to interpolate data back and forth between the cells and vertices. Going from vertices to centers is easy; one could use a simple averaging operator ... let's call this $V2C$ operator. What I need now, is to construct the reverse operator, $C2V$, with the property that $V2C\:(C2V) \equiv I_{c}$ and $C2V\:(V2C) \equiv I_{v}$ where $I_c$ and $I_v$ are identity operators.

I have looked looked at this question. However the general schemes, either mentioned there or those I can think of myself, e.g. Inverse Distance Weighted (IDW) or Radial Basis Function (RBF) methods do not seem to satisfy this property (at least its not obvious to me if they do; I'm glad to be proven wrong).

What's the best way to approach this problem? I'd appreciate if anyone could refer me to possible sources? Needles to say, I need something accurate (be able to at least approximate the identity operator, $I$, with a reasonable accuracy) and fast since this has to be done at every time-step.

Answer 1

There are no such operators so that $V2C(C2V)=I$ and $C2V(V2C)=I$ simultaneously. This is already easy to see if you only have a 1d situation with 2 vertices and 1 cell. In that case, $C2V$ is a $2 \times 1$ matrix, and $V2C$ is a $1 \times 2$ matrix. It is easy to verify that you can't find entries for these two matrices that satisfy the criteria you ask. The situation does not become different if you go from a structured 1d mesh to a hierarchic 2d mesh.

More generally, the $C2V$ operation is a smoothing operation because you start with something that is piecewise constant on each cell and you find yourself vertex values that are something like averages of the surrounding cells. On the other hand, the $V2C$ operation computes for each cell a value that is something like the average of the vertex values surrounding it. In other words, $V2C$ is a smoothing operation as well! Clearly, then, $C2V(V2C)$ and $V2C(C2V)$ are operations that start and end with a cell-based field (or, in the second case, start and end with a vertex-based field) and has as output a smoothed version of the input in both cases. It is simply not possible to have an operation that reconstructs in the second step the input to an averaging operation that has been done in the first step.

Answer 2

You cannot do this as a local operation for the reasons that Wolfgang says. As you say, $V2C$ is just integration. For the "inverse" $C2V$, you can perform an $L^2$ projection. Depending on the boundary conditions, the number of vertices can be smaller or larger than the number of cells, in which case you will have to choose compatible fields. The $L^2$ projection is globally conservative (modulo boundary conditions and mesh refinement), but not locally conservative. The projection $C2V$ is also dense which means you have to solve it iteratively (it is well-conditioned and CG or Kaczmarz converge quickly).

As a practical matter, it's worth your time to modify your routines to work with cell-centered fields rather than relying on frequent projections between cells and vertices.