## Modular Algorithms in Symbolic Summation and Symbolic IntegrationThis work brings together two streams in computer algebra: symbolic integration and summation on the one hand, and fast algorithmics on the other hand. In many algorithmically oriented areas of computer science, theanalysisof- gorithms–placedintothe limelightbyDonKnuth’stalkat the 1970ICM –provides a crystal-clear criterion for success. The researcher who designs an algorithmthat is faster (asymptotically, in the worst case) than any previous method receives instant grati?cation: her result will be recognized as valuable. Alas, the downside is that such results come along quite infrequently, despite our best efforts. An alternative evaluation method is to run a new algorithm on examples; this has its obvious problems, but is sometimes the best we can do. George Collins, one of the fathers of computer algebra and a great experimenter,wrote in 1969: “I think this demonstrates again that a simple analysis is often more revealing than a ream of empirical data (although both are important). ” Within computer algebra, some areas have traditionally followed the former methodology, notably some parts of polynomial algebra and linear algebra. Other areas, such as polynomial system solving, have not yet been amenable to this - proach. The usual “input size” parameters of computer science seem inadequate, and although some natural “geometric” parameters have been identi?ed (solution dimension, regularity), not all (potential) major progress can be expressed in this framework. Symbolic integration and summation have been in a similar state. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

Overview | 6 |

21 Outline | 12 |

22 Statement of Main Results | 13 |

23 References and Related Works | 21 |

24 Open Problems | 24 |

Technical Prerequisites | 27 |

31 Sub resultants and the Euclidean Algorithm | 28 |

71 Application to Hypergeometric Summation | 103 |

72 Computing All Integral Roots Via Factoring | 109 |

73 Application to Hyperexponential Integration | 112 |

74 Modular LRT Algorithm | 116 |

Modular Algorithms for the GosperPetkovšek Form | 121 |

81 Modular GPForm Computation | 134 |

Polynomial Solutions of Linear First Order Equations | 149 |

91 The Method of Undetermined Coefficients | 155 |

32 The Cost of Arithmetic | 33 |

Change of Basis | 41 |

41 Computing Taylor Shifts | 42 |

42 Conversion to Falling Factorials | 49 |

43 Fast Multiplication in the Falling Factorial Basis | 57 |

Modular Squarefree and Greatest Factorial Factorization | 61 |

52 Greatest Factorial Factorization | 68 |

Modular Hermite Integration | 78 |

61 Small Primes Modular Algorithm | 80 |

62 Prime Power Modular Algorithm | 85 |

63 Implementation | 87 |

Computing All Integral Roots of the Resultant | 97 |

92 Brent and Kungs Algorithm for Linear Differential Equations | 158 |

93 Rothsteins SPDE Algorithm | 161 |

94 The ABP Algorithm | 165 |

Generic Case | 169 |

General Case | 174 |

97 Barkatous Algorithm for Linear Difference Equations | 179 |

98 Modular Algorithms | 180 |

Modular Gosper and Almkvist Zeilberger Algorithms | 194 |

101 High Degree Examples | 198 |

207 | |

217 | |

### Other editions - View all

Modular Algorithms in Symbolic Summation and Symbolic Integration Jürgen Gerhard Limited preview - 2004 |

### Common terms and phrases

additions and multiplications algebra Algorithm 7.2 algorithm for computing arithmetic operations asymptotically asymptotically optimal characteristic zero classical arithmetic coefﬁcients Corollary 9.6 cost estimate cost for step degg degree sequence denominator difference equation differential equation Extended Euclidean Algorithm f and g falling factorial basis fast arithmetic ﬁeld field of characteristic ﬁnd G F[x G Z[x Gathen & Gerhard Gosper hence Hensel lifting hyperexponential hypergeometric summation implies input integral roots Lemma Let F log2 logarithmic factors logn lucky prime lucky with respect max-norm less metic Mignotte's bound mod pk modular algorithm modular variant modulo modulo pk monic polynomial monomial basis nonconstant nonzero polynomial normalized operations with classical output polynomial f polynomials of degree proof of Theorem rational function reconstruction recursive result return FAIL return unsolvable single precision primes small primes modular squarefree decomposition squarefree factorization subresultant takes Taylor shift unique unlucky word operations