Cell-based vs face-based finite element methods

Question

Notation: Denote $T_{h} = \left\{K\right\}$ to be a face-conforming triangulation of a domain $\Omega$ such that $K_{i} \cap K_{j} = \emptyset$ for $i \neq j.$ Additionally, denote $\mathcal{V}_{h} = \left\{v \in L^{2}(\Omega) : v\big\lvert_{K} \in \mathcal{P}^{k}, K \in T_{h} \right\}$ to be a space of discontinuous test functions.

For a cell-based formulation, we loop over the faces associated to an element $K \in T_{h}$, i.e., $$ \sum_{K \in T_{h}} \int_{\partial K} \widehat{f}(u^{-},u^{+},\mathbf{n}) v = \sum_{K \in T_{h}} \left[\sum_{e \in \partial K} \int_{e} \widehat{f}(u^{-},u^{+},\mathbf{n}) v \right], \forall v \in \mathcal{V}_{h} $$

for a face-based formulation, we loop over interfaces $\Gamma$, where $\Gamma = \partial K^{-} \cap \partial K^{+}$,

$$ \langle \widehat{f}, [v] \rangle_{\Gamma} = \int_{\Gamma} \widehat{f}(u^{-},u^{+},\mathbf{n}) \cdot \left[v\right], \forall v \in \mathcal{V}_{h} $$

From the point of view of computational efficiency, is there an advantage between either formulation?

Answer 1

Yes, there is a computational efficiency difference between the two. However, it's not so straight-forward as one method is always better than the other.

For an element/cell-based approach, you have to recompute the numerical flux twice for every interior face. For a face-based approach you only have to compute this flux once.

If you're just writing a small non-parallel test code, then not having to compute the flux twice is great. There's also no problem adding the numerical flux to each associated element directly, so we don't need any significant amount of extra storage space.

When it comes to parallel codes there are several factors to consider:

1. what if two workers for different faces want to update the same cell at the same time? You can do atomic updates, but this has a performance cost.
2. If you're distributing elements over different processes or different accelerators, you might not own one or both of the elements.

One possible solution to this is to just save the computed numerical flux in a buffer and then use a second loop over elements which reads all the pre-computed fluxes instead of recomputing them. The downsides of this are:

1. You now need a buffer to store the fluxes, of the size about number of faces. If you have a lot of DOFs already this might not physically fit in memory.
2. A lot of times DG codes are memory bandwidth limited (i.e. how quickly can you read/write to memory), not calculation limited. This method required us to read/write the element solution multiple times, as well as now needing to read/write the numerical fluxes. For a relatively simple numerical flux, it might just be quicker to recompute it instead of look up a pre-computed value in a separate buffer.

There is also already the element interior flux: $$ \int_K f(u) \cdot \nabla v $$ This is fundamentally a cell-based loop. For a cell-based implementation of the numerical flux you can combine the two loops together, hopefully improving your memory cache usage.