Shift Equivalence Testing of Polynomials and Symbolic Summation of Multivariate Rational Functions

Supplementary material to the paper by Shaoshi Chen, Lixin Du, and Hanqian Fang.

Maple Implementation:

• Maple code for different algorithms of shift equivalence testing: SET.mm
• For using this package, please see the illustration examples:
  • ExamplesForSET.mw

• Maple code for shift equivalence testing of polynomials over integers and symbolic summation of multivariate rational functions: RationalWZ.mm
• For using this package, please see the illustration examples:
  • ExamplesForRationalWZ.mw

Timings:

We compared the algorithm SET_ADP_expansion and SET_ADP_derivation in our paper to the algorithms by Grigoriev, Kauers et al. and Dvir et al.

The multivariate polynomials we tested are of the form
          f(x), g(x)=f(x+a)+dis(x),
where x is a vector of n variables, a is a vector over integers, f is a polynomial with degree d and t terms, and dis is a polynomial with degree d'.

The table below shows the timings (in seconds) we got in which:

• G: The algorithm by Grigoriev.
• KS: The algorithm by Kauers and Schneider.
• DOS: The algorithm by Dvir, Oliveira and Shpilka.
• ADPE: The algorithm SET_ADP_expansion.
• ADPD: The algorithm SET_ADP_derivation.