Hermite Reduction and Creative Telescoping for Hyperexponential Functions

Supplementary material to the paper by Alin Bostan, Shaoshi Chen, Frédéric Chyzak, Ziming Li,and Guoce Xin.

Maple Implementation:

Please download the following files:

Maple code: HermiteCT.mm
For using this package, please see the illustration examples:

Timings:

We compared the algorithm HermiteTelescoping in our paper to the Maple built-in implementation of the telescoping algorithm by Almkvist and Zeilberger.

The hyperexponential functions we tested are of the form

Hyperexponential function

where m is an positive integer and p, q, a, b, u and v are all irreducible polynomials in x and y over intergers. For simplicity, we choose

degree

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

ZT: The Maple built-in function Zeilberger in package DEtools.
HT: The algorithm HermiteTelescoping with computing telescopers only.
HTC: The algorithm HermiteTelescoping with computing both telescopers and certificates.
order: The order of computed minimal telescoper.
Telescoper: The computed minimal telescoper.
OOM: Maple runs out of memory.

Timings were taken on a Mac OS X machine with 4Gb RAM and 3.06 GHz Core 2 Duo processor.

Example	( λ, μ, ν, m )	ZT	HT	HTC	order	Telescoper
example1	(2, 0, 2, 1)	2.16	2.01	3.80	5	tele1
example2	( 2, 0, 2, 2 )	2.06	1.98	2.59	5	tele2
example3	( 3, 0, 2, 1 )	8.68	6.54	14.01	6	tele3
example4	( 3, 0, 2, 2 )	9.23	6.06	13.72	6	tele4
example5	( 6, 0, 1, 1 )	44.04	24.39	70.49	7	tele5
example6	( 6, 0, 1, 2 )	41.85	22.74	59.50	7	tele6
example7	( 2, 1, 2, 1 )	80.69	17.97	47.51	7	tele7
example8	( 2, 1, 2, 2 )	66.47	17.25	46.94	7	tele8
example9	( 2, 1, 2, 1 )	63.36	17.45	47.94	7	tele9
example10	( 2, 1, 2, 2 )	69.69	17.81	47.11	7	tele10
example11	( 2, 2, 2, 1 )	1399.2	155.54	570.40	9	tele11
example12	( 2, 2, 2, 2 )	1397.7	142.34	510.11	9	tele12
example13	( 3, 0, 3, 1 )	151.84	44.07	120.44	8	tele13
example14	( 3, 0, 3, 2 )	150.14	43.46	122.36	8	tele14
example15	( 3, 3, 0, 1 )	206.90	46.15	165.67	8	tele15
example16	( 3, 3, 0, 2 )	207.81	44.95	161.25	8	tele16
example17	( 3, 2, 1, 1 )	300.93	60.33	184.71	8	tele17
example18	( 3, 2, 1, 2 )	333.75	55.86	176.78	8	tele18
example19	( 3, 1, 3, 1 )	OOM	361.79	1556.1	10	tele19
example20	( 3, 1, 3, 2 )	OOM	370.18	1535.7	10	tele20