Discrete calculus

History

The early history of discrete calculus is the history of calculus. Such basic ideas as the difference quotients and the Riemann sums appear implicitly or explicitly in definitions and proofs. After the limit is taken, however, they are never to be seen again. However, the Kirchhoff's voltage law (1847) can be expressed in terms of the one-dimensional discrete exterior derivative.

During the 20th century discrete calculus remains interlinked with infinitesimal calculus especially differential forms but also starts to draw from algebraic topology as both develop. The main contributions come from the following individuals:

• Henri Poincaré: triangulations (barycentric subdivision, dual triangulation), Poincaré lemma, the first proof of the general Stokes Theorem, and a lot more
• L. E. J. Brouwer: simplicial approximation theorem
• Élie Cartan, Georges de Rham: the notion of differential form, the exterior derivative as a coordinate-independent linear operator, exactness/closedness of forms
• Emmy Noether, Heinz Hopf, Leopold Vietoris, Walther Mayer: modules of chains, the boundary operator, chain complexes
• J. W. Alexander, Solomon Lefschetz, Lev Pontryagin, Andrey Kolmogorov, Norman Steenrod, Eduard Čech: the early cochain notions
• Hermann Weyl: the Kirchhoff laws stated in terms of the boundary and the coboundary operators
• W. V. D. Hodge: the Hodge star operator, the Hodge decomposition
• Samuel Eilenberg, Saunders Mac Lane, Norman Steenrod, J.H.C. Whitehead: the rigorous development of homology and cohomology theory including chain and cochain complexes, the cup product
• Hassler Whitney: cochains as integrands

The recent development of discrete calculus, starting with Whitney, has been driven by the needs of applied modeling.

Applications

Discrete calculus is used for modeling either directly or indirectly as a discretization of infinitesimal calculus in every branch of the physical sciences, actuarial science, computer science, statistics, engineering, economics, business, medicine, demography, and in other fields wherever a problem can be mathematically modeled. It allows one to go from (non-constant) rates of change to the total change or vice versa, and many times in studying a problem we know one and are trying to find the other.

Physics makes particular use of calculus; all discrete concepts in classical mechanics and electromagnetism are related through discrete calculus. The mass of an object of known density that varies incrementally, the moment of inertia of such objects, as well as the total energy of an object within a discrete conservative field can be found by the use of discrete calculus. An example of the use of discrete calculus in mechanics is Newton's second law of motion: historically stated it expressly uses the term "change of motion" which implies the difference quotient saying The change of momentum of a body is equal to the resultant force acting on the body and is in the same direction. Commonly expressed today as Force = Mass × Acceleration, it invokes discrete calculus when the change is incremental because acceleration is the difference quotient of velocity with respect to time or second difference quotient of the spatial position. Starting from knowing how an object is accelerating, we use the Riemann sums to derive its path.

Maxwell's theory of electromagnetism and Einstein's theory of general relativity have been expressed in the language of discrete calculus.

Chemistry uses calculus in determining reaction rates and radioactive decay (exponential decay).

In biology, population dynamics starts with reproduction and death rates to model population changes (population modeling).

In engineering, difference equations are used to plot a course of a spacecraft within zero gravity environments, to model heat transfer, diffusion, and wave propagation.

The discrete analogue of Green's theorem is applied in an instrument known as a planimeter, which is used to calculate the area of a flat surface on a drawing. For example, it can be used to calculate the amount of area taken up by an irregularly shaped flower bed or swimming pool when designing the layout of a piece of property. It can be used to efficiently calculate sums of rectangular domains in images, to rapidly extract features and detect object; another algorithm that could be used is the summed area table.

In the realm of medicine, calculus can be used to find the optimal branching angle of a blood vessel so as to maximize flow. From the decay laws for a particular drug's elimination from the body, it is used to derive dosing laws. In nuclear medicine, it is used to build models of radiation transport in targeted tumor therapies.

In economics, calculus allows for the determination of maximal profit by calculating both marginal cost and marginal revenue, as well as modeling of markets.

In signal processing and machine learning, discrete calculus allows for appropriate definitions of operators (e.g., convolution), level set optimization and other key functions for neural network analysis on graph structures.

Discrete calculus can be used in conjunction with other mathematical disciplines. For example, it can be used in probability theory to determine the probability of a discrete random variable from an assumed density function.

Calculus of differences and sums

Suppose a function (a ${\displaystyle 0}$-cochain) ${\displaystyle f}$ is defined at points separated by an increment ${\displaystyle \mathrm{\Delta }x=h>0}$: $${\displaystyle a,a+h,a+2h,\dots ,a+nh,\dots }$$ The difference (or the exterior derivative, or the coboundary operator) of the function is given by: $${\displaystyle (\mathrm{\Delta }f)([x,x+h])=f(x+h)-f(x).}$$ It is defined at each of the above intervals; it is a ${\displaystyle 1}$-cochain.

Suppose a ${\displaystyle 1}$-cochain ${\displaystyle g}$ is defined at each of the above intervals. Then its sum is a function (a ${\displaystyle 0}$-cochain) defined at each of the points by: $${\displaystyle \left(\sum g\right)(a+nh)=\sum _{i=1}^{n}g([a+(i-1)h,a+ih]).}$$

These are their properties:

• Constant rule: If ${\displaystyle c}$ is a constant, then $${\displaystyle \mathrm{\Delta }c=0}$$
• Linearity: if ${\displaystyle a}$ and ${\displaystyle b}$ are constants, $${\displaystyle \mathrm{\Delta }(af+bg)=a\mathrm{\Delta }f+b\mathrm{\Delta }g,\sum (af+bg)=a\sum f+b\sum g}$$
• Product rule: $${\displaystyle \mathrm{\Delta }(fg)=f\mathrm{\Delta }g+g\mathrm{\Delta }f+\mathrm{\Delta }f\mathrm{\Delta }g}$$
• Fundamental theorem of calculus I: $${\displaystyle \left(\sum \mathrm{\Delta }f\right)(a+nh)=f(a+nh)-f(a)}$$
• Fundamental theorem of calculus II: $${\displaystyle \mathrm{\Delta }\left(\sum g\right)=g}$$

The definitions are applied to graphs as follows. If a function (a ${\displaystyle 0}$-cochain) ${\displaystyle f}$ is defined at the nodes of a graph: $${\displaystyle a,b,c,\dots }$$ then its exterior derivative (or the differential) is the difference, i.e., the following function defined on the edges of the graph (${\displaystyle 1}$-cochain): $${\displaystyle \left(df\right)([a,b])=f(b)-f(a).}$$ If ${\displaystyle g}$ is a ${\displaystyle 1}$-cochain, then its integral over a sequence of edges ${\displaystyle \sigma }$ of the graph is the sum of its values over all edges of ${\displaystyle \sigma }$ ("path integral"): $${\displaystyle {\int }_{\sigma }g=\sum _{\sigma }g([a,b]).}$$

These are the properties:

• Constant rule: If ${\displaystyle c}$ is a constant, then $${\displaystyle dc=0}$$
• Linearity: if ${\displaystyle a}$ and ${\displaystyle b}$ are constants, $${\displaystyle d(af+bg)=adf+bdg,{\int }_{\sigma }(af+bg)=a{\int }_{\sigma }f+b{\int }_{\sigma }g}$$
• Product rule: $${\displaystyle d(fg)=fdg+gdf+dfdg}$$
• Fundamental theorem of calculus I: if a ${\displaystyle 1}$-chain ${\displaystyle \sigma }$ consists of the edges ${\displaystyle [a_0,a_1],[a_1,a_2],...,[a_{n-1},a_n]}$, then for any ${\displaystyle 0}$-cochain ${\displaystyle f}$ $${\displaystyle {\int }_{\sigma }df=f(a_n)-f(a_0)}$$
• Fundamental theorem of calculus II: if the graph is a tree, ${\displaystyle g}$ is a ${\displaystyle 1}$-cochain, and a function (${\displaystyle 0}$-cochain) is defined on the nodes of the graph by $${\displaystyle f(x)={\int }_{\sigma }g}$$ where a ${\displaystyle 1}$-chain ${\displaystyle \sigma }$ consists of ${\displaystyle [a_0,a_1],[a_1,a_2],...,[a_{n-1},x]}$ for some fixed ${\displaystyle a_0}$, then $${\displaystyle df=g}$$

See references.

Chains of simplices and cubes

A simplicial complex ${\displaystyle S}$ is a set of simplices that satisfies the following conditions:

1. Every face of a simplex from ${\displaystyle S}$ is also in ${\displaystyle S}$.
2. The non-empty intersection of any two simplices ${\displaystyle {\sigma }_1,{\sigma }_2\in S}$ is a face of both ${\displaystyle {\sigma }_1}$ and ${\displaystyle {\sigma }_2}$.

By definition, an orientation of a k-simplex is given by an ordering of the vertices, written as ${\displaystyle (v_0,...,v_k)}$, with the rule that two orderings define the same orientation if and only if they differ by an even permutation. Thus every simplex has exactly two orientations, and switching the order of two vertices changes an orientation to the opposite orientation. For example, choosing an orientation of a 1-simplex amounts to choosing one of the two possible directions, and choosing an orientation of a 2-simplex amounts to choosing what "counterclockwise" should mean.

Let ${\displaystyle S}$ be a simplicial complex. A simplicial k-chain is a finite formal sum $${\displaystyle \sum _{i=1}^N{c}_i{\sigma }_i,}$$ where each c_i is an integer and σ_i is an oriented k-simplex. In this definition, we declare that each oriented simplex is equal to the negative of the simplex with the opposite orientation. For example, $${\displaystyle (v_0,v_1)=-(v_1,v_0).}$$

The vector space of k-chains on ${\displaystyle S}$ is written ${\displaystyle C_k}$. It has a basis in one-to-one correspondence with the set of k-simplices in ${\displaystyle S}$. To define a basis explicitly, one has to choose an orientation of each simplex. One standard way to do this is to choose an ordering of all the vertices and give each simplex the orientation corresponding to the induced ordering of its vertices.

Let ${\displaystyle \sigma =(v_0,...,v_k)}$ be an oriented k-simplex, viewed as a basis element of ${\displaystyle C_k}$. The boundary operator $${\displaystyle {\mathrm{\partial }}_k:C_k\to C_{k-1}}$$ is the linear operator defined by: $${\displaystyle {\mathrm{\partial }}_k(\sigma )=\sum _{i=0}^k(-1{)}^i(v_0,\dots ,\widehat{v_i},\dots ,v_k),}$$ where the oriented simplex $${\displaystyle (v_0,\dots ,\widehat{v_i},\dots ,v_k)}$$ is the ${\displaystyle i}$th face of ${\displaystyle \sigma }$, obtained by deleting its ${\displaystyle i}$th vertex.

In ${\displaystyle C_k}$, elements of the subgroup $${\displaystyle Z_k=\ker {\mathrm{\partial }}_k}$$ are referred to as cycles, and the subgroup $${\displaystyle B_k=\mathrm{im}{\mathrm{\partial }}_{k+1}}$$ is said to consist of boundaries.

A direct computation shows that ${\displaystyle {\mathrm{\partial }}^2=0}$. In geometric terms, this says that the boundary of anything has no boundary. Equivalently, the vector spaces ${\displaystyle (C_k,{\mathrm{\partial }}_k)}$ form a chain complex. Another equivalent statement is that ${\displaystyle B_k}$ is contained in ${\displaystyle Z_k}$.

A cubical complex is a set composed of points, line segments, squares, cubes, and their n-dimensional counterparts. They are used analogously to simplices to form complexes. An elementary interval is a subset ${\displaystyle I\subset \mathbf{R}}$ of the form $${\displaystyle I=[\ell ,\ell +1]\text{or}I=[\ell ,\ell ]}$$ for some ${\displaystyle \ell \in \mathbf{Z}}$. An elementary cube ${\displaystyle Q}$ is the finite product of elementary intervals, i.e. $${\displaystyle Q=I_1\times I_2\times \cdots \times I_d\subset {\mathbf{R}}^d}$$ where ${\displaystyle I_1,I_2,\dots ,I_d}$ are elementary intervals. Equivalently, an elementary cube is any translate of a unit cube ${\displaystyle [0,1{]}^n}$ embedded in Euclidean space ${\displaystyle {\mathbf{R}}^d}$ (for some ${\displaystyle n,d\in \mathbf{N}\cup \{0\}}$ with ${\displaystyle n\le d}$). A set ${\displaystyle X\subseteq {\mathbf{R}}^d}$ is a cubical complex if it can be written as a union of elementary cubes (or possibly, is homeomorphic to such a set) and it contains all of the faces of all of its cubes. The boundary operator and the chain complex are defined similarly to those for simplicial complexes.

More general are cell complexes.

A chain complex ${\displaystyle (C_{\ast },{\mathrm{\partial }}_{\ast })}$ is a sequence of vector spaces ${\displaystyle \dots ,C_0,C_1,C_2,C_3,C_4,\dots }$ connected by linear operators (called boundary operators) ${\displaystyle {\mathrm{\partial }}_n:C_n\to C_{n-1}}$, such that the composition of any two consecutive maps is the zero map. Explicitly, the boundary operators satisfy ${\displaystyle {\mathrm{\partial }}_n\circ {\mathrm{\partial }}_{n+1}=0}$, or with indices suppressed, ${\displaystyle {\mathrm{\partial }}^2=0}$. The complex may be written out as follows. $${\displaystyle \cdots \stackrel{{\mathrm{\partial }}_0}{\leftarrow }{C}_0\stackrel{{\mathrm{\partial }}_1}{\leftarrow }{C}_1\stackrel{{\mathrm{\partial }}_2}{\leftarrow }{C}_2\stackrel{{\mathrm{\partial }}_3}{\leftarrow }{C}_3\stackrel{{\mathrm{\partial }}_4}{\leftarrow }{C}_4\stackrel{{\mathrm{\partial }}_5}{\leftarrow }\cdots }$$

A simplicial map is a map between simplicial complexes with the property that the images of the vertices of a simplex always span a simplex (therefore, vertices have vertices for images). A simplicial map ${\displaystyle f}$ from a simplicial complex ${\displaystyle S}$ to another ${\displaystyle T}$ is a function from the vertex set of ${\displaystyle S}$ to the vertex set of ${\displaystyle T}$ such that the image of each simplex in ${\displaystyle S}$ (viewed as a set of vertices) is a simplex in ${\displaystyle T}$. It generates a linear map, called a chain map, from the chain complex of ${\displaystyle S}$ to the chain complex of ${\displaystyle T}$. Explicitly, it is given on ${\displaystyle k}$-chains by $${\displaystyle f((v_0,\dots ,v_k))=(f(v_0),\dots ,f(v_k))}$$ if ${\displaystyle f(v_0),...,f(v_k)}$ are all distinct, and otherwise it is set equal to ${\displaystyle 0}$.

A chain map ${\displaystyle f}$ between two chain complexes ${\displaystyle (A_{\ast },d_{A,\ast })}$ and ${\displaystyle (B_{\ast },d_{B,\ast })}$ is a sequence ${\displaystyle f_{\ast }}$ of homomorphisms ${\displaystyle f_n:A_n\to B_n}$ for each ${\displaystyle n}$ that commutes with the boundary operators on the two chain complexes, so ${\displaystyle d_{B,n}\circ f_n=f_{n-1}\circ d_{A,n}}$. This is written out in the following commutative diagram:

A chain map sends cycles to cycles and boundaries to boundaries.

See references.

Discrete differential forms: cochains

For each vector space C_i in the chain complex we consider its dual space ${\displaystyle C_i^{\ast }:=\mathrm{H}\mathrm{o}\mathrm{m}(C_i,\mathbf{R}),}$ and ${\displaystyle d^i={\mathrm{\partial }}_i^{\ast }}$ is its dual linear operator $${\displaystyle d^{i-1}:C_{i-1}^{\ast }\to C_i^{\ast }.}$$ This has the effect of "reversing all the arrows" of the original complex, leaving a cochain complex $${\displaystyle \cdots \leftarrow C_{i+1}^{\ast }\stackrel{{\mathrm{\partial }}_i^{\ast }}{\leftarrow }{C}_i^{\ast }\stackrel{{\mathrm{\partial }}_{i-1}^{\ast }}{\leftarrow }{C}_{i-1}^{\ast }\leftarrow \cdots }$$

The cochain complex ${\displaystyle (C^{\ast },d^{\ast })}$ is the dual notion to a chain complex. It consists of a sequence of vector spaces ${\displaystyle ...,C_0,C_1,C_2,C_3,C_4,...}$ connected by linear operators ${\displaystyle d^n:C^n\to C^{n+1}}$ satisfying ${\displaystyle d^{n+1}\circ d^n=0}$. The cochain complex may be written out in a similar fashion to the chain complex. $${\displaystyle \cdots \stackrel{d^{-1}}{\to }{C}^0\stackrel{d^0}{\to }{C}^1\stackrel{d^1}{\to }{C}^2\stackrel{d^2}{\to }{C}^3\stackrel{d^3}{\to }{C}^4\stackrel{d^4}{\to }\cdots }$$

The index ${\displaystyle n}$ in either ${\displaystyle C_n}$ or ${\displaystyle C^n}$ is referred to as the degree (or dimension). The difference between chain and cochain complexes is that, in chain complexes, the differentials decrease dimension, whereas in cochain complexes they increase dimension.

The elements of the individual vector spaces of a (co)chain complex are called cochains. The elements in the kernel of ${\displaystyle d}$ are called cocycles (or closed elements), and the elements in the image of ${\displaystyle d}$ are called coboundaries (or exact elements). Right from the definition of the differential, all boundaries are cycles.

The Poincaré lemma states that if ${\displaystyle B}$ is an open ball in ${\displaystyle {\mathbf{R}}^n}$, any closed ${\displaystyle p}$-form ${\displaystyle \omega }$ defined on ${\displaystyle B}$ is exact, for any integer ${\displaystyle p}$ with ${\displaystyle 1\le p\le n}$.

When we refer to cochains as discrete (differential) forms, we refer to ${\displaystyle d}$ as the exterior derivative. We also use the calculus notation for the values of the forms: $${\displaystyle \omega (s)={\int }_s\omega .}$$

Stokes' theorem is a statement about the discrete differential forms on manifolds, which generalizes the fundamental theorem of discrete calculus for a partition of an interval: $${\displaystyle \sum _{i=0}^{n-1}\frac{\mathrm{\Delta }F}{\mathrm{\Delta }x}(a+ih+h/2)\mathrm{\Delta }x=F(b)-F(a).}$$

Stokes' theorem says that the sum of a form ${\displaystyle \omega }$ over the boundary of some orientable manifold ${\displaystyle \mathrm{\Omega }}$ is equal to the sum of its exterior derivative ${\displaystyle d\omega }$ over the whole of ${\displaystyle \mathrm{\Omega }}$, i.e., $${\displaystyle {\int }_{\mathrm{\Omega }}d\omega ={\int }_{\mathrm{\partial }\mathrm{\Omega }}\omega .}$$

It is worthwhile to examine the underlying principle by considering an example for ${\displaystyle d=2}$ dimensions. The essential idea can be understood by the diagram on the left, which shows that, in an oriented tiling of a manifold, the interior paths are traversed in opposite directions; their contributions to the path integral thus cancel each other pairwise. As a consequence, only the contribution from the boundary remains.

See references.

The wedge product of forms

In discrete calculus, this is a construction that creates from forms higher order forms: adjoining two cochains of degree ${\displaystyle p}$ and ${\displaystyle q}$ to form a composite cochain of degree ${\displaystyle p+q}$.

For cubical complexes, the wedge product is defined on every cube seen as a vector space of the same dimension.

For simplicial complexes, the wedge product is implemented as the cup product: if ${\displaystyle f^p}$ is a ${\displaystyle p}$-cochain and ${\displaystyle g^q}$ is a ${\displaystyle q}$-cochain, then $${\displaystyle (f^p⌣g^q)(\sigma )=f^p({\sigma }_{0,1,...,p})\cdot g^q({\sigma }_{p,p+1,...,p+q})}$$ where ${\displaystyle \sigma }$ is a ${\displaystyle (p+q)}$ -simplex and ${\displaystyle {\sigma }_S,S\subset \{0,1,...,p+q\}}$, is the simplex spanned by ${\displaystyle S}$ into the ${\displaystyle (p+q)}$-simplex whose vertices are indexed by ${\displaystyle \{0,...,p+q\}}$. So, ${\displaystyle {\sigma }_{0,1,...,p}}$ is the ${\displaystyle p}$-th front face and ${\displaystyle {\sigma }_{p,p+1,...,p+q}}$ is the ${\displaystyle q}$-th back face of ${\displaystyle \sigma }$, respectively.

The coboundary of the cup product of cochains ${\displaystyle f^p}$ and ${\displaystyle g^q}$ is given by $${\displaystyle d(f^p⌣g^q)=d{f}^p⌣g^q+(-1{)}^p(f^p⌣d{g}^q).}$$ The cup product of two cocycles is again a cocycle, and the product of a coboundary with a cocycle (in either order) is a coboundary.

The cup product operation satisfies the identity $${\displaystyle {\alpha }^p⌣{\beta }^q=(-1{)}^{pq}({\beta }^q⌣{\alpha }^p).}$$ In other words, the corresponding multiplication is graded-commutative.

See references.

However, the wedge product can be defined also on cellular complexes, whose highest-dimensional cells are general polygons. Such a wedge product was presented in A simple and complete discrete exterior calculus on general polygonal meshes. Furthermore, the authors then employ this polygonal wedge product to define discrete Lie derivative on general polygonal meshes.

Laplace operator

The Laplace operator ${\displaystyle \mathrm{\Delta }f}$ of a function ${\displaystyle f}$ at a vertex ${\displaystyle p}$, is (up to a factor) the rate at which the average value of ${\displaystyle f}$ over a cellular neighborhood of ${\displaystyle p}$ deviates from ${\displaystyle f(p)}$. The Laplace operator represents the flux density of the gradient flow of a function. For instance, the net rate at which a chemical dissolved in a fluid moves toward or away from some point is proportional to the Laplace operator of the chemical concentration at that point; expressed symbolically, the resulting equation is the diffusion equation. For these reasons, it is extensively used in the sciences for modelling various physical phenomena.

The codifferential $${\displaystyle \delta :C^k\to C^{k-1}}$$ is an operator defined on ${\displaystyle k}$-forms by: $${\displaystyle \delta =(-1{)}^{n(k-1)+1}\star d\star =(-1{)}^k{\star }^{-1}d\star ,}$$ where ${\displaystyle d}$ is the exterior derivative or differential and ${\displaystyle \star }$ is the Hodge star operator.

The codifferential is the adjoint of the exterior derivative according to Stokes' theorem: $${\displaystyle (\eta ,\delta \zeta )=(d\eta ,\zeta ).}$$ Since the differential satisfies ${\displaystyle d^2=0}$, the codifferential has the corresponding property $${\displaystyle {\delta }^2=\star d\star \star d\star =(-1{)}^{k(n-k)}\star d^2\star =0.}$$

The Laplace operator is defined by: $${\displaystyle \mathrm{\Delta }=(\delta +d{)}^2=\delta d+d\delta .}$$

See references.

Related

• Discrete element method
• Divided differences
• Finite difference coefficient
• Finite difference method
• Finite element method
• Finite volume method
• Numerical differentiation
• Numerical integration
• Numerical methods for ordinary differential equations