# 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:
• G: Reduction Based Telescoping with Lazy Hermite Reduction (LHR) as described in the paper. In the ith iteration, LHR is applied to the remainder of the previous iteration after polynomial reduction.
• H: Reduction Based Telescoping with Lazy Hermite Reduction (LHR) as described in the paper. In the ith iteration, LHR is applied to the output of the LHR call of the previous iteration, i.e., the form of the remainder before polynomial reduction was applied to it.
• I: Reduction Based Telescoping with Hermite Reduction applied to an integral basis that is normal at infinity. The reported computation time includes the time for computing the integral bases, which is typically a dominant portion. In the ith iteration, LHR is applied to the output of the LHR call of the previous iteration, i.e., the form of the remainder before polynomial reduction was applied to it.
Timings were taken on a 64bit Linux machine with 700Gb RAM and 24 Intel Xeon processors with 3GHz each.
 in out A A' B C D E F G H I ord deg bytecount meaning in-1.m out-1.m 0.71 7.45 1.41 16.11 6.56 5.88 4.98 6.66 4.47 392.61 3 11 3824 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 10.93 6.36 957.27 4 13 4576 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 22.64 15.54 990.96 4 15 5632 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 12.47 6.79 652.16 4 13 4576 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 12.58 6.44 457.73 3 10 3600 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 16.52 9.70 365.82 4 14 6104 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 29.96 18.55 583.24 4 14 5432 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 14.96 8.37 596.67 4 14 6104 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 23.98 20.67 1309.75 4 14 5432 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 63.51 87.62 8227.50 7 11 10368 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 1.31 1.22 2.57 4 6 4144 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 182.94 225.07 8441.65 6 9 7056 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 325.08 411.58 >30h 11 17 20928 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 0.94 0.94 2.32 3 4 2192 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 589.46 759.66 >30h 13 21 32392 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 774.64 1465.19 >30h 10 16 19768 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 102.89 79.84 6620.72 5 8 5904 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 2.00 1.99 3.00 4 6 4144 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 56.27 55.93 155.31 3 6 4216 artificial example from the paper in-20.m out-20.m 19.79 19.98 9.50 104.79 6.93 8.77 6.85 11.42 8.71 1841.74 4 9 6144 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 45.41 43.41 2739.10 7 20 19480 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 45.87 43.24 2756.84 7 20 19480 random groves, [x^n y^(2n)] in-23.m out-23.m >30h 529.80 10946.79 >30h 166.86 403.41 173.14 170.91 202.49 7004.39 10 32 51904 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 78485.99 >30h >30h 7 27 31440 random groves, [x^(2n) y^(2n)] in-25.m out-25.m 873.93 >33h 1125.10 >30h 168.78 244.90 158.93 167.70 193.23 6996.08 10 32 51904 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 >30h >30h >30h 6 23 13224 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 >30h >30h >30h 12 76 89360 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 >30h >30h >30h 12 76 89752 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 >30h >30h >30h 12 76 90272 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 >30h >30h >30h 12 76 89752 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 >30h >30h >30h 12 74 87664 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 >30h >30h >30h 12 74 87664 knight walks ending at (-1,1) in-33.m out-33.m 7754.31 8209.88 34464.58 >30h 8528.18 7808.53 72216.13 >30h >30h >30h 12 74 86952 knight walks ending at (1,-1) in-34.m out-34.m 7436.03 10732.05 34075.48 >30h 10663.64 7756.55 71008.12 >30h >30h >30h 12 74 86952 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 34.83 16.11 992.58 4 9 3592 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 29.22 13.70 1852.53 3 9 3600 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 23.17 17.56 795.27 3 9 3520 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 23.13 11.19 834.99 3 11 4200 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 70.45 45.13 2220.32 3 11 4056 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 86.82 55.38 1995.38 4 13 5104 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 31.08 21.17 873.72 3 12 4432 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 70.97 46.69 2069.46 3 12 4576 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 33.66 23.73 1348.67 4 9 3592 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 0.63 0.60 470.72 3 5 3072 diagonal of 3d-rooks in-45.m out-45.m 27.89 30.74 65.50 206.58 1.51 1.59 2.50 2.43 2.40 1538.17 4 21 15688 diagonal of 3d-rooks (variation) in-46.m out-46.m 4838.00 4986.07 8019.37 >30h 543.69 580.05 479.52 >30h >30h >30h 6 45 49352 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 1.42 1.43 1120.87 3 10 3424 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 5.64 6.22 1888.39 4 30 22552 diagonal of 3d-rooks (variation) in-49.m out-49.m 12109.41 12318.27 39640.75 >30h 1252.31 1452.92 1186.72 >30h >30h >30h 6 71 92552 diagonal of 3d-queens in-50.m out-50.m 2.87 3.48 1.59 19.93 0.42 0.46 0.67 0.86 0.75 554.30 3 5 3072 diagonal of 3d-rooks in-51.m out-51.m 31.38 28.82 42.98 182.97 1.40 1.53 2.39 2.39 2.72 2007.43 4 21 15688 diagonal of 3d-rooks (variation) in-52.m out-52.m 5226.95 4912.46 8242.97 >30h 536.11 602.07 479.23 >30h >30h >30h 6 45 49352 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 0.85 0.89 551.16 3 10 3424 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.32 4.47 2233.15 4 30 22552 diagonal of 3d-rooks (variation) in-55.m out-55.m 11797.54 11598.18 38827.70 >30h 1260.61 1453.87 1201.81 >30h >30h >30h 6 71 92552 diagonal of 3d-queens in-56.m out-56.m 2.80 2.77 1.60 22.96 22.69 1.55 2.58 0.72 0.73 489.17 3 5 2952 diagonal of 3d-rooks in-57.m out-57.m 31.48 32.27 42.25 198.90 201.68 42.73 31.40 2.56 2.42 1532.73 4 21 15352 diagonal of 3d-rooks (variation) in-58.m out-58.m 5195.78 5082.99 8270.46 >30h 571.67 8262.68 5086.82 >30h >30h >30h 6 45 49048 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 1.40 1.43 1077.43 3 10 3424 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 5.90 6.06 1904.77 4 30 22552 diagonal of 3d-rooks (variation) in-61.m out-61.m 11805.01 11975.58 39649.67 >30h 1268.54 1416.92 1203.11 >30h >30h >30h 6 71 92552 diagonal of 3d-queens in-62.m out-62.m 95.64 8.89 42.94 400.03 2.47 2.52 94.70 2.59 3.28 772.53 5 14 10128 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 57.61 57.71 3486.60 8 60 87760 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 1.59 1.24 1010.77 3 4 2712 2-1-1 diagonal of 3d-rooks (variation) in-66.m out-66.m >30h 1166.03 >30h >30h 183.22 183.68 242.61 111.48 75.88 6271.12 9 93 167008 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 57583.62 61792.83 >30h 4 40 24936 randomly generated input in-69.m out-69.m 216.96 243.07 466.36 1374.09 249.16 202.67 989.00 51819.31 54077.99 >30h 4 40 24360 randomly generated input in-70.m out-70.m 221.35 45.30 436.84 1232.80 43.09 38.34 26.76 1133.48 200.49 6024.10 4 40 24144 randomly generated input in-71.m out-71.m 37.21 238.57 447.21 3060.84 48.05 32.82 27.33 933.03 205.61 5548.89 4 40 24632 randomly generated input in-72.m out-72.m 227.78 257.81 494.57 1357.72 263.46 210.24 1012.61 57982.13 64668.30 >30h 4 40 24752 randomly generated input in-73.m out-73.m 36.77 231.64 351.79 2540.32 44.68 49.84 26.82 1487.15 225.44 5850.57 4 40 24120 randomly generated input in-74.m out-74.m 225.23 242.18 438.31 1319.19 235.85 191.66 1185.38 51913.45 54944.86 >30h 4 40 24104 randomly generated input in-75.m out-75.m 2.01 1.78 1.60 6.98 1.68 1.90 1.35 3.71 2.12 37.42 3 4 2776 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 7.89 2.51 101.73 3 5 3392 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 9.11 5.46 118.09 3 8 4680 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 12.41 5.28 223.65 3 6 4000 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 6.43 6.29 383.01 5 16 13368 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 12.91 12.04 553.63 5 20 17680 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 7.25 6.11 386.41 5 15 13120 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 11.88 10.99 708.43 5 18 13688 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 26.39 23.50 399.55 5 24 21328 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 43.66 27.27 1132.38 5 24 21328 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.65 5.34 190.02 5 15 12936 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 11.99 10.68 322.24 5 18 15600 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 21.39 15.43 381.87 5 24 21328 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 27.83 17.88 625.52 5 24 21328 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.51 5.31 198.36 5 16 13848 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 11.66 10.22 347.50 5 19 16512 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 5.19 5.03 768.18 3 4 2928 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 0.14 0.18 47.81 2 3 2160 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 1.02 1.08 241.80 4 10 7496 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 1.50 1.60 248.73 4 10 7496 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 4.57 4.31 401.69 6 15 16032 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 1627.46 1869.53 >30h 4 11 9464 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 4.78 4.78 419.63 6 15 16032 1-3-1 diagonal of Szego's ratfun