We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li, Moreno Maza and Schost, 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 to notably addition of algebraic numbers in small characteristic.

Authors: Alin Bostan, Muhammad Chowdhury, Joris van der Hoeven, Éric Schost

Keywords: Triangular sets, multiplication, complexity

View: Pdf, BibTeX