Discrete Exterior Calculus

DEC is a discretized version of the theory of exterior calculus, developped by Mathieu Desbrun, Anil Hirani and their coworkers at the dawn of the XXIst century. It can be seen as an "exotic Finite Element Method" focused on differential forms.

Within DEC, the concepts at the core of exterior calculus, manifolds, differential forms, and the operators acting on them (differential, hodge, musical isomorphisms...), will find discrete analogs. Let's quickly introduce the most inportant ones.

Simplicial complexes

In this discrete paradigm, nD manifolds are approximated by n-dimensional combinatorial structures, composed of simplices, called simplicial manifolds, a specific kind of simplicial complexes.

What makes a simplicial manifold?

In order to approximate a nD manifold, a simplicial complex must fullfil two additional conditions:

• All its simplices must be the face of at least one n-simplex. Such simplicial complexes are called pure simplicial complexes.

• The link (1) of any 0-simplex must be homeomorphic to a (n-1)D sphere, or at least to a (n-1)D half-sphere if the considered 0-simplex lies on the border of the complex.

  1. Link: The smallest (n-1)-simplicial complex surrounding a given simplex.

Simplicial complexes meeting these two criteria are called Simplicial Manifolds.

Why simplicial manifolds matter? Because they can be dualized, a requirement to perform discrete differential geometry in DEC.

• From a topological perspective

  A k-dimensional simplex corresponds to an oriented set of k+1 nodes, $$\sigma^{(k)} = [i_0i_1\dots i_k].$$ These nodes do not need any geometrical embedding and can be seen as indices.Any oriented subset of k'nodes, k'≤ k, forms a k'-face of the initial simplex and is, by construction, also a simplex. A simplical complex is therefore a set of simplices closed under inclusion, meaning that: (i) If a k-simplex belongs to a simplicial complex, its k'-faces (k'≤ k) also belong to it. And (ii) when considering two simplices within the same simplicial complex, their intersection is either empty or another simplex of the considered complex.

  An "abstract" definition

  When dealing only with the topological aspects of simplices and simplicial complexes, we usually refer to them as "abstract". An abstract simplicial complex is a complex that is not embedded in any geometrical space.

  Relative orientation of facetsRelative orientation of two adjacent k-simplices

  We call facets of a k-simplex its k+1 (k-1)-faces. These facets can easily be generated from the list of k+1 indices corresponding to the k-simplex by removing one index: $$\sigma_j^{(k-1)} = [i_0\dots\hat{i_j}\dots i_k] \quad \forall\: j \in [0,k],$$ where the hat above the index means it is removed.

  The relative orientation of a facet with respect to a simplex is simply defined as: $$\pi^{\sigma_j^{(k-1)}}_{\sigma^{(k)}}=\text{sign}\left(\sigma_j^{(k-1)}|\sigma^{(k)}\right) \colon = (-1)^{j},$$ $j$ being the position of the removed index in the k-simplex.

  Within a complex, two adjacent k-simplices share one common facet. Two relative orientations can therefore be computed for this facet, one relative to each k-simplex.

  By definition, we say that these two adjacent k-simplices share the same orientation if the relative orientations of their shared facet are opposite: $$\text{sign}(\sigma_1^{(k)}|\sigma_2^{(k)}) \colon = - \text{sign}(\sigma_{12}^{(k-1)}|\sigma_1^{(k)}) \cdot \text{sign}(\sigma_{12}^{(k-1)}|\sigma_2^{(k)}).$$ This property will be crutial for the definition of the algebraic structure required to emulate exterior calculus on discret settings.

• From a geometrical perspective

  A k-dimensional simplex corresponds to the convex hull of k+1 linearly independent vectors within a N-dimensional embedding space, N>k: $$\sigma^{(k)} = \Big\{ \boldsymbol{x} = \underset{i=0}{\overset{k}{\sum}} \lambda_i \boldsymbol{x}_i \:|\: \lambda_i \geq 0\: \forall i\in[0,k],\: \underset{i=0}{\overset{k}{\sum}} \lambda_i = 1 \Big\}.$$ A n-dimensional simplicial complex is therefore a piecewize linear geometric space where each k-dimensional element is homeomorph to a subset of the kD euclidean space. Grouping k-dimensional simplices together, we can therefore express a nD simplicial complex as a set of n+1 sets of simplices of the same degree (or dimension): $$\mathcal{K}^{(n)} = \Big\{ \{\sigma^{(k)}_i\}_{i\in [0,N_k]} \Big\}_{k\in [0,n]},$$ where $N_k$ stands for the number of k-simplices within the considered nD simplicial complex.

  Dualization of a simplicial complex

  Given a n-dimensional simplicial complex $\mathcal{K}$ embedded within a geometric space, one can compute the circumcenters of every n-simplex $\sigma^{(n)}\in\mathcal{K}$. Connected together, these circumcenters form k-polytopes, referred to as k-cells. By construction, to each k-simplex of the primal complex $\mathcal{K}$, corresponds such a (n-k)-cell.

  In the specific case of a simplicial manifold, the generated set of dual k-cells is closed under inclusion and consequently form a cellular complex, noted $\mathcal{K}^{\star}$, dual $\mathcal{K}$ (1).

  1. Formally, the initial simplicial manifold is referred to as the primal (simplicial) complex in contrast to the dual (cell) complex.

  The ability to define a dual complex is of prime importance for discrete differential geometry purposes: It enables the definition of the Hodge star operator and the subsequent construction of dual cochains and the codifferential operator (required to define divergence and laplacian in DEC).

• From an algebraic perspective

  We define a k-chain on a simplicial complex as a sum(1) , weighted by integers, over the k-simplices of this complex:

  1. Einstein notation used below for concision.

  $$c^{(k)} = c^i \sigma^{(k)}_i.$$

  k-chains are crutial in DEC for they represent (oriented) sub-complexes of the simplicial complex they are defined upon. For instance, a 2-chain composed by adjacent 2-simplices weighted by $\pm 1s$ corresponds to a bounded surface within the considered n-complex (n≥2).

  Within a given complex, k-chains form a module (1) , noted $C_k$ hereafter, and the coresponding set of k-simplices can be seen as its generating base. In this perspective, a k-chain can be represented as the column vector of its coefficients:

  1. Module: An abelian group over the ring of integers.

  $$c^{(k)} = \begin{bmatrix} c^1 \\ \vdots \\ c^{N_k} \end{bmatrix},$$ where $N_k$ stands for the cardinality of the k-module. DEC offers a convinent algebraic representation of any kD subset of an nD simplicial complex.

  The boundary operator

  When considering the simplices within the k-module defined on a nD simplicial complex (0<k≤n), the inclusion condition ensures that all their facets belong to the adjacent k-1-module. We define the boundary operator as the application that associates to any k-simplex the (k-1)-chain formed by its facets, weighted by their relative orientations $\pi^j = \pm 1$: $$\begin{array}{crl} \partial_k \colon & C_{k} &\to C_{k-1}\\ & \sigma &\mapsto \underset{\tau_j\prec\sigma}{\sum}\pi^j\tau_j. \end{array}$$ This operator features two fundamental algebraic properties:

  • It constitutes an homomorphism between consecutive modules for it is a addition-preserving map between them: $$\forall\: \sigma_1, \sigma_2 \in \mathcal{K}^{(k)}, m\in\mathbb{Z}, \partial\left(\sigma_1 + m \sigma_2\right) = \partial\left(\sigma_1\right) + m \partial\left(\sigma_2\right).$$

  • It is 2-nilpotent,meaning that when applied twice, it yields 0. In other words the image of $\partial_k(C^{(k)})$ lies in the kernel of $\partial_{k-1}$: $$\forall\: \sigma \in \mathcal{K}, \partial\circ\partial\left(\sigma\right) = 0.$$ This emerges from the opposite orientations of a facet between two adjacent k-simplices.

---

Cochains

• From an algebraic perspective

  In order to approximate k-forms from the continuous theory; we define k-cochains (1), on a given nD simplicial complex, as the homomorphisms between $C_k$, the module of k-chains & the additive group defined on $\mathbb{R}$. The thereby defined set of k-cochains forms an abelian group, noted $C^k$, dual to $C_k$:

  1. The terminology "chain/cochain" directly inherits from the notions of "vector/covector field"; one being a geometrical object and the other a linear application acting on it. Notation: In ambiguous contexts, we will note cochains with a "hat" (^) to distinguish them from their continuous counterparts.

  $$\forall\; m,\hat{\omega},\sigma_1,\sigma_2 \in \mathbb{Z}\times C^k\times C_k\times C_k, \quad \hat{\omega}\left(\sigma_1 + m \sigma_2\right) = \hat{\omega}\left(\sigma_1\right) + m \hat{\omega}\left(\sigma_2\right) \in \mathbb{R}.$$

  This duality between $C^k$ and $C_k$ entails that every k-cochain is solely defined by its evaluation on a basis of $C_k$, i.e. the k-simplices $\sigma\in C_k$. This evaluation corresponding to the discrete version of the natural pairing between k-forms & k-vectors, we can defined cochains as row vectors: $$\hat{\omega} = [\omega_1,\dots,\omega_{N_k}], \quad\text{s.t.}\quad \omega_i = \hat{\omega}(\sigma_i) = \langle \hat{\omega},\sigma_i\rangle = \int_{\sigma_i}\hat{\omega},$$ with $N_k$ still being the cardinality of the considered module.

  At this point, cochains might look rather abstract, but they can actually be related to their smooth counterparts in a very tangible way.

  DeRham maps

  Given a continuous nD manifold $\mathcal{M}$ & a simplicial complex $\mathcal{K}$ locally embedded into it (1), we can define a pasting homeomorphism, $\pi$, that maps any k-simplex of $\mathcal{K}$ onto a kD subset of $\mathcal{M}$:

  1. For reasons beyond the scope of this short introduction, we won't detail this point. But the idea is that we don't need the whole complex to be embedded into the manifold but just each simplex locally. This is inheritantly due to the intrinsic nature of the DEC theory.

  $$\pi\colon \mathcal{K}\succ\sigma \mapsto \Omega\subset\mathcal{M}.$$ Based on such pasting homeomorphisms, we can define a mapping between smooth k-forms on $\mathcal{M}$ and k-cochains on $\mathcal{K}$: $$\begin{array}{rl} \Lambda^k(\mathcal{M}) &\to C^k \\ \omega &\mapsto \hat{\omega} \end{array} \quad \text{s.t.} \quad \forall\sigma_i\in C_k(\mathcal{K}),\; \hat{\omega}\left(\sigma_i\right) = \omega_i = \int_{\pi(\sigma)}\omega.$$ Such maps are called DeRham maps & constitute one funding principle of DEC for we will always assume that a k-cochain corresponds to the linear interpolation of a k-form over the k-simplices of the considered complex.

• Analogy with FEMs

  At this point, DEC emerges as an "exotic Finite Element Method", where k-forms $\omega\in\Lambda^k\left(\mathcal{M}\right)$ are approximated by their projections onto spaces of piecewise-constant k-forms, called k-cochains. The basis cochains for these spaces being defined as: $$\hat{\sigma}^i\colon\sigma_j\mapsto\delta^i_j\quad \forall\; (i,j)\in [\![1,N_k]\!]^2.$$

  Warning

  The fact that we are using Kronecker deltas as basic k-forms, induces a common, but sometimes confusing, simplification widespread in the field: We often state that k-cochains can be expressed as sums over k-simplices: $\hat{\omega}^{(k)} = \sum_i\omega_i\sigma_i$. Doing so, we implicitly associate a k-simplex $\sigma_i$ with its dedicated basis k-form $\hat{\sigma}^i$. As this usage can be confusion, especially for newcomers, we will try to avoid it in the present document.

  In the smooth case, we saw that differential forms of increasing degrees, defined on the same manifold, we connected by a specific mapping called the exterior derivative. Let's now see how this concept is defined in DEC.

Discrete exterior derivative

Based on Riesz representation theorem and the natural pairing between k-forms and k-vectors, we saw that in the smooth setting, one output of the Stokes-Cartan theorem was the definition of the exterior derivative as the adjoint of the boundary operator.

The discrete Stokes-Cartan theorem

In DEC, the (discrete) exterior derivative (1), noted $d_k$, is constructed in order to fullfill the following discretized version of the Stokes-Cartan Theorem:

1. For the sake of simplicity, we will refer to the "discrete exterior derivative" as the "exterior derivative", whenever possible.

$$\begin{array}{crl} d_k \colon & C^k &\to C^{k+1} \\ & \hat{\omega} &\mapsto d\hat{\omega} \end{array} \quad\text{s.t.}\quad \forall \sigma\in C_{k+1}\quad d_k\hat{\omega}(\sigma)= \hat{\omega}(\delta\sigma) = \underset{\tau\prec\sigma}\sum \pi^\tau_\sigma\hat{\omega}(\tau),$$ where the $\tau\in C_k$ correspond to the facets of $\sigma$ and the $\pi^\tau_\sigma$ coefficients depict their relative orientation.

• From an algebraic perspective

  The algebraic structures formed by the sequence of boundary homomorphisms combined with the sequence of chain modules is called a chain complex, $\big(C_k,\partial_k\big)$. Likewise, a similar structure is formed by the sequence of discrete exterior derivatives connecting the cochain modules: The cochain complex, $\left(C^k, d_k\right)$ (1):

  1. While the chain complex is oriented toward decreasing degrees, the cochain one is oriented toward increasing degrees.

  $$\begin{align*} 0 \overset{\partial_0}{\longleftarrow} & C_0 \overset{\partial_1}{\longleftarrow} & C_1 \overset{\partial_2}{\longleftarrow} & \dots\overset{\partial_k}{\longleftarrow} & C_{n-1} \overset{\partial_n}{\longleftarrow} & C_n \\ &\updownarrow &\updownarrow\quad\quad\: & &\updownarrow\quad\quad\quad &\updownarrow \\ & C^0\overset{d_0}{\longrightarrow} & C^1 \overset{d_1}{\longrightarrow} & \dots{\longrightarrow} & C^{n-1}\overset{d_{n-1}}{\longrightarrow} & C^n \overset{d_n}{\longrightarrow}0. \end{align*}$$

  The exterior derivative is a fundamental purely topological operator in DEC, we need now to define another fundamental operator, related this time to geometry: The Hodge operator.

The Hodge star operator

Hodge duality has been introduced in the section dedicated to the continuous theory of exterior calculus. When considering a nD simplicial complex $\mathcal{K}$, the cardinalities of its k- and (n-k)-subsets do not match a priori (1). That is why, in the discrete setting, we need to compute a dual nD oriented complex, $\star\mathcal{K}$, where all (n-k)-cells are isomorphic to one k-simplex in the primal simplicial complex. Cochains can be defined on this new complex, we call them dual cochains.

1. There is no reason the number of triangles matches the number of vertices in a 2D triangular mesh for instance.

From cochains to dual cochains

The discrete Hodge star operator, noted $*_k$, performs the isomorphism from primal k-cochains to dual (n-k)-cochains and vice-versa. Based on the algebraic representation of cochains, these isomorphisms (1) can easily be computed as matrices (2).

1. As the notation suggests, we have one discrete Hodge star per topological degree of the considered complex.
2. When the dual complex is built upon the circumcenters of the primal simplices — which is the case in the Dxtr library — these matrices are by construction diagonals.

$$\begin{array}{crl} *_k \colon & C_k &\to \star C_{n-k} \\ & \hat{\omega} &\mapsto \boldsymbol{H}\cdot\hat{\omega} \end{array} \quad\text{s.t.}\quad \boldsymbol{H} = \begin{bmatrix} \frac{|\star\sigma_1|}{|\sigma_1|} & \dots & \dots \\ \dots &\ddots & \dots \\ \dots & \dots& \frac{|\star\sigma_{N_k}|}{|\sigma_{N_k}|} \\ \end{bmatrix}.$$

From the expression of the matrix $\boldsymbol{H}$ above, we see that the discrete Hodge operator is constructed so that the "duality requirement" given by $\text{eq.}(1)$ in the continuous case is verified for any couple of k-simplex/(n-k)-cell: $$\forall \sigma \in C_k,\: \frac{*_k\hat{\omega}(\star\sigma)}{|\star\sigma|} = \frac{\hat{\omega}(\sigma)}{|\sigma|},$$ where $|\star\sigma|$ and $|\sigma|$ respectively stand for the (n-k)- and k-volumes(1) of the corresponding cell/simplices.

1. The fact that by construction, the discrete Hodge star operator rely on k-volumes, makes it a geometrical operator and not a topological one, as the exterior derivative. To that end, it cannot be implemented on abstract complexes.

Warning

Within Dxtr, the discrete Hodge operator can only be computed on simplicial manifolds, for two reasons:

• As the formulae above suggest, to define $\boldsymbol{H}$, we need to compute dual (n-k)-volumes. Given a nD simplicial complex, this can only be achieved if this all k-simplices (k<n) admit (k+1)-cofaces (1).

  1. The computation of the dual (n-k)-volumes relies on the circumcenters of the (k+1)-simplices.

• If the considered simplicial complex is not pure, its dual wont' be closed under inclusion (1) and consequently its cochain-complex and the subsequence differential operators would be ill-defined.

  1. Meaning that some k-cells could miss (k-1)-faces.

Musical isomorphisms

Like the Hodge star operator, musical isomorphisms are by definition metric-based and therefore related to geometry of the considered space. That is why in Dxtr their definition is limited to SimplicialManifold instances.

Flat $(\cdot)^{\flat}$Sharp $(\cdot)^{\sharp}$

The flat operator maps vector fields to 1-cochains.

As mentionned by Anil Hirani is his PhD Thesis (c.f. link on this page), there are up to 8 definitions of the flat operator depending on the type of input vector field, the type of returned cochain and the type of interpolation used.
In Dxtr, we only implemented two of them:

• The "DPP-flat"(1), that converts a vector-valued dual 0-cochain into a primal 1-cochain, through a dual-to-primal interpolation.

  1. Names by Anil Hirani, All right reserved.

• The "DPD-flat"(1), that converts a vector-valued dual 0-cochain into a dual 1-cochain, through a primal-to-dual interpolation.

  1. Names by Anil Hirani, All right reserved.

The sharp operator maps scalar-valued 1-cochains onto discrete vector fields, i.e. vector-valued dual 0-cochains.

This mapping is performed by interpolation(1) of the 1-cochains (defined on 1-simplices, since they are primal) onto the neighboring n-simplices.

1. This idea to define the sharp operator from interpolation based on Whitney forms has been inspired by Anil Hirani's PhD manuscript; again.

Note that for now, only primal 1-cochains can be "flatten" into vector fields.

Limitations of our musical isomorphisms implementations

• Within Dxtr, discrete vector fields are only implemented as vector-valued dual 0-cochains for such vector-fields are easily defined even on curved complexes (the vectors lies within the n-simplices). We prioritized this implementation since we plan on using the library mostly on curved structures.
• In the discrete setting, due to the various projections performed, we do not have in general $(\boldsymbol{v}^{\flat})^{\sharp} = \boldsymbol{v}$.

Wedge product

Last, but not least, let's mention, upon the fundamental DEC operators, the wedge product. In the section dedicated to the continuous theory, we saw that the wedge product is a graded operator that enables the construction of high-degree differential forms from ones of smaller degrees.

Under construction!

In the current version (V 1.0.0) of the Dxtr library, it is important to note that the implemented version of the wedge product is not complete for it can only handle primal cochains. A dual version is currently under development and should be available soon.

---

These basic notions been introduced, we can now take a closer look at their instanciations within the Dxtr library Dxtr in a nutshell.