# Telescopers for Rational and Algebraic Functions via Residues

Supplementary material to the paper by Shaoshi Chen, Manuel Kauers, and Michael F. Singer.

## Software

A prototype implementation of the algorithms described in the paper is available here. This file contains Mathematica code which requires Koutschan's package HolonomicFunctions.m. It contains definitions of six functions ctRat1, ctRat2, ..., ctRat6, which correspond to the six algorithms for which a timing comparison is given below.

## Certificates for Example 8

The file certEx8.m contains the example rational function considered in the paper together with its two certificates. To check that the certificates are correct, type the following:
```      In[1]:= << HolonomicFunctions.m
HolonomicFunctions package by Christoph Koutschan, RISC-Linz, Version 1.5.1 (09.08.2011)
--> Type  ?HolonomicFunctions  for help
In[2]:= {L, f, g, h} = << certEx8.m;
In[3]:= ApplyOreOperator[L, f] - D[g, x] - D[h, y] // Together
Out[3]= 0
```
See cert.m for the Mathematica code which was used to compute these certificates. (This file also uses the Singular interface.)

## Timings

We have tested the algorithms from our paper against standard algorithms on about a hundred rational functions various sources, most of them with some combinatorial meaning. The following six techniques were compared:
• A: Chyzak's algorithm (the command CreativeTelescoping in Koutschan's package) applied to the rational function, yielding an ideal of telescopers in x and t. Then Chyzak's algorithm again applied to this ideal, yielding the desired telescoper in t only.
• A': same as A, but with x and y exchanged.
• B: Like in A, except that for the second application, Koutschan's ansatz (the command FindCreativeTelescoping in his package) was employed.
• C: Koutschan's command FindCreativeTelescoping was used for computing the telescoper in one shot.
• D: Equivalence from Section 2 of our paper, then Chyzak's algorithm (viz. the CreativeTelescoping command) for integrating the resulting algebraic functions.
• E: Equivalence from Section 2 of our paper, then step 1 of the algorithm from Section 3 of our paper, then Chyzak's algorithm (viz. the CreativeTelescoping command) for integrating the resulting algebraic functions.
• F: Equivalence from Section 2 of our paper, then the full algorithm from Section 3 of our paper, using Koutschan's implementation SolveCoupledSystem.
Timings were taken on a 64bit Linux machine with 100Gb RAM and 24 Intel Xeon processors with 3GHz each.
 in out A A' B C D E F ord deg bytecount meaning in-1.m out-1.m 0.71 7.45 1.41 16.11 6.56 5.88 4.98 3 11 3600 aztec diamond edge gfun, [x^0 y^0] in-2.m out-2.m 5.90 11.03 7.89 51.75 11.06 10.90 9.30 4 13 4344 aztec diamond edge gfun, [x^1 y^0] in-3.m out-3.m 1.16 34.96 7.30 61.89 12.21 12.48 11.42 4 15 5368 aztec diamond edge gfun, [x^0 y^1] in-4.m out-4.m 5.96 11.87 7.82 52.97 11.38 11.15 9.09 4 13 4344 aztec diamond edge gfun, [x^(-1) y^0] in-5.m out-5.m 0.73 6.32 1.66 21.57 6.19 5.63 4.79 3 10 3376 aztec diamond edge gfun, [x^0 y^(-1)] in-6.m out-6.m 6.04 11.47 11.32 77.44 11.54 11.28 9.27 4 14 5824 aztec diamond edge gfun, [x^(-1) y^(-1)] in-7.m out-7.m 6.04 32.20 11.24 52.98 11.90 11.59 11.49 4 14 5160 aztec diamond edge gfun, [x^(-1) y^1] in-8.m out-8.m 5.98 11.06 11.54 60.53 11.11 11.04 9.39 4 14 5824 aztec diamond edge gfun, [x^1 y^(-1)] in-9.m out-9.m 5.94 31.59 11.50 47.14 12.09 12.54 11.71 4 14 5160 aztec diamond edge gfun, [x^1 y^1] in-10.m out-10.m 34.02 495.75 23.72 465.36 69.87 87.31 60.35 7 11 10400 cores of a planar graph, [x^(2n)y^n] in-11.m out-11.m 2.89 147.87 2.33 32.67 1.63 1.68 1.76 4 6 3920 cores of a planar graph, [x^n y^(2n)] in-12.m out-12.m 18.82 409.63 20.45 199.60 54.72 63.09 44.66 6 9 7424 cores of a planar graph, [x^(2n)y^(2n)] in-13.m out-13.m 314.34 2079.81 565.10 6022.78 6098.31 630.98 287.44 11 17 20608 cores of a planar graph, [x^(3n)y^n] in-14.m out-14.m 1.82 55.74 1.57 16.63 17.88 1.57 1.84 3 4 2032 cores of a planar graph, [x^n y^(3n)] in-15.m out-15.m 1385.74 5198.98 2434.02 44390.07 848.92 2491.66 1332.63 13 21 31920 cores of a planar graph, [x^(4n)y^n] in-16.m out-16.m 252.61 2052.27 454.48 3623.02 337.07 414.81 298.00 10 16 19368 cores of a planar graph, [x^(2n) y^(3n)] in-17.m out-17.m 13.47 194.59 9.54 98.62 29.84 33.49 25.17 5 8 6128 cores of a planar graph, [x^(3n) y^(2n)] in-18.m out-18.m 3.12 1751.68 2.38 56.55 1.10 1.17 1.69 4 6 4016 cores of a planar graph, [x^n y^(4n)] in-19.m out-19.m >30h 2.17 4431.06 399.11 21.43 22.10 23.40 3 6 3992 artificial example from the paper in-20.m out-20.m 19.79 19.98 9.50 104.79 6.93 9.49 6.85 4 9 5872 random groves, [x^n y^n] in-21.m out-21.m 10712.13 125.60 421.60 5062.14 37.60 52.26 33.18 7 20 21784 random groves, [x^(2n) y^n] in-22.m out-22.m 117.96 11099.43 87.98 6060.53 37.11 54.08 33.48 7 20 21784 random groves, [x^n y^(2n)] in-23.m out-23.m >30h 529.80 10946.79 >30h 166.86 403.41 173.14 10 32 50560 random groves, [x^(3n) y^n] in-24.m out-24.m 16773.93 14784.08 765.81 15679.77 759.26 758.02 1997.19 7 27 31168 random groves, [x^(2n) y^(2n)] in-25.m out-25.m 873.93 >33h 1125.10 >30h 168.78 244.90 158.93 10 32 50560 random groves, [x^n y^(3n)] in-26.m out-26.m 126.55 125.61 275.13 2655.64 2666.71 280.68 127.92 6 23 13576 knight walks ending at (0,0) in-27.m out-27.m 4294.85 2227.09 31336.71 >30h 2178.55 3116.89 4378.15 12 76 88128 knight walks ending at (1,0) in-28.m out-28.m 2164.31 4283.18 21465.62 >30h 4264.47 5166.89 65365.06 12 76 87728 knight walks ending at (0,1) in-29.m out-29.m 4271.47 2303.72 37185.64 >30h 2287.83 3273.19 2376.63 12 76 88176 knight walks ending at (-1,0) in-30.m out-30.m 2441.47 4247.27 43244.79 >30h 5386.17 6190.89 64508.09 12 76 87728 knight walks ending at (0,-1) in-31.m out-31.m 8333.90 7494.64 39162.78 >30h 7419.98 7915.04 72994.38 12 74 85536 knight walks ending at (-1,-1) in-32.m out-32.m 8392.92 7465.50 36957.55 >30h 7276.75 7938.35 74181.14 12 74 85536 knight walks ending at (-1,1) in-33.m out-33.m 7754.31 8209.88 34464.58 running 8528.18 7808.53 72216.13 12 74 84928 knight walks ending at (1,-1) in-34.m out-34.m 7436.03 10732.05 34075.48 running 10663.64 7756.55 71008.12 12 74 84928 knight walks ending at (1,1) in-35.m out-35.m 9.75 9.86 12.99 28.70 9.71 9.85 7.47 4 9 3384 quantum random walks ending at (0,0) in-36.m out-36.m 5.53 5.81 3.74 11.70 5.55 5.46 3.99 3 9 3392 quantum random walks ending at (1,0) in-37.m out-37.m 5.85 5.62 3.88 10.57 5.41 5.36 4.01 3 9 3312 quantum random walks ending at (0,1) in-38.m out-38.m 6.89 6.22 6.93 19.09 5.77 5.35 3.89 3 11 3968 quantum random walks ending at (-1,0) in-39.m out-39.m 6.00 6.62 4.92 13.98 6.61 6.33 5.44 3 11 3824 quantum random walks ending at (0,-1) in-40.m out-40.m 11.41 11.16 13.95 53.75 11.06 11.25 9.25 4 13 4864 quantum random walks ending at (-1,-1) in-41.m out-41.m 6.64 5.98 7.18 12.90 5.67 5.22 3.82 3 12 4200 quantum random walks ending at (-1,1) in-42.m out-42.m 5.97 6.33 6.91 13.03 6.16 6.35 5.41 3 12 4344 quantum random walks ending at (1,-1) in-43.m out-43.m 10.26 10.37 9.80 35.48 10.05 10.56 7.52 4 9 3384 quantum random walks ending at (1,1) in-44.m out-44.m 3.48 2.61 2.59 24.55 0.36 0.40 0.59 3 5 2880 diagonal of 3d-rooks in-45.m out-45.m 27.89 30.74 65.50 206.58 1.51 1.59 2.50 4 21 16840 diagonal of 3d-rooks (variation) in-46.m out-46.m 4838.00 4986.07 8019.37 >30h 543.69 580.05 479.52 6 45 48200 diagonal of 3d-rooks (variation) in-47.m out-47.m 3.05 5.72 1.69 29.06 0.55 0.61 0.89 3 10 3216 diagonal of 3d-rooks (variation) in-48.m out-48.m 44.63 62.06 104.79 498.45 2.02 2.12 3.38 4 30 24712 diagonal of 3d-rooks (variation) in-49.m out-49.m 12109.41 12318.27 39640.75 >30h 1252.31 1452.92 1186.72 6 71 90320 diagonal of 3d-queens in-50.m out-50.m 2.87 3.48 1.59 19.93 0.42 0.46 0.67 3 5 2880 diagonal of 3d-rooks in-51.m out-51.m 31.38 28.82 42.98 182.97 1.40 1.53 2.39 4 21 16840 diagonal of 3d-rooks (variation) in-52.m out-52.m 5226.95 4912.46 8242.97 >30h 536.11 602.07 479.23 6 45 48200 diagonal of 3d-rooks (variation) in-53.m out-53.m 5.76 3.03 6.69 24.42 0.39 0.44 0.64 3 10 3216 diagonal of 3d-rooks (variation) in-54.m out-54.m 60.18 44.90 211.31 420.31 1.82 1.91 3.02 4 30 24712 diagonal of 3d-rooks (variation) in-55.m out-55.m 11797.54 11598.18 38827.70 >30h 1260.61 1453.87 1201.81 6 71 90320 diagonal of 3d-queens in-56.m out-56.m 2.80 2.77 1.60 22.96 22.69 1.55 2.58 3 5 2768 diagonal of 3d-rooks in-57.m out-57.m 31.48 32.27 42.25 198.90 201.68 42.73 31.40 4 21 17048 diagonal of 3d-rooks (variation) in-58.m out-58.m 5195.78 5082.99 8270.46 >30h 571.67 8262.68 5086.82 6 45 48552 diagonal of 3d-rooks (variation) in-59.m out-59.m 6.47 5.91 7.53 28.93 0.54 0.71 0.88 3 10 3216 diagonal of 3d-rooks (variation) in-60.m out-60.m 65.59 61.88 208.60 1270.58 2.06 2.14 3.70 4 30 24712 diagonal of 3d-rooks (variation) in-61.m out-61.m 11805.01 11975.58 39649.67 >30h 1268.54 1416.92 1203.11 6 71 90320 diagonal of 3d-queens in-62.m out-62.m 95.64 8.89 42.94 400.03 2.47 2.52 94.70 5 14 11392 2-1-1 diagonal of 3d-rooks in-63.m out-63.m >30h 477.99 48682.20 86435.48 99.49 97.23 151.46 8 60 85752 2-1-1 diagonal of 3d-rooks (variation) in-65.m out-65.m 709.68 3.91 30.30 57.40 0.54 0.58 0.87 3 4 2536 2-1-1 diagonal of 3d-rooks (variation) in-66.m out-66.m >30h 1166.03 running running 183.22 183.68 242.61 9 93 163536 2-1-1 diagonal of 3d-rooks (variation) in-68.m out-68.m 225.47 271.87 515.36 1517.94 259.35 204.20 1704.81 4 40 24192 randomly generated input in-69.m out-69.m 216.96 243.07 466.36 1374.09 249.16 202.67 989.00 4 40 23680 randomly generated input in-70.m out-70.m 221.35 45.30 436.84 1232.80 43.09 38.34 26.76 4 40 23528 randomly generated input in-71.m out-71.m 37.21 238.57 447.21 3060.84 48.05 32.82 27.33 4 40 24016 randomly generated input in-72.m out-72.m 227.78 257.81 494.57 1357.72 263.46 210.24 1012.61 4 40 23920 randomly generated input in-73.m out-73.m 36.77 231.64 351.79 2540.32 44.68 49.84 26.82 4 40 23296 randomly generated input in-74.m out-74.m 225.23 242.18 438.31 1319.19 235.85 191.66 1185.38 4 40 23488 randomly generated input in-75.m out-75.m 2.01 1.78 1.60 6.98 1.68 1.90 1.35 3 4 2592 restricted 2D lattice walks with small steps in-76.m out-76.m 1.75 1.73 1.60 11.84 1.72 2.19 1.30 3 5 3192 restricted 2D lattice walks with small steps in-77.m out-77.m 2.06 2.05 2.05 12.81 1.95 2.71 1.66 3 8 4448 restricted 2D lattice walks with small steps in-78.m out-78.m 2.72 2.34 1.79 12.43 2.32 3.31 1.83 3 6 3776 restricted 2D lattice walks with small steps in-79.m out-79.m 38.02 31.55 18.15 330.90 13.45 21.02 11.49 5 16 12880 restricted 2D lattice walks with small steps in-80.m out-80.m 64.94 66.18 46.34 505.83 25.49 37.43 20.48 5 20 17136 restricted 2D lattice walks with small steps in-81.m out-81.m 42.14 32.90 19.45 334.40 14.15 21.84 11.90 5 15 12656 restricted 2D lattice walks with small steps in-82.m out-82.m 69.64 72.50 50.74 474.22 25.45 37.29 20.01 5 18 13424 restricted 2D lattice walks with small steps in-83.m out-83.m 99.65 68.21 64.35 751.13 27.78 39.20 22.80 5 24 22200 restricted 2D lattice walks with small steps in-84.m out-84.m 114.51 81.38 99.00 866.63 26.04 35.92 21.49 5 24 22656 restricted 2D lattice walks with small steps in-85.m out-85.m 36.02 23.29 35.90 192.23 6.38 6.97 4.94 5 15 12464 restricted 2D lattice walks with small steps in-86.m out-86.m 57.41 45.51 26.76 250.46 18.21 19.23 13.63 5 18 15072 restricted 2D lattice walks with small steps in-87.m out-87.m 109.70 65.87 71.00 775.62 29.81 42.23 24.04 5 24 22160 restricted 2D lattice walks with small steps in-88.m out-88.m 136.23 79.23 101.06 863.12 27.99 39.03 23.40 5 24 22584 restricted 2D lattice walks with small steps in-89.m out-89.m 30.51 22.46 30.68 162.53 6.03 6.76 4.85 5 16 13368 restricted 2D lattice walks with small steps in-90.m out-90.m 51.72 43.52 25.63 228.03 17.87 19.34 13.61 5 19 15944 restricted 2D lattice walks with small steps in-91.m out-91.m 396.82 363.07 11.36 66.08 6.29 6.85 3.91 3 4 2736 restricted 2D lattice walks with small steps in-92.m out-92.m 0.21 0.27 0.46 1.68 0.13 0.21 0.38 2 3 1992 diagonal of Szego's ratfun in-93.m out-93.m 8.99 0.81 9.03 40.33 0.83 0.85 1.06 4 10 7976 2-1-1 diagonal of Szego's ratfun in-94.m out-94.m 0.76 11.96 2.97 33.38 0.91 0.73 0.91 4 10 7976 1-2-1 diagonal of Szego's ratfun in-95.m out-95.m 200.42 7.82 103.93 510.25 9.78 7.54 10.41 6 15 15528 3-1-1 diagonal of Szego's ratfun in-96.m out-96.m 12.37 13.81 16.10 81.62 17.77 14.17 51.66 4 11 9128 2-2-1 diagonal of Szego's ratfun in-97.m out-97.m 6.01 206.22 17.49 579.80 10.30 10.10 10.62 6 15 15528 1-3-1 diagonal of Szego's ratfun