CS 830b: Algorithms for recurrences, differential equations, and the automatic proof of identities
Éric Schost, Computer Science Department
Lectures: MC 320, Monday, 9:30 am - 11:30 am.
Office Hours: MC 415, Tuesday and Wednesday, 9:30 am - 11 am.
Phone: 519 661 2111 ext 86994 (e-mail contact preferred!)
Representing functions or sequences on a computer is hard. The good
data structures are not the functions themselves, but rather the
equations that define them. This course will present algorithms for
handling functions or sequences given by linear differential equations
and recurrences. We will cover the following (tentative) list of
- Basic algorithms on power series: multiplication, inversion, composition.
- Further algorithms: Newton iteration, Padé and Hermite-Padé approximants.
- Various aspects of the notion of "solving" linear differential equations and recurrences.
- Discovering and proving identities.
- Extension to multivariate settings and non-commutative Gröbner bases.
- Lecture 1
Introduction, polynomial multiplication, rational generating series
- Lecture 2
Newton iteration: inverse, exponential, first-order differential equations
- Lecture 3
D-finiteness and P-recursiveness
- Lecture 4
- Lecture 5
Definite hypergeometric summation
- Lecture 6
- March 23: slides are online for lecture 6.
- March 16: slides are online for lecture 5.
- March 9: slides are online for lecture 4.
- March 3: slides are online for lecture 3.
- Feb. 18: more papers for the oral presentation are online.
- Feb. 10: the first papers for the oral presentation are online.
- Feb. 10: updated slides for lecture 2.
- Jan. 28: slides are online for lectures 1 and 2.
- There is no class on January 7th. The first class is on Monday, January 14th.
- Modern Computer Algebra, by Joachim von zur Gathen and
Jürgen Gerhard, Cambridge University Press, 1999.
- A=B, by Marko Petkovsek, Herbert Wilf and Doron Zeilberger,
There is no quizz or midterm exam. Students will choose a paper in a
list, write a report and give an oral presentation.
Remark: I am not asking you to read the papers in their
integrality; some are too long. Once you have chosen a topic of
interest, you should contact me; we will decide exactly what content is
suitable for presentation.
- D. J. Bernstein, Scaled remainder trees.
- V. Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields (proc. ISSAC'99).
- R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series (Journal of the ACM , 25(4):581-595, 1978).
- C. Umans, Fast polynomial factorization, modular composition, and multipoint evaluation of multivariate polynomials in small characteristic (proc. STOC'08).
- A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, E. Schost and A. Sedoglavic,
Fast computation of power series solutions of systems of differential equations
- S. Gerhold and M. Kauers,
A procedure for proving special function inequalities involving a discrete parameter
- G. Almkvist and D. Zeilberger,
The method of differentiating under the integral sign.
(Journal of Symbolic Computation, 10: 571-591, 1990).
- H. Wilf and D. Zeilberger
Rational functions certify combinatorial identities, (J. Amer. Math. Soc. 3, 147-158, 1990).
- H. Cheng, G. Hanrot, E. Thomé, E. Zima, P. Zimmermann
Time- and space-efficient evaluation of some hypergeometric constants
- F. Chyzak
An extension of Zeilberger's fast algorithm to general holonomic functions
Discrete Mathematics 217(1-3): 115-134 (2000)