This article 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.

Two fundamental objects in knot theory are the minimal genus surface and the least area surface bounded by a knot in a 3-dimensional manifold. When the knot is embedded in a general 3-manifold, the problems of finding these surfaces were shown to be NP-complete and NP-hard respectively. However, there is evidence that the special case when the ambient manifold is R^3, or more generally when the second homology is trivial, should be considerably more tractable. Indeed, we show here that a natural discrete version of the least area surface can be found in polynomial time. The precise setting is that the knot is a 1-dimensional subcomplex of a triangulation of the ambient 3-manifold. The main tool we use is a linear programming formulation of the Optimal Bounding Chain Problem (OBCP), where one is required to find the smallest norm chain with a given boundary. While the decision variant of OBCP is NP-complete in general, we give conditions under which it can be solved in polynomial time. We then show that the least area surface can be constructed from the optimal bounding chain using a standard desingularization argument from 3-dimensional topology.

Given a simplicial complex with weights on its simplices, and a nontrivial cycle on it, we are interested in finding the cycle with minimal weight which is homologous to the given one. Assuming that the homology is defined with integer ($\mathbb{Z}$) coefficients, we show the following (Theorem 5.2): For a finite simplicial complex K of dimension greater than p, the boundary matrix $[\partial_{p+1}]$ is totally unimodular if and only if $H_p(L, L_0)$ is torsion-free for all pure subcomplexes $L_0, L$ in K of dimensions p and $p+1$, respectively, where $L_0 \subsetL$. Because of the total unimodularity of the boundary matrix, we can solve the optimization problem, which is inherently an integer programming problem, as a linear program and obtain an integer solution. Thus, the problem of finding optimal cycles in a given homology class can be solved in polynomial time. This result is surprising in the backdrop of a recent result which says that the problem is NP-hard under $\mathbb{Z}_2$ coefficients which, being a field, is in general easier to deal with. Our result implies, among other things, that one can compute in polynomial time an optimal $(d-1)$-cycle in a given homology class for any triangulation of an orientable compact d-manifold or for any finite simplicial complex embedded in $\mathbb{R}^d$. Our optimization approach can also be used for various related problems, such as finding an optimal chain homologous to a given one when these are not cycles. Our result can also be viewed as providing a topological characterization of total unimodularity.

Given a simplicial complex with weights on its simplices, and a nontrivial cycle on it, we are interested in finding the cycle with minimal weight which is homologous to the given one. Assuming that the homology is defined with integer (Z) coefficients, we show the following: For a finite simplicial complex K of dimension greater than p, the boundary matrix [partialp+1] is totally unimodular if and only if Hp(L, L0) is torsion-free, for all pure subcomplexes L0, L in K of dimensions p and p+1 respectively, where L0 ⊂ L.

While 2D and 3D vector fields are ubiquitous in computational sciences, their use in graphics is often limited to regular grids, where computations are easily handled through finite-difference methods. In this paper, we propose a set of simple and accurate tools for the analysis of 3D discrete vector fields on arbitrary tetrahedral grids. We introduce a variational, multiscale decomposition of vector fields into three intuitive components: a divergence-free part, a curl-free part, and a harmonic part. We show how our discrete approach matches its well-known smooth analog, called the Helmotz-Hodge decomposition, and that the resulting computational tools have very intuitive geometric interpretation. We demonstrate the versatility of these tools in a series of applications, ranging from data visualization to fluid and deformable object simulation.

This paper describes a new fast, iterative algorithm for interactive image noise removal. Given the locations of noisy pixels and a prototype image, the noisy pixels are to be restored in a natural way. Most existing image noise removal algorithms use either frequency domain information (e.g. low pass filtering) or spatial domain information (e.g median filtering or stochastic texture generation). However, for good noise removal, both spatial and frequency information must be used. The existing algorithms that do combine the two domains (e.g. Gerchberg-Papoulis and related algorithms) place the limitation that the image be band-limited and the band limits be known. Also, some of these may not work well when the noisy pixels are contiguous and numerous. Our algorithm combines the spatial and frequency domain information by using projection onto convex sets (POCS). But unlike previous methods it does not need to know image band limits and does not require the image to be band-limited. Results given here show noise removal from images with texture and prominent lines. The detailed textures as well as the pixels representing prominent lines are created by our algorithm for the noise pixels. The algorithm is fast, the cost being a few iterations (usually under 10), each requiring an FFT, IFFT and copying of a small neighborhood of the noise.

Scratches on old films must be removed since these are more noticeable on higher definition and digital televisions. Wires that suspend actors or cars must be carefully erased during post production of special effects shots. Both of these are time consuming tasks but can be addressed by the following image restoration process: given the locations of noisy pixels to be replaced and a prototype image, restore those noisy pixels in a natural way. We call it image noise removal and this paper describes its fast iterative algorithm. Most existing algorithms for removing image noise use either frequency domain information (e.g low pass filtering) or spatial domain information (e.g median filtering or stochastic texture generation). The few that do combine the two domains place the limitation that the image be band limited and the band limits be known. Our algorithm works in both spatial and frequency domains without placing the limitations about band limits, making it possible to fully exploit advantages from each domain. While global features and large textures are captured in frequency domain, local continuity and sharpness are maintained in spatial domain. With a judicious choice of operations and domains in which they work, our dual-domain approach can reconstruct many contiguous noisy pixels in areas with large patterns while maintaining continuity of features such as lines. In addition, the image intensity does not have to be uniform. These are significant advantages over existing algorithms. Our algorithm is based on a general framework of projection onto convex sets (POCS). Any image analysis technique that can be described as a closed convex set can be cleanly plugged into the iteration loop of our algorithm. This is another important advantage of our algorithm.