Background, Questions, and Papers

A spline is a piecewise polynomial function over a subdivision P of a region O in R^n. You may assume this region O is homeomorphic to an n-ball, and the subdivision P is a simplicial or polytopal complex. The set of all splines which are continuously differentiable of order r over P are denoted by C^r(P). They form an algebra over the ring of global polynomials. Of particular interest is the finite dimension vector space C^r_d(P), which is the vector space consisting of splines F in C^r(P) of degree at most d (this means that the restriction of the spline to each polytope of P is a polynomial of degree at most d). Two primary questions in spline theory are

(1) Compute the dimension of C^r_d(P)

(2) Find bases of C^r_d(P) with good properties (i.e. locally supported - important in applications)

From the perspective of GKM theory we could add a third question:

(3) Find generators of C^r(P) as a ring with good properties ('flow-up' basis - see the third paper below)

A landmark paper of Billera, "Homology of smooth splines: generic triangulations and a conjecture of Strang," introduces techniques of homological and commutative algebra to approach question 1., which had previously been approached from an analytic perspective. Billera introduces a chain complex whose top homology is the algebra of splines. However this paper is probably not the best one for learning the topic. I suggest two papers:

(1) Billera-Rose "A Dimension Series for Multivariate Splines" introduces a matrix whose kernel is the module of splines; creating this matrix is one of key functions of the splines package. I'll call this the spline matrix.

(2) Schenck-Stillman "Local Cohomology of Bivariate Splines" introduces a modification of Billera's original complex; creating this complex is another key function of the splines package. I'll call this the spline complex.

One other paper which would be nice (and hopefully fairly easy) to incorporate into the splines package is

(3) Gilbert-Polster-Tymoczko "Generalized Splines on Arbitrary Graphs"

Suggestions for Workshop Tasks

There are two primary bodies of code (of which I am aware) for performing spline computations. Hal Schenck has a bunch of code for doing spline computations on simplicial complexes, and I have a bunch of code for doing spline computations on polyhedral complexes.

A reasonable goal for the workshop is to get an initial merger these two bodies of code into one package. Some of this should be copy-and-paste, but maybe we will decide to rewrite certain pieces of the code altogether. I suggest a number of tasks with priorities attached to them below; group members please add/comment as you wish.

Tasks for which existing code should be merged

Task 1: The Spline Matrix (High Priority)

INPUT: A polytopal complex P and a smoothness parameter (there should be an option to make this a vector) OUTPUT: The matrix whose kernel is the module of splines over P

NOTES: This function should detect whether the input is a simplicial or polytopal complex (easy). The reason for this is that the input required for a polytopal complex is more involved (one has to specify both facets and codimension one faces).

The function should automatically homogenize the problem (i.e. compute splines on the cone over P) in order to make it graded, but there should be an option to turn off this automatic homogenization.

STATUS: Done. Detects whether input is simplicial or polytopal and employs different methods. Has options to homogenize as well as a few different input options.

Task 1': Spline Module (High Priority)

INPUT: Same as for spline matrix OUTPUT: Matrix whose columns generate the module of splines

NOTES: This is (quickly) done by taking generators of kernel of the spline matrix and getting rid of superfluous entries that encode 'cofactors.'

STATUS: Done.

Task 1'': Table of Hilbert Function values

INPUT: Polytopal complex P, smoothness parameter r, two integers n<m OUTPUT: A table of Hilbert function values dim C^r_d(P) for d between n and m.

NOTES: Unsure whether this should be a separate function. Perhaps this function should also indicate when the Hilbert Polynomial of C^r(P) gives the correct value for dim C^r_d(P).

STATUS: Done.

Task 2: The Spline Complex (High Priority)

INPUT: Same as for spline matrix OUTPUT: The Schenck-Stillman chain complex R/J whose top homology is the splines over the subdivision P

NOTES: This function should also detect whether the input is a simplicial or polytopal complex. It is much simpler to code this function when the complex is simplicial. Currently the code for polytopal complexes relies on the package "Polyhedra" which, while it is extremely thorough, is very slow.

STATUS: Done. Reliance on Polyhedra eliminated, but it's still kinda slow. Function automatically detects if the input is simplicial so it can use the simplicial boundary map in this case.

Task 3: Cofactor Matrix (Medium Priority)

INPUT: Same as for spline matrix OUTPUT: Matrix whose kernel is (non-canonically isomorphic to) the module of splines which are not globally polynomial.

NOTES: This matrix is in some sense dual to the spline matrix, and often smaller (so easier to deal with).

STATUS: Pending.

Task 4: Schenck-Stillman Homology presentation (Medium Priority)

INPUT: Same as for spline matrix, except this should be a two dimensional complex OUTPUT: The presentation (see Schenck-Stillman paper above) for H_0(J)

NOTES: It should be possible to code a similar presentation for central three dimensional complexes.

STATUS: Pending.

Task 5: Code for Interacting with Peter Alfeld's Applet (Medium Priority)

I haven't looked at this yet but there is some existing code thanks to Alexei Kolesnikov at Towson.

STATUS: Pending.

Tasks without existing code

Task 6: Generalized Splines (Medium-High Priority)

INPUT: A graph G whose edges are labelled by ideals of a ring R (say a domain). OUTPUT: The ring of generalized splines on G (or a matrix whose kernel is this ring)

NOTES: Julianna Tymoczko would like to see the following things implemented over Z and Z/mZ:

1. Input of any graph accepted (user-ordered input ok)
2. Find "flow-up" splines with minimal leading entries
3. Allow user to input rings of polynomials over Z and Z/mZ
4. Compute multiplication table of basis found by M2
5. Allow user to input a basis and have M2 compute multiplication table (if flow-up basis is known, will allow upper-triangular calculation)
6. Wish list: Computation of intersection homology per Braden-MacPherson.
7. Minimal vs. minimum generating sets (for Z/mZ inputs)
8. Have user input a potential basis and M2 decides whether or not it generates the spline module
9. Given input of a generating set, find graphs whose splines are generated by that generating set

STATUS: 1. and 3. are done. M2 seems to return a upper triangular (flow-up) basis automatically.

Task 7: Super-Smoothness (Medium Priority)

INPUT: A two-dimensional (for now) polytopal complex and two smoothness parameters r (global) and s (across vertices). OUTPUT: The module of splines which are differentiable of order r across edges and differentiable of order s at vertices.

NOTES: There is considerable interest in such splines in approximation theory. This may not be too difficult to do.

STATUS: Daniel has some initial code in our GitHub file.

Task 8: Locally Supported Splines (Low Priority)

INPUT: A simplicial complex P, a smoothness parameter r, and a degree d OUTPUT: A locally supported (star-supported) basis for the splines of degree d, or an indication that no such basis exists.

NOTES: I have some bad brute-force ideas of how to do this.

STATUS: Pending.

Task 9: Nice Bases for Generalized Splines (Low Priority)

INPUT: Same as Task 6 OUTPUT: A basis for generalized splines with nice properties (like a flow-up basis)

NOTES: See Task 6

Task 10: More general subdivisions (Low priority)

INPUT: A subdivision of a two-manifold with boundary by cells whose boundaries are arbitrary algebraic curves OUTPUT: The module of piecewise polynomials over this cellular subdivision.

NOTES: This could call the generalized splines function from Task 6. There is at least some interest in such subdivisions from an applied perspective.

STATUS: Pending.

Task 11: Interact with an open-source graphics program (Low priority)

This doesn't fall under splines proper, but it would be nice to have some interaction with an open-source graphics program which draws the polytopal complexes. I have some code snippets to produce pictures in Mathematica, but not everybody has access to Mathematica.

STATUS: There has been some communication with the Visualize team (particularly Brett Barwick and Branden Stone) about getting this set up.

Any more ideas?