François Charton (Facebook AI Research, Paris)

Given a computer algebra problem described by polynomials with rational coefficients, I will present various tools that help measuring the cost of solving it, where cost means giving bounds for the degrees and heights (i.e. bit-sizes) of the output in terms of those of the input data. I will detail an arithmetic Bézout inequality and give some applications to zero-dimensional polynomial systems. I will also speak about the Nullstellensatz and Perron’s theorem for implicitization, if time permits.

Users of computer algebra systems expect these systems to be able to perform numerical calculations to arbitrary precision. They may also, perhaps somewhat optimistically, assume that the outputs will be accurate or even that they will have the status of rigorously proven results. This mini-course will explore ways to achieve these goals when computing solutions of ordinary differential equations. The focus will be on Taylor methods, a family of numerical methods that are well-suited to arbitrary precision computations and can be adapted to provide rigorous error bounds. More specifically, we will concentrate on linear differential equations whose coefficients depend polynomially on the time variable, and examine algorithms dedicated to this class of equations. This is motivated by applications in fields ranging from combinatorics or theoretical physics to algebraic geometry and number theory that require evaluating solutions of equations of this type to accuracies in the thousands of decimal f igures. We will also discuss some practical implementation results and applications.

This course is dedicated to core algorithms of polyhedral geometry and covers theoretical aspects as well as practical ones. We will start with rational polyhedra, their projections and the conversions between their different types of representations. We will continue with a tour of the different questions related to the lattice points of rational polyhedra : checking existence, counting these points, describing them, in particular for the case of parametric polyhedra. Practical applications of rational polyhedra and lattice polyhedra require, at least in theory, to perform quantifier elimination; we will see how this is done in the context of optimizing compilers.