Anil N. Hirani

Mamdouh S. Mohamed, Anil N. Hirani, Ravi Samtaney

A conservative discretization of incompressible Navier-Stokes equations is developed based on discrete exterior calculus (DEC). A distinguishing feature of our method is the use of an algebraic discretization of the interior product operator and a combinatorial discretization of the wedge product. The governing equations are first rewritten using the exterior calculus notation, replacing vector calculus differential operators by the exterior derivative, Hodge star and wedge product operators. The discretization is then carried out by substituting with the corresponding discrete operators based on the DEC framework. Numerical experiments for flows over surfaces reveal a second order accuracy for the developed scheme when using structured-triangular meshes, and first order accuracy for otherwise unstructured meshes. By construction, the method is conservative in that both mass and vorticity are conserved up to machine precision. The relative error in kinetic energy for inviscid flow test cases converges in a second order fashion with both the mesh size and the time step.

Evan VanderZee, Anil N. Hirani, Damrong Guoy et al.

Meshes composed of well-centered simplices have nice orthogonal dual meshes (the dual Voronoi diagram). This is useful for certain numerical algorithms that prefer such primal-dual mesh pairs. We prove that well-centered meshes also have optimality properties and relationships to Delaunay and minmax angle triangulations. We present an iterative algorithm that seeks to transform a given triangulation in two or three dimensions into a well-centered one by minimizing a cost function and moving the interior vertices while keeping the mesh connectivity and boundary vertices fixed. The cost function is a direct result of a new characterization of well-centeredness in arbitrary dimensions that we present. Ours is the first optimization-based heuristic for well-centeredness, and the first one that applies in both two and three dimensions. We show the results of applying our algorithm to small and large two-dimensional meshes, some with a complex boundary, and obtain a well-centered tetrahedralization of the cube. We also show numerical evidence that our algorithm preserves gradation and that it improves the maximum and minimum angles of acute triangulations created by the best known previous method.

Mamdouh S. Mohamed, Anil N. Hirani, Ravi Samtaney

Discrete exterior calculus (DEC) is a structure-preserving numerical framework for partial differential equations solution, particularly suitable for simplicial meshes. A longstanding and widespread assumption has been that DEC requires special (Delaunay) triangulations, which complicated the mesh generation process especially on curved surfaces. This paper presents numerical evidences demonstrating that this restriction is unnecessary. Convergence experiments are carried out for various physical problems using both Delaunay and non-Delaunay triangulations. Signed diagonal definition for the key DEC operator (Hodge star) is adopted. The errors converge as expected for all considered meshes and experiments. This relieves the DEC paradigm from unnecessary triangulation limitation.

John Jossey, Anil N. Hirani

We show that if a numerical method is posed as a sequence of operators acting on data and depending on a parameter, typically a measure of the size of discretization, then consistency, convergence and stability can be related by a Lax-Richtmyer type equivalence theorem -- a consistent method is convergent if and only if it is stable. We define consistency as convergence on a dense subspace and stability as discrete well-posedness. In some applications convergence is harder to prove than consistency or stability since convergence requires knowledge of the solution. An equivalence theorem can be useful in such settings. We give concrete instances of equivalence theorems for polynomial interpolation, numerical differentiation, numerical integration using quadrature rules and Monte Carlo integration.

Nathan Bell, Anil N. Hirani

This paper describes the algorithms, features and implementation of PyDEC, a Python library for computations related to the discretization of exterior calculus. PyDEC facilitates inquiry into both physical problems on manifolds as well as purely topological problems on abstract complexes. We describe efficient algorithms for constructing the operators and objects that arise in discrete exterior calculus, lowest order finite element exterior calculus and in related topological problems. Our algorithms are formulated in terms of high-level matrix operations which extend to arbitrary dimension. As a result, our implementations map well to the facilities of numerical libraries such as NumPy and SciPy. The availability of such libraries makes Python suitable for prototyping numerical methods. We demonstrate how PyDEC is used to solve physical and topological problems through several concise examples.

Alan Demlow, Anil N. Hirani

Finite element exterior calculus (FEEC) has been developed over the past decade as a framework for constructing and analyzing stable and accurate numerical methods for partial differential equations by employing differential complexes. The recent work of Arnold, Falk and Winther \cite{ArFaWi2010} includes a well-developed theory of finite element methods for Hodge Laplace problems, including a priori error estimates. In this work we focus on developing a posteriori error estimates in which the computational error is bounded by some computable functional of the discrete solution and problem data. More precisely, we prove a posteriori error estimates of residual type for Arnold-Falk-Winther mixed finite element methods for Hodge-de Rham Laplace problems. While a number of previous works consider a posteriori error estimation for Maxwell's equations and mixed formulations of the scalar Laplacian, the approach we take is distinguished by unified treatment of the various Hodge Laplace problems arising in the de Rham complex, consistent use of the language and analytical framework of differential forms, and the development of a posteriori error estimates for harmonic forms and the effects of their approximation on the resulting numerical method for the Hodge Laplacian.

Anil N. Hirani, Kaushik Kalyanaraman, Evan B. VanderZee

We define signed dual volumes at all dimensions for circumcentric dual meshes. We show that for pairwise Delaunay triangulations with mild boundary assumptions these signed dual volumes are positive. This allows the use of such Delaunay meshes for Discrete Exterior Calculus (DEC) because the discrete Hodge star operator can now be correctly defined for such meshes. This operator is crucial for DEC and is a diagonal matrix with the ratio of primal and dual volumes along the diagonal. A correct definition requires that all entries be positive. DEC is a framework for numerically solving differential equations on meshes and for geometry processing tasks and has had considerable impact in computer graphics and scientific computing. Our result allows the use of DEC with a much larger class of meshes than was previously considered possible.

Anil N. Hirani, Kaushik Kalyanaraman, Seth Watts

Given a set of alternatives to be ranked, and some pairwise comparison data, ranking is a least squares computation on a graph. The vertices are the alternatives, and the edge values comprise the comparison data. The basic idea is very simple and old: come up with values on vertices such that their differences match the given edge data. Since an exact match will usually be impossible, one settles for matching in a least squares sense. This formulation was first described by Leake in 1976 for rankingfootball teams and appears as an example in Professor Gilbert Strang's classic linear algebra textbook. If one is willing to look into the residual a little further, then the problem really comes alive, as shown effectively by the remarkable recent paper of Jiang et al. With or without this twist, the humble least squares problem on graphs has far-reaching connections with many current areas ofresearch. These connections are to theoretical computer science (spectral graph theory, and multilevel methods for graph Laplacian systems); numerical analysis (algebraic multigrid, and finite element exterior calculus); other mathematics (Hodge decomposition, and random clique complexes); and applications (arbitrage, and ranking of sports teams). Not all of these connections are explored in this paper, but many are. The underlying ideas are easy to explain, requiring only the four fundamental subspaces from elementary linear algebra. One of our aims is to explain these basic ideas and connections, to get researchers in many fields interested in this topic. Another aim is to use our numerical experiments for guidance on selecting methods and exposing the need for further development.

Evan VanderZee, Anil N. Hirani, Damrong Guoy

A completely well-centered tetrahedral mesh is a triangulation of a three dimensional domain in which every tetrahedron and every triangle contains its circumcenter in its interior. Such meshes have applications in scientific computing and other fields. We show how to triangulate simple domains using completely well-centered tetrahedra. The domains we consider here are space, infinite slab, infinite rectangular prism, cube and regular tetrahedron. We also demonstrate single tetrahedra with various combinations of the properties of dihedral acuteness, 2-well-centeredness and 3-well-centeredness.

Anil N. Hirani, Kaushik Kalyanaraman, Han Wang et al.

We describe algorithms for finding harmonic cochains, an essential ingredient for solving elliptic partial differential equations in exterior calculus. Harmonic cochains are also useful in computational topology and computer graphics. We focus on finding harmonic cochains cohomologous to a given cocycle. Amongst other things, this allows localization near topological features of interest. We derive a weighted least squares method by proving a discrete Hodge-deRham theorem on the isomorphism between the space of harmonic cochains and cohomology. The solution obtained either satisfies the Whitney form finite element exterior calculus equations or the discrete exterior calculus equations for harmonic cochains, depending on the discrete Hodge star used.

Daniel Berwick-Evans, Anil N. Hirani, Mark D. Schubel

We develop a combinatorial theory of vector bundles with connection on locally ordered simplicial complexes. This is a first step towards a discrete exterior calculus for bundle-valued forms. The basic building block is the discrete exterior covariant derivative, a forward-difference operator defined on bundle-valued cochains. Many standard objects in differential geometry (e.g., curvature, connection 1-forms, gauge transformations) can be understood via the discrete covariant derivative operator, with their defining formulas identical to the smooth setting. These discrete objects satisfy all of the expected algebraic identities, such as naturality with respect to simplicial maps, and a Bianchi identity for discrete curvature. We also show that flat discrete connections determine a cochain complex that computes twisted de Rham cohomology in a local coefficient system determined by the discrete vector bundle, with twisted Poincare duality (of densities) being one application. Finally, a coarsening operation applied to bundle-valued cochains provides a direct and concrete comparison with the recent framework for discrete bundles of Christiansen and Hu.

Anil N. Hirani, Kaushik Kalyanaraman

There are very few results on mixed finite element methods on surfaces. A theory for the study of such methods was given recently by Holst and Stern, using a variational crimes framework in the context of finite element exterior calculus. However, we are not aware of any numerical experiments where mixed finite elements derived from discretizations of exterior calculus are used for a surface domain. This short note shows results of our preliminary experiments using mixed methods for Darcy flow (hence scalar Poisson's equation in mixed form) on surfaces. We demonstrate two numerical methods. One is derived from the primal-dual Discrete Exterior Calculus and the other from lowest order finite element exterior calculus. The programming was done in the language Python, using the PyDEC package which makes the code very short and easy to read. The qualitative convergence studies seem to be promising.

Chengbin Zhu, Snorre H. Christiansen, Kaibo Hu et al.

We prove convergence and stability of the discrete exterior calculus (DEC) solutions for the Hodge-Laplace problems in two dimensions for families of meshes that are non-degenerate Delaunay and shape regular. We do this by relating the DEC solutions to the lowest order finite element exterior calculus (FEEC) solutions. A Poincaré inequality and a discrete inf-sup condition for DEC are part of this proof. We also prove that under appropriate geometric conditions on the mesh the DEC and FEEC norms are equivalent. Only one side of the norm equivalence is needed for proving stability and convergence and this allows us to relax the conditions on the meshes.

Johnny Guzmán, Anil N. Hirani, Bingyan Liu et al.

Smooth Poincaré operators are a tool used to show the vanishing of smooth de Rham cohomology on contractible manifolds and have found use in the analysis of finite element methods based on the Finite Element Exterior Calculus (FEEC). We construct analagous discrete Poincaré operators acting on cochains and Whitney forms. We provide explicit, constructive realizations of these operators under various assumptions on the underlying domain or simplicial complex. In particular, we provide simple constructions for the discrete Poincaré operators on simplicial complexes which are collapsible and those with underlying domain being star-shaped with respect to a point. We then provide more abstract constructions on simplicial complexes which are discrete contractible and domains which are Lipschitz contractible. We also modify the discrete Poincaré operator on star-shaped domains to construct a discrete Bogovski\uı operator which satisfies the requisite homotopy identity while preserving homogeneous boundary conditions. Applications arise in the construction of discrete scalar and vector potentials and in the discrete wedge product of Discrete Exterior Calculus (DEC).

Mathieu Desbrun, Anil N. Hirani, Melvin Leok et al.

We present a theory and applications of discrete exterior calculus on simplicial complexes of arbitrary finite dimension. This can be thought of as calculus on a discrete space. Our theory includes not only discrete differential forms but also discrete vector fields and the operators acting on these objects. This allows us to address the various interactions between forms and vector fields (such as Lie derivatives) which are important in applications. Previous attempts at discrete exterior calculus have addressed only differential forms. We also introduce the notion of a circumcentric dual of a simplicial complex. The importance of dual complexes in this field has been well understood, but previous researchers have used barycentric subdivision or barycentric duals. We show that the use of circumcentric duals is crucial in arriving at a theory of discrete exterior calculus that admits both vector fields and forms.