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: Timings were taken on a 64bit Linux machine with 100Gb RAM and 24 Intel Xeon processors with 3GHz each.
inoutAA'BCDEForddegbytecountmeaning
in-1.mout-1.m0.717.451.4116.116.565.884.983113600aztec diamond edge gfun, [x^0 y^0]
in-2.mout-2.m5.9011.037.8951.7511.0610.909.304134344aztec diamond edge gfun, [x^1 y^0]
in-3.mout-3.m1.1634.967.3061.8912.2112.4811.424155368aztec diamond edge gfun, [x^0 y^1]
in-4.mout-4.m5.9611.877.8252.9711.3811.159.094134344aztec diamond edge gfun, [x^(-1) y^0]
in-5.mout-5.m0.736.321.6621.576.195.634.793103376aztec diamond edge gfun, [x^0 y^(-1)]
in-6.mout-6.m6.0411.4711.3277.4411.5411.289.274145824aztec diamond edge gfun, [x^(-1) y^(-1)]
in-7.mout-7.m6.0432.2011.2452.9811.9011.5911.494145160aztec diamond edge gfun, [x^(-1) y^1]
in-8.mout-8.m5.9811.0611.5460.5311.1111.049.394145824aztec diamond edge gfun, [x^1 y^(-1)]
in-9.mout-9.m5.9431.5911.5047.1412.0912.5411.714145160aztec diamond edge gfun, [x^1 y^1]
in-10.mout-10.m34.02495.7523.72465.3669.8787.3160.3571110400cores of a planar graph, [x^(2n)y^n]
in-11.mout-11.m2.89147.872.3332.671.631.681.76463920cores of a planar graph, [x^n y^(2n)]
in-12.mout-12.m18.82409.6320.45199.6054.7263.0944.66697424cores of a planar graph, [x^(2n)y^(2n)]
in-13.mout-13.m314.342079.81565.106022.786098.31630.98287.44111720608cores of a planar graph, [x^(3n)y^n]
in-14.mout-14.m1.8255.741.5716.6317.881.571.84342032cores of a planar graph, [x^n y^(3n)]
in-15.mout-15.m1385.745198.982434.0244390.07848.922491.661332.63132131920cores of a planar graph, [x^(4n)y^n]
in-16.mout-16.m252.612052.27454.483623.02337.07414.81298.00101619368cores of a planar graph, [x^(2n) y^(3n)]
in-17.mout-17.m13.47194.599.5498.6229.8433.4925.17586128cores of a planar graph, [x^(3n) y^(2n)]
in-18.mout-18.m3.121751.682.3856.551.101.171.69464016cores of a planar graph, [x^n y^(4n)]
in-19.mout-19.m>30h2.174431.06399.1121.4322.1023.40363992artificial example from the paper
in-20.mout-20.m19.7919.989.50104.796.939.496.85495872random groves, [x^n y^n]
in-21.mout-21.m10712.13125.60421.605062.1437.6052.2633.1872021784random groves, [x^(2n) y^n]
in-22.mout-22.m117.9611099.4387.986060.5337.1154.0833.4872021784random groves, [x^n y^(2n)]
in-23.mout-23.m>30h529.8010946.79>30h166.86403.41173.14103250560random groves, [x^(3n) y^n]
in-24.mout-24.m16773.9314784.08765.8115679.77759.26758.021997.1972731168random groves, [x^(2n) y^(2n)]
in-25.mout-25.m873.93>33h1125.10>30h168.78244.90158.93103250560random groves, [x^n y^(3n)]
in-26.mout-26.m126.55125.61275.132655.642666.71280.68127.9262313576knight walks ending at (0,0)
in-27.mout-27.m4294.852227.0931336.71>30h2178.553116.894378.15127688128knight walks ending at (1,0)
in-28.mout-28.m2164.314283.1821465.62>30h4264.475166.8965365.06127687728knight walks ending at (0,1)
in-29.mout-29.m4271.472303.7237185.64>30h2287.833273.192376.63127688176knight walks ending at (-1,0)
in-30.mout-30.m2441.474247.2743244.79>30h5386.176190.8964508.09127687728knight walks ending at (0,-1)
in-31.mout-31.m8333.907494.6439162.78>30h7419.987915.0472994.38127485536knight walks ending at (-1,-1)
in-32.mout-32.m8392.927465.5036957.55>30h7276.757938.3574181.14127485536knight walks ending at (-1,1)
in-33.mout-33.m7754.318209.8834464.58running8528.187808.5372216.13127484928knight walks ending at (1,-1)
in-34.mout-34.m7436.0310732.0534075.48running10663.647756.5571008.12127484928knight walks ending at (1,1)
in-35.mout-35.m9.759.8612.9928.709.719.857.47493384quantum random walks ending at (0,0)
in-36.mout-36.m5.535.813.7411.705.555.463.99393392quantum random walks ending at (1,0)
in-37.mout-37.m5.855.623.8810.575.415.364.01393312quantum random walks ending at (0,1)
in-38.mout-38.m6.896.226.9319.095.775.353.893113968quantum random walks ending at (-1,0)
in-39.mout-39.m6.006.624.9213.986.616.335.443113824quantum random walks ending at (0,-1)
in-40.mout-40.m11.4111.1613.9553.7511.0611.259.254134864quantum random walks ending at (-1,-1)
in-41.mout-41.m6.645.987.1812.905.675.223.823124200quantum random walks ending at (-1,1)
in-42.mout-42.m5.976.336.9113.036.166.355.413124344quantum random walks ending at (1,-1)
in-43.mout-43.m10.2610.379.8035.4810.0510.567.52493384quantum random walks ending at (1,1)
in-44.mout-44.m3.482.612.5924.550.360.400.59352880diagonal of 3d-rooks
in-45.mout-45.m27.8930.7465.50206.581.511.592.5042116840diagonal of 3d-rooks (variation)
in-46.mout-46.m4838.004986.078019.37>30h543.69580.05479.5264548200diagonal of 3d-rooks (variation)
in-47.mout-47.m3.055.721.6929.060.550.610.893103216diagonal of 3d-rooks (variation)
in-48.mout-48.m44.6362.06104.79498.452.022.123.3843024712diagonal of 3d-rooks (variation)
in-49.mout-49.m12109.4112318.2739640.75>30h1252.311452.921186.7267190320diagonal of 3d-queens
in-50.mout-50.m2.873.481.5919.930.420.460.67352880diagonal of 3d-rooks
in-51.mout-51.m31.3828.8242.98182.971.401.532.3942116840diagonal of 3d-rooks (variation)
in-52.mout-52.m5226.954912.468242.97>30h536.11602.07479.2364548200diagonal of 3d-rooks (variation)
in-53.mout-53.m5.763.036.6924.420.390.440.643103216diagonal of 3d-rooks (variation)
in-54.mout-54.m60.1844.90211.31420.311.821.913.0243024712diagonal of 3d-rooks (variation)
in-55.mout-55.m11797.5411598.1838827.70>30h1260.611453.871201.8167190320diagonal of 3d-queens
in-56.mout-56.m2.802.771.6022.9622.691.552.58352768diagonal of 3d-rooks
in-57.mout-57.m31.4832.2742.25198.90201.6842.7331.4042117048diagonal of 3d-rooks (variation)
in-58.mout-58.m5195.785082.998270.46>30h571.678262.685086.8264548552diagonal of 3d-rooks (variation)
in-59.mout-59.m6.475.917.5328.930.540.710.883103216diagonal of 3d-rooks (variation)
in-60.mout-60.m65.5961.88208.601270.582.062.143.7043024712diagonal of 3d-rooks (variation)
in-61.mout-61.m11805.0111975.5839649.67>30h1268.541416.921203.1167190320diagonal of 3d-queens
in-62.mout-62.m95.648.8942.94400.032.472.5294.70514113922-1-1 diagonal of 3d-rooks
in-63.mout-63.m>30h477.9948682.2086435.4899.4997.23151.46860857522-1-1 diagonal of 3d-rooks (variation)
in-65.mout-65.m709.683.9130.3057.400.540.580.873425362-1-1 diagonal of 3d-rooks (variation)
in-66.mout-66.m>30h1166.03runningrunning183.22183.68242.619931635362-1-1 diagonal of 3d-rooks (variation)
in-68.mout-68.m225.47271.87515.361517.94259.35204.201704.8144024192randomly generated input
in-69.mout-69.m216.96243.07466.361374.09249.16202.67989.0044023680randomly generated input
in-70.mout-70.m221.3545.30436.841232.8043.0938.3426.7644023528randomly generated input
in-71.mout-71.m37.21238.57447.213060.8448.0532.8227.3344024016randomly generated input
in-72.mout-72.m227.78257.81494.571357.72263.46210.241012.6144023920randomly generated input
in-73.mout-73.m36.77231.64351.792540.3244.6849.8426.8244023296randomly generated input
in-74.mout-74.m225.23242.18438.311319.19235.85191.661185.3844023488randomly generated input
in-75.mout-75.m2.011.781.606.981.681.901.35342592restricted 2D lattice walks with small steps
in-76.mout-76.m1.751.731.6011.841.722.191.30353192restricted 2D lattice walks with small steps
in-77.mout-77.m2.062.052.0512.811.952.711.66384448restricted 2D lattice walks with small steps
in-78.mout-78.m2.722.341.7912.432.323.311.83363776restricted 2D lattice walks with small steps
in-79.mout-79.m38.0231.5518.15330.9013.4521.0211.4951612880restricted 2D lattice walks with small steps
in-80.mout-80.m64.9466.1846.34505.8325.4937.4320.4852017136restricted 2D lattice walks with small steps
in-81.mout-81.m42.1432.9019.45334.4014.1521.8411.9051512656restricted 2D lattice walks with small steps
in-82.mout-82.m69.6472.5050.74474.2225.4537.2920.0151813424restricted 2D lattice walks with small steps
in-83.mout-83.m99.6568.2164.35751.1327.7839.2022.8052422200restricted 2D lattice walks with small steps
in-84.mout-84.m114.5181.3899.00866.6326.0435.9221.4952422656restricted 2D lattice walks with small steps
in-85.mout-85.m36.0223.2935.90192.236.386.974.9451512464restricted 2D lattice walks with small steps
in-86.mout-86.m57.4145.5126.76250.4618.2119.2313.6351815072restricted 2D lattice walks with small steps
in-87.mout-87.m109.7065.8771.00775.6229.8142.2324.0452422160restricted 2D lattice walks with small steps
in-88.mout-88.m136.2379.23101.06863.1227.9939.0323.4052422584restricted 2D lattice walks with small steps
in-89.mout-89.m30.5122.4630.68162.536.036.764.8551613368restricted 2D lattice walks with small steps
in-90.mout-90.m51.7243.5225.63228.0317.8719.3413.6151915944restricted 2D lattice walks with small steps
in-91.mout-91.m396.82363.0711.3666.086.296.853.91342736restricted 2D lattice walks with small steps
in-92.mout-92.m0.210.270.461.680.130.210.38231992diagonal of Szego's ratfun
in-93.mout-93.m8.990.819.0340.330.830.851.0641079762-1-1 diagonal of Szego's ratfun
in-94.mout-94.m0.7611.962.9733.380.910.730.9141079761-2-1 diagonal of Szego's ratfun
in-95.mout-95.m200.427.82103.93510.259.787.5410.41615155283-1-1 diagonal of Szego's ratfun
in-96.mout-96.m12.3713.8116.1081.6217.7714.1751.6641191282-2-1 diagonal of Szego's ratfun
in-97.mout-97.m6.01206.2217.49579.8010.3010.1010.62615155281-3-1 diagonal of Szego's ratfun