Homotopy techniques for multiplication modulo triangular sets

We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li et al. (2007), we propose an algorithm that relies on homotopy and fast evaluation–interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given notably to additions of algebraic numbers in small characteristic.

► Quasi-linear time algorithms for multiplication modulo certain triangular sets.
► Fast multiplication modulo Cauchy modules; applications in effective Galois theory.
► Fast multiplication of exponential generating series in positive characteristic.
► Fast computation of the composed sum of two polynomials.
► New quasi-linear time algorithm for univariate polynomial multiplication.