|
REVISIÓN BIBLIOGRÁFICA |
On Differential Operators in Discrete Exterior Calculus
Diego Arévalo, Camilo Rey
Faculty of Engineering and Sciences
Politécnico Grancolombiano
Cra 3E # 57-00, Bogotá DC, Colombia
Tel: (57+1) 3468800 ext. 640
[email protected]
August 17, 2010
1 Introduction
Computationally speaking, most programming in computer graphics starts with the de ni-
tion of a simplicial complex representing an object. Properties calculated on each of the
simplices forming the complex can be extended by interpolation throughout the complex to
produce complex behavior and that allow the study of topological invariants within surfaces
in a clear and orderly fashion[10, 8].
We can de ne notions like compactness, connectedness and continuity using simplicial com-
plexes and de ne new ways of studying surfaces. In particular, the classi cation theorem of
compact surfaces states that any compact surface can be thought of as either homeomorphic
to a sphere or to products of Torii (in the set topological sense). Such a result can be ob-
tained over polytopes, by rst observing the behavior of operators de ned over points, lines,
simple polygons and simple volumes called simplices.
Calculations over simplices using techniques of algebraic topology can help extend numerical
analysis providing new schemes for the solution of partial dierential equations and consti-
tute powerful tools in computer simulation that help bridge the gap between the continuum
and the discrete[9, 4, 7].
Indeed, one of the rst steps in many numerical algorithms for the solution of dieren-
tial equations start with a subdivision of the domain of the problem into simpler units, in
which the solution can be approximated[7, 14, 12]. In such methods, the geometry and
topology of the problem domain is paramount in determining if a solution exists and how
to construct algorithms to compute it. However, common methods such as Finite Element
1
Analysis and Finite Dierence methods fail to provide a coherent framework in terms of the
discretization of the problem and its original continuous presentation.
Discrete Exterior Calculus (DEC) promises to bridge the gap between continuum and dis-
crete by reconstructing a theory from the bottom up: a reconstruction of topology and
dierential structures that allows the de nition of dierential operators bringing computer
simulation into a one to one correspondence with the theory.
In this sense, a coherent introduction of DEC is present based on the works of [5, 15, 13] must
include rst the de nition of a simplicial complex: a geometric setting on which dierential
forms can be developed . Next reconstructions of operations among both the tangent and
cotangent space over a Manifold has to be developed, in order to construct a dierential
structure onto which operations can be carried out[8, 10].
Computer simulation based on Discrete Exterior Calculus depends largely on the rewriting
of basic dierential equations in terms of the operators of exterior calculus and developing
coherent discretizations ex-geometrica [2, 15]. Such rewriting of dierential equations results
in a linear system that, though large, is for most applications xed and can be solved us-
ing numerous schemes. The advantage of DEC over other simulation methods is that the
process of developing this linear system is that it becomes straight-forward [6], not requiring
conditions on the solution nor on the discretization of the geometry of the problem.
2 Simplicial Complexes
The triangle and the tetrahedron (tet for short) are the simplest geometric object in both
R2 and R3 that reduce the amount of calculations needed to solve a dierential equation
or to study the topology of a dierentiable manifold. We can generalize this notion of the
simplest geometric object to higher dimensional spaces by de ning the simplex.
De nition 1 (k-Simplex). Let k ∈ Z, a k -simplex is the convex hull of k + 1 points in Rn
(k ≤ n). That is, if x0 , . . . , xk ∈ Rn , the simplex σ k = [x0 , . . . , xk ] is de ned by
n n
(1)
αi xi : αi ∈ R, αi ≥ 0,
[x0 , . . . , xk ] = αi = 1
i=0 i=0
Brower's xed point theorem was rst proved in a triangle and then extended to more
complex geometric shapes. In the same sense, by studying the properties of dierent objects
using triangles or simplices we can nd a more cohesive argument when dealing with the
topological characterization of several objects, as simplices posses highly useful properties
that help quantify and qualify properties on a space[5]. Among them, it is remarkable that
a simplex is composed literally of smaller simplices known as faces,
De nition 2 (l-face of a Simplex). Given a k -simplex, σ k = [x0 , . . . , xk ], the simplex
spanned by any subset of {x0 , . . . , xk } of size l is called an l-face of σ k .
2
since a simplex can be regarded as a collection of smaller simplices, that start from vertices
or points (0-simplices) and escalate to tets extending in any dimension. Theoretically, such
a construct is called a complex and follows strict rules. Not every collection of points (0-
faces), edges (1-faces), triangles (2-faces),etc on constitute a simplicial complex. In order to
produce a simplicial complex, joinings between components of the complex must constitute
also faces of the complex (i.e., simplices in itself). Formally speaking,
De nition 3 (Simplicial Complex). Let Σ be a set of simplices. Σ is a simplicial complex
if:
1. Every l-face of every simplex in Σ belongs also to Σ.
2. The intersection of any two simplices in Σ is either a simplex in Σ or is empty.
2.1 Primal versus Dual Complexes
In discrete exterior calculus, the de nition of the dual complex, is paramount in de ning
operators that connect chains, conchains with discrete vector elds and dierential forms.
In the same sense that a function on a manifold is only locally de nable in terms of a
coordinate system[11], the primal and dual complexes allow the easy and correct de nition
of domains for integration and act as a weights when constructing approximations of several
operators ( and for example)[5, 2]. The dual complex is not a simplicial complex in itself.
However, it holds the same topological properties and within the literature is treated as a
simplicial complex as well, via the dualization operator and Hodge stars.
De nition 4 (Circumcenter of a Simplex). Given a simplex σk = [v0 , . . . , vk ], we de ne the
circumcenter of σk as the point c(σk ) on the embedding space of the simplex such that all
points v0 , . . . , vk of σ k lie on a sphere with center c(σ k ).
De nition 5 (Dualization Operator). dual of σk is de ned as the
Let σ k be a simplex. The
formal sum
(2)
(σ k ) = cσk σk+1 ···σn c(σ k ), . . . , c(σ n )
σk σ k+1 σn
···
where cσk σk+1 ···σn ∈ {−1, 1} is chosen to preserve the orientation. The dual of a simplex
is called a cell.
De nition 6 (Dual Complex). Given a simplicial complex K = σ 1 , . . . , σ N , the dual
complex K is de ned as
(3)
K = { (σ) : σ ∈ K}
2.2 Chains and cochains
Simplicial complexes are regarded as collections of simplices satis ying xed connectiviy
properties that act as pasting rules for composing complex shapes and, given some particular
properties manifolds. In this sense, we can regard simplicial complexes as sums of points,
lines, triangles and tets that follow speci c rules.
3
De nition 7 (p-Chain). Given a k -dimensional simplicial complex Σ, a p-chain over Σ is
a formal sum with real coe cients over all p-dimensional simplices in Σ. That is, if c is a
p-chain,
(4)
c= c(σ)σ
σ∈Σp
where Σp denotes the set of p-simplices in Σ and c(σ) ∈ R. We denote the collection of all
p-chains over Σ by Cp = Cp (Σ).
We can think of the space of p-cochains as a vector space of functions. However, since
for most applications of simplicial complexes the complexes studied are nite, we can regard
the space of cochains as a nitely generated free abelian group on functions attaching values
to vertices, edges, faces and tets. More speci cally,
Proposition 1. The set of p-chains denoted by Cp can be described as the free abelian
group generated by the forms
ω : Cp → R
(5)
σ → δσp (σ)
where
1, σ = σ p
(6)
δσp (σ) =
0, otherwise
for every σ p ∈ Σp
2.3 Boundaries
The classi ciation of surfaces using algebraic topology depends up to some point on the be-
havior of several operators, whose kernel and image characterize -among others- the number
of holes a surface has[8]. In DEC, the most basic operator that can be thought as dierential
arises from the notion of boundary within a simplicial complex.
De nition 8 (Simplicial Complex with Boundary). an n-dimensional simplicial complex Σ
is said to have a boundary if there is a collection of n-simplices within the complex that have
faces not common to any other simplex in the compound.
boundary of Σ.
The collection of all not-common faces in the complex is known as the
De nition 9 (Boundary of a simplex). Given σ p a p-dimensional simplex, the boundary of
σ p is de ned as a p − 1-chain on its p − 1-faces. That is, if ∂σ p denotes the boundary of σ p ,
(7)
∂σ p = c(σ p−1 )σ p−1
σ p−1 σ p
in particular, the coe cients yielding the p−1-chain composing the boundary of a p-chain
are given by the following theorem.
4
Theorem 1 ((Morita[10])). The boundary of a simplex σ k = [x0 , . . . , xk ] can be calculated
by means of the following identity:
k
(8)
∂k σ k = (−1)i [x0 , . . . , xi , . . . , xk ]
ˆ
i=0
where [x0 , . . . , xi , . . . , xk ] stands for the simplex obtained from removing xi from the σ k [10].
ˆ
Remark 1. The boundary operator is linear. It constitutes a linear mapping between k -
chains and k − 1-chains.
Theorem 2. Given an n-dimensional simplicial complex Σ, and 0 ≤ k < n,
(9)
∂k+1 ◦ ∂k ≡ 0
2.4 Dierential Forms
Consider Stokes' theorem on its continuous form:
(10)
dω = ω
Ω ∂Ω
Stokes theorem provides an insight into building dierential forms and discrete dieren-
tial forms. In the continuum, dierential forms are multilinear alternating tensors that be
constructed as linear combinations of a basis of the cotangent space. In the discrete case,
dierential forms can be regarded as values stored on the k -faces of a simplicial complex: a
cochain.
de Rham map of the simplicial complex.
Such an assignment is done by means of the
De nition 10 (de Rham Map). Given a triangulated manifold M , its triangulation K and
p-dierential form, we de ne its discretization via the de Rham map, R(ω, σ p ) on a p-simplex
σ p as:
(11)
R(ω, σ p ) = ω
σp
via linearity of the integral with regard to chain construction, discrete dierential forms
can be de ned as cochains over a simplicial complex.
De nition 11. The space of k -cochains (dierential forms) over a simplicial complex K is
denoted by
(12)
Ωk (K)
d
5
3 Dierential Operators in Simplicial Complexes
The de nition of dierential operators in the context of Discrete Exterior calculus depends
on weighing averages of integral values -given by the de Rham map- mimicking several
properties as in the case of dierentiable manifolds. The embedding space of the simplicial
complex cannot be then disregarded, for the volume of simplices within simplicial complexes
is determinant in the de nition of operators such as the Hodge star, sharp, and at operators.
De nition 12 (Volume of a simplex). Given a simplex σ k , we can view σ k as a subset of
Rn we denotes its volume by |σ k |. Actual volumes of simplices will play an important rol in
de ning several operators and quantities as averged values of
The geometry of dierential forms devised for dierentiable manifolds as well as many
concepts in variational calculus and mathematical physics depends on the relation and con-
joint behavior of dierential forms versus vector elds. Indeed, if vector elds can be thought
of as instances of dierentiation operations, dierential forms are worth integrating over xed
subsets. Under DEC there are two kinds of vector elds: primal and dual vector elds. A
primal vector eld is de ned as a function
(13)
σ 0 → X(σ 0 )
assigning vectors to 0-simplices. Dual vector elds assign vectors to 0-cells (n-simplices).
3.1 Exterior Derivatives
Discretely, we can use Stokes theorem to our advantage to develop a discrete version of the
exterior dierential of a dierential form. To do so, we de ne a natural pairing of forms and
simplices:
(14)
ω = σk , ω
σk
computationally speaking, the values of an integral over dierent simplices can be stored in
a data structure, so that the value of an integral over a chain can be recovered by linearity:
(15)
ω
ω= c
σ
cσ
In this sense we can de ne the exterior derivative operator over cochains -dierential forms-
as the adjoint (or transpose) of the boundary operator, provided with Stokes theorem:
(16)
ω = ∂σ, ω = σ, dω = dω
∂σ σ
exterior derivative plays an important role in the development of algebraic topology tech-
niques under simplicial complexes. Indeed, the de Rham cohomology is developed solely by
studying the properties of d and is able to classify a given simplicial complex according to
the theorem of classi cation of compact surfaces[8]. Furthermore, dierential operators such
as the gradient of a scalar function and the curl of a vector eld is de ned in terms of the
exterior derivative.
6
3.2 Hodge Stars
The notion of the dual complex allows the de nition of several dierential operators among
discrete dierential forms. In the continuum case, the Hodge star operator ∗ replaces a
dierential form α , with its dual form ∗α, so that
(17)
α ∧ ∗α
diers only by a scalar mutliple to the volume form on a given manifold. In the discrete case
instead, the Hodge star operator replaces dierential forms over the primal complex with
complementary forms in the dual complex. More speci cally, the Hodge star ∗ is a function
(n−k)
(18)
∗ : Ωk (K) → Ωd ( K)
d
and is de ned by its action on simplices satis ying the equation:
1 1
αk = ∗αk
|σ k | | σk |
σk σk
over the simplices of complex K . Equivalently,
1 1
(19)
αk , σ k = ∗αk , σ k
k| k|
|σ | σ
Following the properties of adjacency and representability of discrete dierential operators
as matrices, the Hodge star is also de nable in terms of its value on dierent forms and its
inverse is provided by the following lemma[1, 3, 5].
Lemma 1. For a k -form αk ,
∗ ∗ αk = (−1)k(n−k) αk
3.3 Flat and Sharp Operators
Exchanging dierential forms for vector elds and viceversa is needed when constructing
dierential operators. To do so, we de ne two basic operations at and sharp :
De nition 13 (Discrete Primal-Primal Flat). Given a 1-simplex σ 1 and a primal vector
eld X, we de ne the Primal-Primal-Dual Sharp operator by its action as follows:
| (σ 1 ) ∩ σ n |
(20)
X , σ1 = X( (σ n )) · σ 1
| (σ 1 )|
σ1 σn
If the at operator allows exchanging vector elds to dierential forms, the sharp operator
does the opposite. Needless to say, they are not perfect inverse of one another, but suggest
ways of deriving vector elds, necessary for the construction of other dierential operators,
such as divergence and the laplacian.
7
De nition 14 (Sharp operator). Given a simplicial complex K of dimension n, the discrete
sharp operator on primal 1-forms acts on 1-forms turning them into vector elds. If ω ∈
Ω1 (K), we de ne the action of ω on individual vertices as:
d
| (v) ∩ σ n |
(21)
ω (σ 1 )(v) = ω, σ 0 n[v,σ0 ]
ˆ
|σ n |
[v,σ 0 ]
3.4 Codierentials
The exterior derivative constitutes a linear transformation between Ωk (K) and Ωk+1 (K).
d d
When combining the exterior derivative with the Hodge Star we obtain a new operator
called the codiferential, by which the laplacian and the divergence of a vector eld can be
de ned, and that poses a derivation rule in the dual complex.
De nition 15 (Codierential). Given a primal k -form ω we de ne the codierential of ω,
δω as
(22)
δω = (−1)nk+1 ∗ d ∗ ω
References
[1] Marsden J.E. Abraham, R. and R. Tudor. Manifolds, Tensor Analysis, and Applications.
Number 75 in Applied Mathematical Sciences. Springer-Verlag, New York, NY, 2nd
edition, 1988.
[2] M. Desbrun, E. Kanso, and Y. Tong. Discrete dierential forms for computational
modeling. In SIGGRAPH '05: ACM SIGGRAPH 2005 Courses, page 7, New York,
NY, USA, 2005. ACM.
Dierential topology : an introduction. M. Dekker, New York, 1982.
[3] D.B. Gauld.
SCA
[4] E. Grinspun, A. N. Hirani, M. Desbrun, and P. Schröder. Discrete shells. In
'03: Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer
animation, pages 6267, Aire-la-Ville, Switzerland, Switzerland, 2003. Eurographics
Association.
[5] A.N. Hirani. Discrete Exterior Calculus. PhD thesis, California Institute of Technology,
Faculty of Engineering and Applied Science, 2003.
[6] Chaudhry J.H Hirani A.N, Nakshatrala K.B. Numerical method for darcy ow derived
using discrete exterior calculus, 2003.
A Computational Dierential Geometry Approach to Grid Generation
[7] V.D. Liseikin.
(Scienti c Computation). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2007.
Algebraic topology, an introduction. Springer-Verlag, New York, 1967.
[8] W.S. Massey.
8
[9] D. Metaxas and D. Terzopoulos. Dynamic deformation of solid primitives with con-
straints. In Computer Graphics, pages 309312, 1992.
Geometry of Dierential Forms. American Mathematical Society, 2001.
[10] S. Morita.
[11] J.R. Munkres. Analysis on Manifolds, volume 2 of The Advanced Book Program.
Addision-Wesley, 1991.
[12] F.K. Musgrave. Methods for Realistic Landscape Imaging. PhD thesis, Yale University
Graduate School, 1993.
[13] Robidoux N. and Steinberg S. A discrete vector calculus in tensor grids, 2003.
Eurographics
[14] Bonnani U Kmoch P. Virtual hair handle: A model for haptic hairstyling.
2008 Short Papers, 2008.
SCA '03: Proceedings
[15] Elcott S. and P. Schröder. Building your own dec at home. In
of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, pages
6873, Aire-la-Ville, Switzerland, Switzerland, 2003. Eurographics Association.
9
|
