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 Δ be a partition (simplicial,polytopal,cellular,rectilinear, etc.) of a space n. The spline module Sr(Δ) is the module of all functions f continuously differentiable to order r such that f is a polynomial when restricted to each facet σ∈Δ. The vector space Srd(Δ) consists of splines whose polynomial restrictions have degree at most d. Its dimension is of particular interest in approximation theory (see ).

The foundations of the algebraic approach to splines (as it applies to numerical analysis) was developed by Billera and Rose in ,,. In particular, it is shown in  that dimSrd(Δ)=dimSr(cΔ)d, where Sr(cΔ)d is the vector space of splines of degree exactly d on the cone over Δ. So the statistic dimSrd(Δ) is the Hilbert function of Sr(cΔ). The functions splineMatrix and splineModule construct the matrix from  whose kernel is Sr(Δ), and the module Sr(Δ), respectively. The functions splineDimensionTable and hilbertComparisonTable display the statistic dimSrd(Δ) and compare it to the long term dimension formula, respectively.

In , Billera uses a homological approach to solve a conjecture of Strang on the dimension of the space S1d(Δ). The chain complex which he defines in  was later modified by Schenck and Stillman in ; we will call this the Billera-Schenck-Stillman chain complex. It has appeared in many papers due to its use in finding dimSrd(Δ); perhaps most notable is . In  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 Δ (relative to the boundary of Δ); 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 Sr(Δ) as a module over the polynomial ring. The method ringStructure constructs Sr(Δ) as a quotient of a polynomial ring, thus recovering its ring structure. In , Billera shows that there is a natural isomorphism between the affine Stanley-Reisner ring Ka[Δ] (see explanation in documentation for ringStructure) of a simplicial complex and the ring S0(Δ) of continuous piecewise polynomials on Δ. 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 . Moreover, the rings Sr(Δ) live inside S0(Δ) - this is of particular interest when Δ is simplicial due to Billera’s result. The method stanleyReisnerPresentation constructs Sr(Δ) as a quotient of a ring map from a polynomial ring into S0(Δ); in particular the generators of Sr(Δ) are presented in terms of generators of S0(Δ). If Δ 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  for a survey of how this relates to splines in numerical analysis; and  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 . 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 ,.

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

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

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

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\$.
• 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\$