CS 487 Introduction to Symbolic Computation
Watch a video introduction to the course on YouTube.
Objectives
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.
Intended Audience
CS 487 is normally completed in a student's fourth year.
Related Courses
Prerequisites: CS 234 or 240 or SE 240; Honours Mathematics or Software Engineering students only.
Cross-listed: CM 433
References
Algorithms for Computer Algebra, by K. Geddes, S. Czapor and G. Labahn, Kluwer Academic Publishers, 1992.
Schedule
3 hours of lectures per week. Normally available in Winter.
Outline
Introduction (1 hour)
Symbolic versus numeric computation. History of systems for symbolic computation.
Algebraic Structures (5 hours)
Rings, integral domains, Euclidean domains, fields, quotient fields, finite fields.
Normal Forms and Data Structures (2 hours)
The need for simplification. Normal forms for polynomials. Data structures for integers and polynomials. Rational functions and power series.
Homomorphism Methods (6 hours)
Homomorphisms. Chinese remainder algorithm and interpolation. The Hensel construction.
Greatest Common Divisor Algorithms (6 hours)
Generalizations of the Euclidean algorithm for multivariate polynomials. Modular algorithms. Hensel techniques. Heuristic techniques.
Polynomial Factoring (6 hours)
Berlekamps method. Hensel techniques. Heuristic techniques.
Solution of Equations (4 hours)
Variations of Gaussian elimination. Modular techniques. Systems of polynomial equations.
Symbolic Integration (6 hours)
Hermite/Rothstein method for rational functions. The Risch algorithm for transcendental and algebraic functions.
