next | previous | forward | backward | up | top | index | toc | Macaulay2 website
AlgebraicSplines :: AlgebraicSplines

AlgebraicSplines -- a package for working with splines on simplicial complexes, polytopal complexes, and graphs

Description

This package provides methods for computations with piecewise polynomial functions (splines) over polytopal complexes.

Let $\Delta$ be a partition (simplicial,polytopal,cellular,rectilinear, etc.) of a space $\RR^n$. The spline module $S^{r}(\Delta)$ is the module of all functions $f$ continuously differentiable to order $r$ such that $f$ is a polynomial when restricted to each facet $\sigma\in\Delta$. The vector space $S^r_d(\Delta)$ consists of splines whose polynomial restrictions have degree at most $d$. Its dimension is of particular interest in approximation theory (see [10]).

The foundations of the algebraic approach to splines (as it applies to numerical analysis) was developed by Billera and Rose in [1],[2],[3]. In particular, it is shown in [3] that dim$S^r_d(\Delta)=$dim$S^r(c\Delta)_d$, where $S^r(c\Delta)_d$ is the vector space of splines of degree exactly $d$ on the cone $c\Delta$ over $\Delta$. So the statistic dim$S^r_d(\Delta)$ is the Hilbert function of $S^r(c\Delta)$. The functions splineMatrix and splineModule construct the matrix from [3] whose kernel is $S^r(\Delta)$, and the module $S^r(\Delta)$, respectively. The functions splineDimensionTable and hilbertComparisonTable display the statistic dim$S^r_d(\Delta)$ and compare it to the long term dimension formula, respectively.

In [1], Billera uses a homological approach to solve a conjecture of Strang on the dimension of the space $S^1_d(\Delta)$. The chain complex which he defines in [1] was later modified by Schenck and Stillman in [10]; we will call this the Billera-Schenck-Stillman chain complex. It has appeared in many papers due to its use in finding dim$S^r_d(\Delta)$; perhaps most notable is [11]. In [10] the chain complex is also used to compute dimension formulas in the polytopal setting. The Billera-Schenck-Stillman complex is implemented by the method splineComplex. The Billera-Schenck-Stillman chain complex is a quotient of the cellular chain complex of $\Delta$ (relative to the boundary of $\Delta$); the latter is computed by cellularComplex. The kernel of this surjection is given by idealsComplex.

The functions mentioned thus far are concerned only with the structure of $S^r(\Delta)$ as a module over the polynomial ring. The method ringStructure constructs $S^r(\Delta)$ as a quotient of a polynomial ring, thus recovering its ring structure. In [2], Billera shows that there is a natural isomorphism between the affine Stanley-Reisner ring $K_a[\Delta]$ (see explanation in documentation for ringStructure) of a simplicial complex and the ring $S^0(\Delta)$ of continuous piecewise polynomials on $\Delta$. The isomorphism identifies the variable corresponding to a vertex with the Courant function for that vertex. The method courantFunctions computes these functions, and the method stanleyReisner constructs the isomorphism identified in [2]. Moreover, the rings $S^r(\Delta)$ live inside $S^0(\Delta)$ - this is of particular interest when $\Delta$ is simplicial due to Billera's result. The method stanleyReisnerPresentation constructs $S^r(\Delta)$ as a quotient of a ring map from a polynomial ring into $S^0(\Delta)$; in particular the generators of $S^r(\Delta)$ are presented in terms of generators of $S^0(\Delta)$. If $\Delta$ is simplicial these are selected to be the Courant functions.

In topology, splines arise as equivariant cohomology of spaces with a torus action via GKM theory - see [14] for a survey of how this relates to splines in numerical analysis; and [6] for the precise relationship between continuous splines and the equivariant Chow cohomology of toric varieties. From this perspective, the notion of generalized splines on graphs was introduced in [5]. The method generalizedSplines computes splines in this more flexible setting. The relationship to splines in numerical analysis is via the dual graph described by Rose in [7],[8].

Additionally, there are connections between splines and the module of multi-derivations of a hyperplane arrangement. A basic structural connection was noticed in [3]. For the braid arrangement and its sub-arrangements, the module of derivations is isomorphic to a ring of splines in a natural way (see [11] and [4]).

Methods in this package borrow from code written by Hal Schenck.

References:\break [1] Louis J. Billera. Homology of smooth splines: generic triangulations and a conjecture of Strang. Trans. Amer. Math. Soc., 310(1):325–340, 1988.\break [2] Louis J. Billera, The Algebra of Continuous Piecewise Polynomials, Adv. in Math. 76, 170-183 (1989).\break [3] Louis J. Billera and Lauren L. Rose. A dimension series for multivariate splines. Discrete Comput. Geom., 6(2):107–128, 1991.\break [4] Michael DiPasquale. Generalized Splines and Graphic Arrangements. J. Algebraic Combin. 45 (2017), no. 1, 171-189.\break [5] Simcha Gilbert, Julianna Tymoczko, and Shira Viel. Generalized splines on arbitrary graphs. Pacific J. Math. 281 (2016), no. 2, 333-364.\break [6] Sam Payne, Equivariant Chow cohomology of toric varieties, Math. Res. Lett. 13 (2006), 29-41.\break [7] Lauren Rose, Combinatorial and topological invariants of modules of piecewise polynomials, Adv. Math. 116 (1995), 34-45.\break [8] Lauren Rose, Graphs, syzygies, and multivariate splines, Discrete Comput. Geom. 32 (2004), 623-637.\break [9] T. McDonald, H. Schenck, Piecewise polynomials on polyhedral complexes, Adv. in Appl. Math. 42 (2009), 82-93.\break [10] Hal Schenck and Mike Stillman. Local cohomology of bivariate splines. J. Pure Appl. Algebra,117/118:535–548, 1997. Algorithms for algebra (Eindhoven, 1996).\break [11] Hal Schenck, A Spectral Sequence for Splines, Adv. in Appl. Math. 19, 183-199 (1997).\break [12] Schenck, Hal . Splines on the Alfeld split of a simplex and type A root systems. J. Approx. Theory 182 (2014), 1-6.\break [13] Gilbert Strang, Piecewise Polynomials and the Finite Element Method, Bull. Amer. Math. Soc. 79 (1973) 1128-1137.\break [14] Julianna Tymoczko. Splines in geometry and topology. Comput. Aided Geom. Design 45 (2016), 32-47.

Authors

Version

This documentation describes version 0.1.0 of AlgebraicSplines.

Source code

The source code from which this documentation is derived is in the file AlgebraicSplines.m2.

Exports

  • Functions and commands
    • cellularComplex -- create the cellular chain complex whose homologies are the singular homologies of the complex $\Delta$ relative to its boundary
    • courantFunctions -- returns the Courant functions of a simplicial complex
    • formsList -- list of powers of (affine) linear forms cutting out a specified list of codimension one faces.
    • generalizedSplines -- the module of generalized splines associated to a simple graph with an edge labelling
    • hilbertComparisonTable -- a table to compare the values of the hilbertFunction and hilbertPolynomial of a graded module
    • idealsComplex -- creates the Billera-Schenck-Stillman chain complex of ideals
    • postulationNumber -- computes the largest degree at which the hilbert function of the graded module M is not equal to the hilbertPolynomial
    • ringStructure -- given a sub-module of a free module (viewed as a ring with direct sum structure) which is also a sub-ring, creates a ring map whose image is the module with its ring structure
    • splineComplex -- creates the Billera-Schenck-Stillman chain complex
    • splineDimensionTable -- a table with the dimensions of the graded pieces of a graded module
    • splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$
    • splineModule -- compute the module of all splines on partition of a space
    • stanleyReisner -- Creates a ring map whose image is the ring of piecewise continuous polynomials on $\Delta$. If $\Delta$ is simplicial, the Stanley Reisner ring of $\Delta$ is returned.
    • stanleyReisnerPresentation -- creates a ring map whose image is the sub-ring of $C^0(\Delta)$ generated by $C^r(\Delta)$. If $\Delta$ is simplicial, $C^0(\Delta)$ is the Stanley Reisner ring of $\Delta$.
  • Methods
    • "cellularComplex(List)" -- see cellularComplex -- create the cellular chain complex whose homologies are the singular homologies of the complex $\Delta$ relative to its boundary
    • "cellularComplex(List,List)" -- see cellularComplex -- create the cellular chain complex whose homologies are the singular homologies of the complex $\Delta$ relative to its boundary
    • "courantFunctions(List,List)" -- see courantFunctions -- returns the Courant functions of a simplicial complex
    • "formsList(List,List,ZZ)" -- see formsList -- list of powers of (affine) linear forms cutting out a specified list of codimension one faces.
    • "generalizedSplines(List,List)" -- see generalizedSplines -- the module of generalized splines associated to a simple graph with an edge labelling
    • "hilbertComparisonTable(ZZ,ZZ,Module)" -- see hilbertComparisonTable -- a table to compare the values of the hilbertFunction and hilbertPolynomial of a graded module
    • "idealsComplex(List,List,ZZ)" -- see idealsComplex -- creates the Billera-Schenck-Stillman chain complex of ideals
    • "postulationNumber(Module)" -- see postulationNumber -- computes the largest degree at which the hilbert function of the graded module M is not equal to the hilbertPolynomial
    • "ringStructure(Module)" -- see ringStructure -- given a sub-module of a free module (viewed as a ring with direct sum structure) which is also a sub-ring, creates a ring map whose image is the module with its ring structure
    • "splineComplex(List,List,ZZ)" -- see splineComplex -- creates the Billera-Schenck-Stillman chain complex
    • "splineDimensionTable(ZZ,ZZ,List,ZZ)" -- see splineDimensionTable -- a table with the dimensions of the graded pieces of a graded module
    • "splineDimensionTable(ZZ,ZZ,Module)" -- see splineDimensionTable -- a table with the dimensions of the graded pieces of a graded module
    • "splineMatrix(List,List,List,ZZ)" -- see splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$
    • "splineMatrix(List,List,ZZ)" -- see splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$
    • "splineMatrix(List,ZZ)" -- see splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$
    • "splineModule(List,List,List,ZZ)" -- see splineModule -- compute the module of all splines on partition of a space
    • "splineModule(List,List,ZZ)" -- see splineModule -- compute the module of all splines on partition of a space
    • "stanleyReisner(List,List)" -- see stanleyReisner -- Creates a ring map whose image is the ring of piecewise continuous polynomials on $\Delta$. If $\Delta$ is simplicial, the Stanley Reisner ring of $\Delta$ is returned.
    • "stanleyReisnerPresentation(List,List,ZZ)" -- see stanleyReisnerPresentation -- creates a ring map whose image is the sub-ring of $C^0(\Delta)$ generated by $C^r(\Delta)$. If $\Delta$ is simplicial, $C^0(\Delta)$ is the Stanley Reisner ring of $\Delta$.
  • Symbols
    • "RingType" -- see generalizedSplines -- the module of generalized splines associated to a simple graph with an edge labelling
    • "GenVar" -- see ringStructure -- given a sub-module of a free module (viewed as a ring with direct sum structure) which is also a sub-ring, creates a ring map whose image is the module with its ring structure
    • "IdempotentVar" -- see ringStructure -- given a sub-module of a free module (viewed as a ring with direct sum structure) which is also a sub-ring, creates a ring map whose image is the module with its ring structure
    • "Trim" -- see ringStructure -- given a sub-module of a free module (viewed as a ring with direct sum structure) which is also a sub-ring, creates a ring map whose image is the module with its ring structure
    • "VariableGens" -- see ringStructure -- given a sub-module of a free module (viewed as a ring with direct sum structure) which is also a sub-ring, creates a ring map whose image is the module with its ring structure
    • "BaseRing" -- see splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$
    • "ByFacets" -- see splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$
    • "ByLinearForms" -- see splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$
    • "Homogenize" -- see splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$
    • "InputType" -- see splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$
    • "VariableName" -- see splineMatrix -- compute matrix whose kernel is the module of $C^r$ splines on $\Delta$

For the programmer

The object AlgebraicSplines is a package.