08-05-2012, 03:05 PM
PRINCIPLES OF MIMETIC DISCRETIZATIONS OF DIFFERENTIAL OPERATORS
PRINCIPLES OF MIMETIC DISCRETIZATIONS OF DIFFERENTIAL OPERATORS.pdf (Size: 950.49 KB / Downloads: 36)
Abstract
Compatible discretizations transform partial differential equations to discrete algebraic problems that mimic
fundamental properties of the continuum equations. We provide a common framework for mimetic discretizations using algebraic
topology to guide our analysis. The framework and all attendant discrete structures are put together by using two basic mappings
between differential forms and cochains. The key concept of the framework is a natural inner product on cochains which induces
a combinatorial Hodge theory on the cochain complex. The framework supports mutually consistent operations of differentiation
and integration, has a combinatorial Stokes theorem, and preserves the invariants of the De Rham cohomology groups. This
allows, among other things, for an elementary calculation of the kernel of the discrete Laplacian. Our framework provides an
abstraction that includes examples of compatible finite element, finite volume, and finite difference methods. We describe how
these methods result from a choice of the reconstruction operator and explain when they are equivalent. We demonstrate how
to apply the framework for compatible discretization for two scalar versions of the Hodge Laplacian.
Key words. Mimetic discretizations, compatible spatial discretizations, finite element methods, support operator methods,
algebraic topology, De Rham complex, Hodge operator, Stokes theorem
AMS(MOS) subject classifications. 65N06, 65N12, 65N30
1. Introduction
Partial differential equations (PDEs) are ubiquitous in science and engineering. A
key step in their numerical solution is the discretization that replaces the PDEs by a system of algebraic
equations. Like any other model reduction, discretization is accompanied by losses of information about the
original problem and its structure. One of the principal tasks in numerical analysis is to develop compatible,
or mimetic, algebraic models that yield stable, accurate, and physically consistent approximate solutions.
Historically, finite element (FE), finite volume (FV), and finite difference (FD) methods have achieved
compatibility by following different paths that reflected their specific approaches to discretization.
Finite element methods begin by converting the PDEs into an equivalent variational equation and then
restrict that equation to finite dimensional subspaces. Compatibility of the discrete problem is governed
by variational inf-sup conditions, which imply existence of uniformly bounded discrete solution operators;
see [6, 18, 46]. In finite volume methods the PDEs are first replaced by equivalent integral equations that
express balance of global quantities valid on all subdomains of the problem domain. The algebraic equations
are derived by sampling balance equations on a finite set of admissible subdomains (the finite volumes).
Their compatibility is achieved by using the Stokes theorem to define the discrete differential operators
[32, 42, 44, 57]. Finite difference methods approximate vector and scalar functions by discrete values on a
grid and compatibility is realized by choosing the locations of these variables on the grid [28, 33, 34, 51, 60].
In spite of their differences, compatible FE, FV, and FD methods can result in discrete problems with
remarkably similar properties. The observation that their compatibility is tantamount to having discrete
structures that mimic vector calculus identities and theorems emerged independently and at about the same
time in the FE, FV, and FD literature. For instance in [14, 15, 16, 37] Bossavit and Kotiuga demonstrated
connections between stable finite elements for the Maxwell’s equations and Whitney forms. In finite volume
methods the idea of discrete field theory guided development of covolume methods [42, 43, 44], while support
operator and mimetic methods [48, 50, 33, 34, 35, 36] combined the Stokes theorem with variational Green’s
1Computational Mathematics and Algorithms, Mail Stop 1110, Sandia National Laboratories, Albuquerque, NM 87185,
pbboche[at]sandia.gov
2Mathematical Modeling and Analysis, T-7 Mail Stop B284, Los Alamos National Laboratory, Los Alamos, NM 87545,
hyman[at]lanl.gov
1
2 P. BOCHEV AND J. HYMAN
identities to derive compatible finite differences. Algebraic topology was used to analyze mimetic discretizations
by Hyman and Scovel in [31] and more recently by Mattiussi [39], Schwalm et al. [47] and Teixeira
[53, 54]. Further research also revealed connections between some compatible methods. For instance, mimetic
FD for the Poisson equation can be obtained from mixed FE by quadrature choice [12, 13, 19]. Another
example is the equivalence between a covolume method and the classical Marker-and-Cell (MAC) scheme on
uniform grids [43] and the analysis of [39] that relates finite volume and finite elements by using the concept
of a ”spread cell”.
This research helped to evolve and clarify the notion of spatial compatibility to its present meaning of a
discrete setting that provides mutually consistent operations for discrete integration and differentiation that
obey the standard vector identities and theorems, such as the Stokes theorem. It also highlighted the role of
differential forms and algebraic topology in the design and analysis of compatible discretizations. The recent
work in [2, 8, 9, 10, 22, 29, 30, 39, 44, 47, 52, 53, 57] and the papers in this volume further affirm that these
tools are gaining wider acceptance among mathematicians and engineers. For instance, FE methods that
have traditionally relied upon nonconstructive variational [6, 18] stability criteria1 now are being derived
by topological approaches that reveal physically relevant degrees of freedom and their proper encoding. Of
particular note are the papers by Arnold et al. [4, 2] which develop stable finite elements for mixed elasticity,
and by Hiptmair [29], Demkowicz et al. [22] and Arnold et al. [3] which define canonical procedures for
building piecewise polynomial differential complexes.
The key role played by differential forms and algebraic topology in compatible discretizations is not
accidental. Exterior calculus provides powerful tools and concise formalism to encode the structure of many
PDEs and to expose their local and global invariants. For instance, integration of differential forms is an
abstraction of the measurement process, while the Stokes theorem connects differentiation and integration
to reveal global equilibrium relations. Algebraic topology, on the other hand, supplies structures that mimic
exterior calculus on finite grids and so is a natural discretization tool for differential forms. The application of
algebraic topology in modeling dates back to 1923 when H. Weyl [58] used it to describe electrical networks.
Other early works of note are Branin [17] and in particular Dodziuk [24] whose combinatorial Hodge theory
has great similarity with mixed FE on simplices. However, these papers contained few applications to
numerical analysis. The first deliberate application of algebraic topology to solve PDEs numerically is due
to Hyman and Scovel [31] who, drawing upon some of the ideas in [24], used it to develop mimetic finite
difference methods.
The present paper extends the approach originated in [31] to create a general framework for compatible
discretizations that includes FE, FV, and FD methods as special cases. We first translate scalar and vector
functions to their differential form equivalents and consider the computational grid to be an algebraic topological
complex. The grid consists of 0-cells (nodes), 1-cells (edges), 2-cells (faces), and 3-cells (volumes)
which combine to form k-chains; k = 0, 1, 2, 3. For simplicity we focus on simplicial grids; however, most of
the developments easily carry over to general polyhedral domain partitions.
All necessary discrete structures in our framework are put together by two basic operations: a reduction
map R and a reconstruction map I, such that I is a right inverse of R. We take R to be the De Rham
map that reduces differential forms to linear functionals on chains, i.e., cochains. Therefore, discrete k-forms
are encoded as k-cell quantities. For differential forms, the operators Div, Grad and Curl are generated by
the exterior derivative d. Stokes theorem states that d is dual to the boundary operator @ with respect to
1One exception in FEM was the Grid Decomposition Property (GDP), formulated by Fix et al. [26], that gives a topological
rather than variational stability condition for mixed discretizations of the Kelvin principle derived from the Hodge
decomposition. The GDP is essentially equivalent to an inf-sup condition; see Bochev and Gunzburger [7].
PRINCIPLES OF MIMETIC DISCRETIZATIONS 3
the pairing between forms and chains. To define the discrete operators we mimic this property and use the
duality between chains and cochains. Thus, the discrete Div, Grad and Curl are generated by the coboundary
which is dual to @ with respect to this pairing.
The reconstruction map I translates cochains back to differential forms and induces the natural inner
product that is central to our approach. This product gives rise to a derived adjoint , a discrete Laplacian
−4 = + and hence a combinatorial Hodge theory [25, 24]. By applying a discrete version of Hodge’s
theorem and De Rham’s theorem, we can compute the size of the kernel of this Laplacian in an elementary
way.
The global (combinatorial) and the local (metric) properties of the discrete models are determined by
R and I, respectively. The discrete derivative, induced by R, is purely combinatorial and invariant under
homeomorphisms. The adjoint is induced by the inner product and depends on the choice of I.
The present work, based on mappings between differential forms and cochains, differs from other approaches
that use differential forms and algebraic topology to provide common frameworks for compatible
discretizations. Most notably, we make the inner product on cochains the key concept of our approach because
it is sufficient to generate a combinatorial Hodge theory. As a result, distinctions between compatible
FE, FV, and FD methods arise from the choice of I and so equivalence of different models can be established
by comparing their reconstruction operators. In contrast, the primary concept in [30, 52, 54] is the discrete
? operator. Different models are distinguished by their choice of the discrete ? and its construction is the
central problem.
As an aside, we point out that developments in the FE literature focus primarily on approximation of
differential forms by piecewise polynomials of arbitrary degree [1, 3, 22] and less on the equivalence between
the discrete models. Except in the lowest-order case, such spaces include degrees of freedom that are not
cochains and result in differential operators that are not purely combinatorial. The main advantage of
cochain encoding used in this work is seen in the possibility to maintain a clear distinction between the
global and the local features in the discrete model. High-order formulations on cochains are also possible by
using an appropriate reconstruction operator [32, 57]. Generally, reconstruction stencils for I grow, which
is seen as the principal drawback of this approach. However, the number of degrees of freedom does not
increase.