Computer algebra deals with exact computations with mathematical formulas. Often, these formulas are very large and often they can be rewritten as polynomials or rational functions in well chosen variables. Direct computations with such expressions can be very expensive and may lead to a further explosion of the size of intermediate expressions. Another approach is to systematically work with evaluations. For a given problem, like inverting a matrix with polynomial coefficients, evaluations of the solution might be relatively cheap to compute. Sparse interpolation is a device that can then be used to recover the result in symbolic form from sufficiently many evaluations. In our talk, we will survey a few classical and a new approach for sparse interpolation, while mentioning a few links with other subjects.

Note: partially based on joint work with Grégoire Lecerf

Occasion: LIX pole-wide seminar, December 12, 2022

Documents: slideshow, TeXmacs source