Evaluation, interpolation and multivariate multiplication
Éric Schost (University of Western Ontario, Canada)
Efficient algorithms are known for operations such as univariate polynomial multiplication or Euclidean division; the main challenge is to close gaps between linear time and linear-up-to-logarithmic-factors. For multivariate problems, the situation is less clear, as many algorithms involve overheads that are exponential in the dimension.
This talk will present algorithms for multivariate evaluation and interpolation, with an application to the multiplication of multivariate power series, that manage to avoid such issues.
Based on joint work with Joris van der Hoeven.
Talk slides (PDF).