CISC 822: Algebraic Algorithms

Catalog Description:
Algorithms for exact symbolic computation with integers of arbitrary size, polynomials, matrices, fields of quotients, and modular domains. Key algorithmic problems: GCD, factorization, and solution of equations. Key techniques: Chinese remaindering, Hensel lifting, and transforms (such as FFT).

Current Texts:
Modern Computer Algebra, Second Edition
von zur Gathen and Gerhard
Cambridge University Press, 2003

Goals:
Systems of polynomial equations arise in all scientific and engineering disciplines. In computer science itself, for example, the areas of theorem proving and robot motion planning particularly involve modelling of problems as systems of polynomial equations. Algorithms for the exact solution (as opposed to approximate or "numeric" solution) of such systems will be the core subject of this course.

Among the tools used are algorithms for manipulating mathematical objects such as arbitrary length integers, univariate and multivariate polynomials, rational functions, and matrices. We will discuss correctness issues, analyze algorithm costs, and consider implentation issues. Our LinBox library for high performance exact linear algebra computation with large sparse integer matrices will be a prime example and research topics relevant to it's further development will be emphasized.

Implementations of these algorithms are the core components of computer algebra systems such as Axiom, the 3 M's (Macsyma, Maple, Mathematica), and Reduce. With these systems computer science has changed the nature of computational science. Computer algebra systems have revolutionized the working environments of scientists and engineers everywhere.

Contents:

• Arithmetic of polynomials, greatest common divisors
• Modular computation, evaluation/interpolation
• Chinese remaindering and Hensel lifting
• Sparse interpolation, factorization, lattice reduction
• Matrix computations