Watch a video introduction to the course on YouTube.
This course is an introduction to the use of computers for symbolic mathematical computation, which involves such traditional algebraic (as opposed to numerical) computations as solving linear equations (exactly), analytic differentiation and integration of functions, and analytic solution of differential equations. The course is designed to expose students to the programming languages and data structures used for symbolic computation, the concepts from modern algebra which are applied to the development of algorithms for symbolic computation, and various applications of symbolic computation.
CS 487 is normally completed in a student's fourth year.
Prerequisites: CS 234 or 240 or SE 240; Honours Mathematics or Software Engineering students only.
Cross-listed: CM 433
Algorithms for Computer Algebra, by K. Geddes, S. Czapor and G. Labahn, Kluwer Academic Publishers, 1992.
3 hours of lectures per week. Normally available in Winter.
Symbolic versus numeric computation. History of systems for symbolic computation.
Rings, integral domains, Euclidean domains, fields, quotient fields, finite fields.
The need for simplification. Normal forms for polynomials. Data structures for integers and polynomials. Rational functions and power series.
Homomorphisms. Chinese remainder algorithm and interpolation. The Hensel construction.
Generalizations of the Euclidean algorithm for multivariate polynomials. Modular algorithms. Hensel techniques. Heuristic techniques.
Berlekamp’s method. Hensel techniques. Heuristic techniques.
Variations of Gaussian elimination. Modular techniques. Systems of polynomial equations.
Hermite/Rothstein method for rational functions. The Risch algorithm for transcendental and algebraic functions.
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-uops@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Wednesday, 15-Feb-2012 12:44:34 EST
