# CS 780 Advanced Symbolic Computation

## Objectives

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.

## References

*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.

## Schedule

Three hours of lecture per week.

## Outline

### 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.