Lazy Hermite Reduction and Creative Telescoping for Algebraic Functions

Supplementary material to the paper by Shaoshi Chen, Lixin Du, and Manuel Kauers.

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.

Timings

We have applied our new approach to the test suite we composed for an earlier paper. Below is a comparison of the algorithms evaluated for the old paper (A--F) and two variants (G, H) of the algorithm of the new paper. The columns A--F are copied verbatim from the earlier evaluation. The new columns G and H are as follows: Timings were taken on a 64bit Linux machine with 700Gb RAM and 24 Intel Xeon processors with 3GHz each.
inoutAA'BCDEFGHIorddegbytecountmeaning
in-1.mout-1.m0.717.451.4116.116.565.884.986.664.47392.613113824aztec diamond edge gfun, [x^0 y^0]
in-2.mout-2.m5.9011.037.8951.7511.0610.909.3010.936.36957.274134576aztec diamond edge gfun, [x^1 y^0]
in-3.mout-3.m1.1634.967.3061.8912.2112.4811.4222.6415.54990.964155632aztec diamond edge gfun, [x^0 y^1]
in-4.mout-4.m5.9611.877.8252.9711.3811.159.0912.476.79652.164134576aztec diamond edge gfun, [x^(-1) y^0]
in-5.mout-5.m0.736.321.6621.576.195.634.7912.586.44457.733103600aztec diamond edge gfun, [x^0 y^(-1)]
in-6.mout-6.m6.0411.4711.3277.4411.5411.289.2716.529.70365.824146104aztec diamond edge gfun, [x^(-1) y^(-1)]
in-7.mout-7.m6.0432.2011.2452.9811.9011.5911.4929.9618.55583.244145432aztec diamond edge gfun, [x^(-1) y^1]
in-8.mout-8.m5.9811.0611.5460.5311.1111.049.3914.968.37596.674146104aztec diamond edge gfun, [x^1 y^(-1)]
in-9.mout-9.m5.9431.5911.5047.1412.0912.5411.7123.9820.671309.754145432aztec diamond edge gfun, [x^1 y^1]
in-10.mout-10.m34.02495.7523.72465.3669.8787.3160.3563.5187.628227.5071110368cores of a planar graph, [x^(2n)y^n]
in-11.mout-11.m2.89147.872.3332.671.631.681.761.311.222.57464144cores of a planar graph, [x^n y^(2n)]
in-12.mout-12.m18.82409.6320.45199.6054.7263.0944.66182.94225.078441.65697056cores of a planar graph, [x^(2n)y^(2n)]
in-13.mout-13.m314.342079.81565.106022.786098.31630.98287.44325.08411.58>30h111720928cores of a planar graph, [x^(3n)y^n]
in-14.mout-14.m1.8255.741.5716.6317.881.571.840.940.942.32342192cores of a planar graph, [x^n y^(3n)]
in-15.mout-15.m1385.745198.982434.0244390.07848.922491.661332.63589.46759.66>30h132132392cores of a planar graph, [x^(4n)y^n]
in-16.mout-16.m252.612052.27454.483623.02337.07414.81298.00774.641465.19>30h101619768cores of a planar graph, [x^(2n) y^(3n)]
in-17.mout-17.m13.47194.599.5498.6229.8433.4925.17102.8979.846620.72585904cores of a planar graph, [x^(3n) y^(2n)]
in-18.mout-18.m3.121751.682.3856.551.101.171.692.001.993.00464144cores of a planar graph, [x^n y^(4n)]
in-19.mout-19.m>30h2.174431.06399.1121.4322.1023.4056.2755.93155.31364216artificial example from the paper
in-20.mout-20.m19.7919.989.50104.796.938.776.8511.428.711841.74496144random groves, [x^n y^n]
in-21.mout-21.m10712.13125.60421.605062.1437.6052.2633.1845.4143.412739.1072019480random groves, [x^(2n) y^n]
in-22.mout-22.m117.9611099.4387.986060.5337.1154.0833.4845.8743.242756.8472019480random groves, [x^n y^(2n)]
in-23.mout-23.m>30h529.8010946.79>30h166.86403.41173.14170.91202.497004.39103251904random groves, [x^(3n) y^n]
in-24.mout-24.m16773.9314784.08765.8115679.77759.26758.021997.1978485.99>30h>30h72731440random groves, [x^(2n) y^(2n)]
in-25.mout-25.m873.93>33h1125.10>30h168.78244.90158.93167.70193.236996.08103251904random groves, [x^n y^(3n)]
in-26.mout-26.m126.55125.61275.132655.642666.71280.68127.92>30h>30h>30h62313224knight walks ending at (0,0)
in-27.mout-27.m4294.852227.0931336.71>30h2178.553116.894378.15>30h>30h>30h127689360knight walks ending at (1,0)
in-28.mout-28.m2164.314283.1821465.62>30h4264.475166.8965365.06>30h>30h>30h127689752knight walks ending at (0,1)
in-29.mout-29.m4271.472303.7237185.64>30h2287.833273.192376.63>30h>30h>30h127690272knight walks ending at (-1,0)
in-30.mout-30.m2441.474247.2743244.79>30h5386.176190.8964508.09>30h>30h>30h127689752knight walks ending at (0,-1)
in-31.mout-31.m8333.907494.6439162.78>30h7419.987915.0472994.38>30h>30h>30h127487664knight walks ending at (-1,-1)
in-32.mout-32.m8392.927465.5036957.55>30h7276.757938.3574181.14>30h>30h>30h127487664knight walks ending at (-1,1)
in-33.mout-33.m7754.318209.8834464.58>30h8528.187808.5372216.13>30h>30h>30h127486952knight walks ending at (1,-1)
in-34.mout-34.m7436.0310732.0534075.48>30h10663.647756.5571008.12>30h>30h>30h127486952knight walks ending at (1,1)
in-35.mout-35.m9.759.8612.9928.709.719.857.4734.8316.11992.58493592quantum random walks ending at (0,0)
in-36.mout-36.m5.535.813.7411.705.555.463.9929.2213.701852.53393600quantum random walks ending at (1,0)
in-37.mout-37.m5.855.623.8810.575.415.364.0123.1717.56795.27393520quantum random walks ending at (0,1)
in-38.mout-38.m6.896.226.9319.095.775.353.8923.1311.19834.993114200quantum random walks ending at (-1,0)
in-39.mout-39.m6.006.624.9213.986.616.335.4470.4545.132220.323114056quantum random walks ending at (0,-1)
in-40.mout-40.m11.4111.1613.9553.7511.0611.259.2586.8255.381995.384135104quantum random walks ending at (-1,-1)
in-41.mout-41.m6.645.987.1812.905.675.223.8231.0821.17873.723124432quantum random walks ending at (-1,1)
in-42.mout-42.m5.976.336.9113.036.166.355.4170.9746.692069.463124576quantum random walks ending at (1,-1)
in-43.mout-43.m10.2610.379.8035.4810.0510.567.5233.6623.731348.67493592quantum random walks ending at (1,1)
in-44.mout-44.m3.482.612.5924.550.360.400.590.630.60470.72353072diagonal of 3d-rooks
in-45.mout-45.m27.8930.7465.50206.581.511.592.502.432.401538.1742115688diagonal of 3d-rooks (variation)
in-46.mout-46.m4838.004986.078019.37>30h543.69580.05479.52>30h>30h>30h64549352diagonal of 3d-rooks (variation)
in-47.mout-47.m3.055.721.6929.060.550.610.891.421.431120.873103424diagonal of 3d-rooks (variation)
in-48.mout-48.m44.6362.06104.79498.452.022.123.385.646.221888.3943022552diagonal of 3d-rooks (variation)
in-49.mout-49.m12109.4112318.2739640.75>30h1252.311452.921186.72>30h>30h>30h67192552diagonal of 3d-queens
in-50.mout-50.m2.873.481.5919.930.420.460.670.860.75554.30353072diagonal of 3d-rooks
in-51.mout-51.m31.3828.8242.98182.971.401.532.392.392.722007.4342115688diagonal of 3d-rooks (variation)
in-52.mout-52.m5226.954912.468242.97>30h536.11602.07479.23>30h>30h>30h64549352diagonal of 3d-rooks (variation)
in-53.mout-53.m5.763.036.6924.420.390.440.640.850.89551.163103424diagonal of 3d-rooks (variation)
in-54.mout-54.m60.1844.90211.31420.311.821.913.024.324.472233.1543022552diagonal of 3d-rooks (variation)
in-55.mout-55.m11797.5411598.1838827.70>30h1260.611453.871201.81>30h>30h>30h67192552diagonal of 3d-queens
in-56.mout-56.m2.802.771.6022.9622.691.552.580.720.73489.17352952diagonal of 3d-rooks
in-57.mout-57.m31.4832.2742.25198.90201.6842.7331.402.562.421532.7342115352diagonal of 3d-rooks (variation)
in-58.mout-58.m5195.785082.998270.46>30h571.678262.685086.82>30h>30h>30h64549048diagonal of 3d-rooks (variation)
in-59.mout-59.m6.475.917.5328.930.540.710.881.401.431077.433103424diagonal of 3d-rooks (variation)
in-60.mout-60.m65.5961.88208.601270.582.062.143.705.906.061904.7743022552diagonal of 3d-rooks (variation)
in-61.mout-61.m11805.0111975.5839649.67>30h1268.541416.921203.11>30h>30h>30h67192552diagonal of 3d-queens
in-62.mout-62.m95.648.8942.94400.032.472.5294.702.593.28772.53514101282-1-1 diagonal of 3d-rooks
in-63.mout-63.m>30h477.9948682.2086435.4899.4997.23151.4657.6157.713486.60860877602-1-1 diagonal of 3d-rooks (variation)
in-65.mout-65.m709.683.9130.3057.400.540.580.871.591.241010.773427122-1-1 diagonal of 3d-rooks (variation)
in-66.mout-66.m>30h1166.03>30h>30h183.22183.68242.61111.4875.886271.129931670082-1-1 diagonal of 3d-rooks (variation)
in-68.mout-68.m225.47271.87515.361517.94259.35204.201704.8157583.6261792.83>30h44024936randomly generated input
in-69.mout-69.m216.96243.07466.361374.09249.16202.67989.0051819.3154077.99>30h44024360randomly generated input
in-70.mout-70.m221.3545.30436.841232.8043.0938.3426.761133.48200.496024.1044024144randomly generated input
in-71.mout-71.m37.21238.57447.213060.8448.0532.8227.33933.03205.615548.8944024632randomly generated input
in-72.mout-72.m227.78257.81494.571357.72263.46210.241012.6157982.1364668.30>30h44024752randomly generated input
in-73.mout-73.m36.77231.64351.792540.3244.6849.8426.821487.15225.445850.5744024120randomly generated input
in-74.mout-74.m225.23242.18438.311319.19235.85191.661185.3851913.4554944.86>30h44024104randomly generated input
in-75.mout-75.m2.011.781.606.981.681.901.353.712.1237.42342776restricted 2D lattice walks with small steps
in-76.mout-76.m1.751.731.6011.841.722.191.307.892.51101.73353392restricted 2D lattice walks with small steps
in-77.mout-77.m2.062.052.0512.811.952.711.669.115.46118.09384680restricted 2D lattice walks with small steps
in-78.mout-78.m2.722.341.7912.432.323.311.8312.415.28223.65364000restricted 2D lattice walks with small steps
in-79.mout-79.m38.0231.5518.15330.9013.4521.0211.496.436.29383.0151613368restricted 2D lattice walks with small steps
in-80.mout-80.m64.9466.1846.34505.8325.4937.4320.4812.9112.04553.6352017680restricted 2D lattice walks with small steps
in-81.mout-81.m42.1432.9019.45334.4014.1521.8411.907.256.11386.4151513120restricted 2D lattice walks with small steps
in-82.mout-82.m69.6472.5050.74474.2225.4537.2920.0111.8810.99708.4351813688restricted 2D lattice walks with small steps
in-83.mout-83.m99.6568.2164.35751.1327.7839.2022.8026.3923.50399.5552421328restricted 2D lattice walks with small steps
in-84.mout-84.m114.5181.3899.00866.6326.0435.9221.4943.6627.271132.3852421328restricted 2D lattice walks with small steps
in-85.mout-85.m36.0223.2935.90192.236.386.974.945.655.34190.0251512936restricted 2D lattice walks with small steps
in-86.mout-86.m57.4145.5126.76250.4618.2119.2313.6311.9910.68322.2451815600restricted 2D lattice walks with small steps
in-87.mout-87.m109.7065.8771.00775.6229.8142.2324.0421.3915.43381.8752421328restricted 2D lattice walks with small steps
in-88.mout-88.m136.2379.23101.06863.1227.9939.0323.4027.8317.88625.5252421328restricted 2D lattice walks with small steps
in-89.mout-89.m30.5122.4630.68162.536.036.764.855.515.31198.3651613848restricted 2D lattice walks with small steps
in-90.mout-90.m51.7243.5225.63228.0317.8719.3413.6111.6610.22347.5051916512restricted 2D lattice walks with small steps
in-91.mout-91.m396.82363.0711.3666.086.296.853.915.195.03768.18342928restricted 2D lattice walks with small steps
in-92.mout-92.m0.210.270.461.680.130.210.380.140.1847.81232160diagonal of Szego's ratfun
in-93.mout-93.m8.990.819.0340.330.830.851.061.021.08241.8041074962-1-1 diagonal of Szego's ratfun
in-94.mout-94.m0.7611.962.9733.380.910.730.911.501.60248.7341074961-2-1 diagonal of Szego's ratfun
in-95.mout-95.m200.427.82103.93510.259.787.5410.414.574.31401.69615160323-1-1 diagonal of Szego's ratfun
in-96.mout-96.m12.3713.8116.1081.6217.7714.1751.661627.461869.53>30h41194642-2-1 diagonal of Szego's ratfun
in-97.mout-97.m6.01206.2217.49579.8010.3010.1010.624.784.78419.63615160321-3-1 diagonal of Szego's ratfun