Modular Algorithms in Symbolic Summation and Symbolic Integration

Front Cover
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

Other editions - View all

Common terms and phrases

Bibliographic information