# Modular Algorithms in Symbolic Summation and Symbolic Integration

Springer Science & Business Media, 2004 - Computers - 224 pages
This 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 References 207 Index 217 Copyright