Symbolic Summation of Multivariate Rational Functions via Shift Equivalence Testing PDF

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 implemented the ADC algorithm in two different ways. The function SET_ADC_expansion constructs the a-degree cover by expanding the 2n-variable polynomial p(x+a)-q(x) completely, while the function SET_ADC_derivation finds the cover via partial derivative.

We compared the algorithm SET_ADC_expansion and SET_ADC_derivation 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.
• ADCE: The algorithm SET_ADC_expansion.
• ADCD: The algorithm SET_ADC_derivation.