pipette
ENEnglish

Faster Stable Numerical Polynomial Multiplication

Hong Duc Bui

Preprint

En palabras de los autores

In the preprint [vdH08], van der Hoeven considers the problem of multiplying two polynomials with floating-point coefficients, and give an algorithm to compute the product with small relative Newton error in time , where is the degree and is the required precision. In this paper, we describe a significantly simpler algorithm with the same time complexity and error bound. Independently, Bringmann and Cassis considered the near-convex min-plus convolution problem in [BC23a], and presented an algorithm to solve that problem. We observe that our algorithm can be adapted to that problem to speed up Bringmann and Cassis' algorithm by a logarithmic factor.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 29 pages, 7 figures