On the complexity of multivariate blockwise polynomial multiplication | Zendy

Joris van der Hoeven | Zendy; Grégoire Lecerf | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the complexity of multivariate blockwise polynomial multiplication

Author(s) -

Joris van der Hoeven,

Grégoire Lecerf

Publication year - 2012

Publication title -

hal (le centre pour la communication scientifique directe)

Language(s) - English

Resource type - Conference proceedings

DOI - 10.1145/2442829.2442861

Subject(s) - multiplication (music) , mathematics , monomial , ring (chemistry) , polynomial , degree (music) , product (mathematics) , multivariate statistics , fast fourier transform , discrete mathematics , combinatorics , algorithm , statistics , mathematical analysis , chemistry , physics , geometry , organic chemistry , acoustics

In this article, we study the problem of multiplying two multivariate polynomials which are somewhat but not too sparse, typically like polynomials with convex supports. We design and analyze an algorithm which is based on blockwise decomposition of the input polynomials, and which performs the actual multiplication in an FFT model or some other more general so called "evaluated model". If the input polynomials have total degrees at most d, then, under mild assumptions on the coefficient ring, we show that their product can be computed with O (s1.5337) ring operations, where s denotes the number of all the monomials of total degree at most 2d.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research