CS 829b: Polynomial systems: geometry and algorithms

Outline

Many algorithms for systems of polynomial equations rely on rewriting techniques. Typical examples are Gröbner bases techniques: one introduces a monomial order, so that multivariate polynomials become of rewriting rules; to compute a Gröbner basis, one introduces new rules (polynomials) until all conflicts (syzygies) are solved.

This point of view has proved quite powerful, but it hides some simple and useful geometric facts: polynomial equations describe algebraic varieties, and the geometry of those varieties (their dimension or degree) should be used as a guide to develop algorithms.

The goal of this course is to introduce a family of algorithms (geometric resolution) which can be easily understood in geometric terms. The basic operations look as follows: knowing two points (1), we manage to reconstruct a curve going through them (2), intersect with a new equation (3), leaving us ready to enter the next step (4).

Contents

This course will describe the algorithms involved in this kind of process, and the mathematical notions necessary to understand and analyze them. We will first review (or introduce, when needed) some background material:

• data structures (primitive element representation),
• reduction to dimension zero (lifting techniques),
• systems of two equations in two unknows (resultant techniques).

• rational reconstruction (how to recognize that 1+x+x²+x³+... is the development of 1/(1-x)?)
• probability analysis (what's the probability that a polynomial vanishes at a random assignment of the variables?)
• the notion of degree (how many roots should a polynomial system have? how does this notion of "number of roots" generalize?)
• last but not least, the connection with symbolic-numeric techniques.

Prerequisites

Students should be familiar with objects such as matrices, polynomials and ideals, and have some knowledge of classical algorithmic techniques (e.g., divide-and-conquer). Knowledge of concepts such as fast polynomial multiplication, resultants or Hensel-lifting is helpful, but not mandatory.

Links

• Ideals, varieties, and algorithms, by Cox, Little and O'Shea.
• Using algebraic geometry, by Cox, Little and O'Shea.
• Numerical solution of polynomial systems arising in engineering and science, by Sommese and Wampler.
• Modern computer algebra, by von zur Gathen and Gerhard.

Slides

• Lecture 1 Introduction, useful concepts
• Lecture 2 Degree and height
• Lecture 3 Euclidean algorithm and resultant
• Lecture 4 Power series, evaluation, interpolation, bivariate systems
• Lecture 5 Newton iteration
• Lecture 6 Newton iteration (continued), straight-line programs
• Lecture 7 Putting the pieces together
• Lecture 8 Univariate root-finding