CS 780 Course Description | SCS | UW

[Please remove <h1>]


The goal of this course is a deep investigation into fundamental problems of symbolic computation. These may include algorithms for linear, and differential systmes of symbolic equations, symbolic integration, factoring polymonials, and symbolic-numeric algorithms. We will also invertigate the basic data structures and data types for algebraic objects and operations, and consider issues in the design of computer algebra systems.


Algorithms for Computer Algebra by K.O. Geddes, S.R. Czapor, and G. Labahn, Kluwer Academic Publishers, 1991. Modern Computer Algebra by J. von sur Gathen and J. Gerhard, Cambridge University Press, 1999. Ideals, Varieties, and Algorithms, 2nd ed., by D. Cox, J. Little and D. O'Shea, Springer-Verlag, 1996. Symbolic Integration 1 --Transcendental Functions (Algorithms and Computations in Mathematics), Vol 1, by M. Bronstein, Springer-Verlag, 1996.


Three hours of lecture per week.


Compute Algebra Systems (6 hrs)

Implementation issues in fundamental data types. Type systems for algebraic objects. Interpreted and compiled computer algebra languages. Garbage collection. Survey of key aspects of Maple, Mathematica, Magma, etc.

Polynomial Factorization (6 hrs)

Factoring univariate polynomials over finite fields. Factoring univariate integer polynomials, LLL and Van Hoeij's algorithms. Factoring multivariate polynomials.

Symbolic Integration (6 hrs)

Risch's algorithm. Hermite's method.

Symbolic Linear Algebra (6 hrs)

Systems of equations over the integers and rationals. Matrix polynomials. Sparce matrices and black box matrices-Wiedemann's algorithm. Fraction free algebras.

Symbolic Numeric Algorithms for Polynomials (6 hrs)

Approximate GCD of polynomials. Approximate factorization and decomposition of polynomials.

Gröbner Bases (6 hrs)

Monomial orders. Division algorithm for multivariate polynomials. Gröbner bases and S-polynomials. Buchberger's algorithm.

Skew Polynomials and Ore Algebras (3 hrs)

GCRDs and LCLMs in skew polynomial rings. Factorization and LCLM-decomposition of skew polynomials. Matrices of skew polynomials. Linear Ordinary Differential Equations.