Consider two polynomials and with multiple precision floating point coefficients. Although the product can in principle be computed efficiently using FFT multiplication, this algorithm is numerically stable only if the coefficients of are of the same order of magnitude and similarly for . In this paper, we present a new asymptotically fast multiplication algorithm which has a “better” numerically stability. We also provide some theoretical support for what we feel to be “better”, by introducing the concept of “relative Newton error”.

Keywords: polynomial, floating point number, multiplication, algorithm, FFT

A.M.S. subject classification: 65T50, 42-04, 68W30

View: Html, TeXmacs, Pdf, BibTeX

Remark. Unfortunately, an annoying error slipped into the preprint: the bound (3) is wrong. Consequently, the complexity estimates in the paper only work in one direction. Nevertheless, we have implemented a first version of the algorithm in Mathemagix and the approach works well in practice. In particular, we implemented a method for computing the roots of complex polynomials, and observed a good asymptotic complexity (together with a bad constant factor).