Periodic piecewise functions

[mkoeppe]

I propose to add periodic piecewise functions (for now, of a single real variable).

I see two main ways of doing so:

(1) By extending piecewise.

(2) By making a suitably general symbolic mod function (#9935) and having the user combine it with a piecewise function. (This is how it is done in Mathematica, it appears - http://community.wolfram.com/groups/-/m/t/156025; see also https://reference.wolfram.com/language/ref/Piecewise.html)

Some literature on piecewise:

• MARTIN VON MOHRENSCHILDT, A Normal Form for Function Rings of Piecewise Functions, J. Symbolic Computation (1998) 26, 607–619, http://www.sciencedirect.com/science/article/pii/S0747717198902292
• Jacques Carette, A canonical form for some piecewise defined functions, https://arxiv.org/pdf/cs/0702010.pdf
• Dilated floor functions having nonnegative commutator https://arxiv.org/abs/1806.00579v1

Depends on #21232

CC: @kcrisman @tscrim @sagetrac-ares @novoselt @rwst @vbraun @pjbruin @burcin @jdemeyer

Component: symbolics

Issue created by migration from https://trac.sagemath.org/ticket/21215

[rwst]

comment:1

My vote is for 1). As you seem to have a use case can you be please more detailed?

[mkoeppe]

comment:2

Replying to @rwst:

My vote is for 1).

Glad to hear; this is what I would strongly prefer too.

Right now the result of piecewise has SR as its parent. Can this be changed so that it is in a more specific parent or category?

As you seem to have a use case can you be please more detailed?

My first use case is in subadditive periodic piecewise linear functions, the periodic extensions of what can be seen here:
https://www.math.ucdavis.edu/~mkoeppe/art/infinite-group/compendium.png
They appear in integer optimization. See https://www.math.ucdavis.edu/~mkoeppe/art/infinite-group/ for more info if you're interested. I have some existing Sage code.

Generalizing slightly, I would actually like support for quasiperiodic piecewise functions -- that is, periodic plus a linear function.
Examples are ceil and floor.

There is an algebraic viewpoint using group actions on this as well, which is useful for further generalizations, in particular for piecewise functions of several variables (#20877).

[rwst]

comment:3

Replying to @mkoeppe:

Right now the result of piecewise has SR as its parent. Can this be changed so that it is in a more specific parent or category?

Possibly we can enforce Sage's convention to give back the same type as the type of the input. Meanwhile you can do ret = f(); if ret.is_numeric(): ret = ret.pyobject() because the type is already preserved.

Generalizing slightly, I would actually like support for quasiperiodic piecewise functions -- that is, periodic plus a linear function.

You are certainly aware that if they have one periodic piece they can be all expressed in terms of floor. Multiple pieces can be done by a combination of floor and piecewise I think.

[mkoeppe]

comment:4

Replying to @rwst:

Replying to @mkoeppe:

Generalizing slightly, I would actually like support for quasiperiodic piecewise functions -- that is, periodic plus a linear function.

You are certainly aware that if they have one periodic piece they can be all expressed in terms of floor. Multiple pieces can be done by a combination of floor and piecewise I think.

I guess it depends on the application whether one should consider a quasiperiodic function as a periodic+floor or as a periodic+linear. The latter is better for asymptotics. This matters for my second application, certain counting functions (http://arxiv.org/pdf/1011.6002v1.pdf page 21).
Sage should provide easy access to the corresponding direct sum decompositions of quasiperiodic functions.

[rwst]

comment:5

Replying to @mkoeppe:

Sage should provide easy access to the corresponding direct sum decompositions of quasiperiodic functions.

Can you please help a computer scientist, where for example in that paper is such a decomposition?

[rwst]

comment:6

Or did you mean decomposition into piecewise+linear. Better question: how should the piecewise quasiperiodic be represented textually? What preferred way to input them?

[mkoeppe]

comment:7

Replying to @rwst:

Or did you mean decomposition into piecewise+linear.

Take as an example the floor function.
It can be written as x - frac(x). This is the unique way of writing it as a sum of a linear function and a periodic function (whose value is 0 at 0 - a normalization to make it unique).
This kind of direct sum decomposition should be accessible by methods of a quasiperiodic.

Better question: how should the piecewise quasiperiodic be represented textually?

Good enough for me if is printed as a sum of periodic and linear.
The periodic piecewise function could print like a piecewise function, followed by "extended periodically to R".

What preferred way to input them?

No clear preference. The linear part could perhaps just be an optional argument in the constructor.
In the continuous piecewise linear case, I suppose one could have a shortcut to build quasiperiodic extensions of the given function, but this is not very important.

[rwst]

Dependencies: #21232

[mkoeppe]

comment:9

By the way, I have some existing code for piecewise linear and quasiperiodic piecewise linear that could probably be adapted. It is based on the old piecewise implementation.

• https://github.com/mkoeppe/infinite-group-relaxation-code/blob/master/functions.sage#L1183
• https://github.com/mkoeppe/infinite-group-relaxation-code/blob/master/quasi_periodic.sage

[mkoeppe]

Description changed:

--- 
+++ 
@@ -6,4 +6,6 @@
 
  (2) By making a suitably general symbolic mod function (#9935) and having the user combine it with a piecewise function. (This is how it is done in Mathematica, it appears - http://community.wolfram.com/groups/-/m/t/156025)
 
+Some literature on piecewise:
+- MARTIN VON MOHRENSCHILDT, A Normal Form for Function Rings of Piecewise Functions, J. Symbolic Computation (1998) 26, 607–619, http://www.sciencedirect.com/science/article/pii/S0747717198902292
 

[mkoeppe]

Description changed:

--- 
+++ 
@@ -8,4 +8,4 @@
 
 Some literature on piecewise:
 - MARTIN VON MOHRENSCHILDT, A Normal Form for Function Rings of Piecewise Functions, J. Symbolic Computation (1998) 26, 607–619, http://www.sciencedirect.com/science/article/pii/S0747717198902292
-
+- Jacques Carette, A canonical form for some piecewise defined functions, https://arxiv.org/pdf/cs/0702010.pdf

[mkoeppe]

Description changed:

--- 
+++ 
@@ -4,7 +4,7 @@
 
  (1) By extending `piecewise`. 
 
- (2) By making a suitably general symbolic mod function (#9935) and having the user combine it with a piecewise function. (This is how it is done in Mathematica, it appears - http://community.wolfram.com/groups/-/m/t/156025)
+ (2) By making a suitably general symbolic mod function (#9935) and having the user combine it with a piecewise function. (This is how it is done in Mathematica, it appears - http://community.wolfram.com/groups/-/m/t/156025; see also https://reference.wolfram.com/language/ref/Piecewise.html)
 
 Some literature on piecewise:
 - MARTIN VON MOHRENSCHILDT, A Normal Form for Function Rings of Piecewise Functions, J. Symbolic Computation (1998) 26, 607–619, http://www.sciencedirect.com/science/article/pii/S0747717198902292

[mkoeppe]

Description changed:

--- 
+++ 
@@ -9,3 +9,4 @@
 Some literature on piecewise:
 - MARTIN VON MOHRENSCHILDT, A Normal Form for Function Rings of Piecewise Functions, J. Symbolic Computation (1998) 26, 607–619, http://www.sciencedirect.com/science/article/pii/S0747717198902292
 - Jacques Carette, A canonical form for some piecewise defined functions, https://arxiv.org/pdf/cs/0702010.pdf
+- Dilated floor functions having nonnegative commutator https://arxiv.org/abs/1806.00579v1