CS 867 - Algorithmic Properties of
University of Western Ontario
Computer Science Department
Date: September 7, 2009
It is a standard problem in mathematical sciences to study which properties of a given structure are preserved in derived structures. A trivial example of such preservation is the fact that every subgraph of a planar graph is itself planar. A more involved example is the fact that, if R is a unique factorization domain, then so is the ring R[x] of univariate polynomials over R. Many algorithms rely on properties that are preserved under certain transformations. For instance, if R is again a unique factorization domain, then the so-called subresultant algorithm reduces polynomial gcd computations in R[x] to number gcd computations in R. In this course, we will discuss the algorithmic properties of R that can be lifted to R[x], with an emphasis on those which help solving systems of equations. In particular, we will discuss the lifting from R to R[x] of prime and primary decomposition of ideals.
Here's a tentative schedule for the lectures.
Then six last lectures cover non-classical subjects that were developed in the last decades by computer algebraists. The theory of regular chains, introduced by M. Kalkbrener in 1991, will be the central notion of this second series. It is recognized today that regular chains are among the most efficient tools for exact solving of systems of algebraic or differential equations.