On the complexity of multivariate blockwise polynomial multiplication

Joris Van Der Hoeven; Grégoire Lecerf

doi:10.1145/2442829.2442861

On the complexity of multivariate blockwise polynomial multiplication

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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 ( s^1:5337) ring operations, where s denotes the number of all the monomials of total degree at most 2d.

Original language	English
Title of host publication	ISSAC 2012 - Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation
Pages	211-218
Number of pages	8
DOIs	https://doi.org/10.1145/2442829.2442861
Publication status	Published - 1 Dec 2012
Event	37th International Symposium on Symbolic and Algebraic Computation, ISSAC 2012 - Grenoble, France Duration: 22 Jul 2012 → 25 Jul 2012

Publication series

Name	Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Conference

Conference	37th International Symposium on Symbolic and Algebraic Computation, ISSAC 2012
Country/Territory	France
City	Grenoble
Period	22/07/12 → 25/07/12

Keywords

Algorithm
Evaluation-interpolation
Multivariate power series
Sparse polynomial multiplication

Access to Document

10.1145/2442829.2442861

Cite this

@inproceedings{3d547b8e58dc4a0eaf18808f8e4f90ae,

title = "On the complexity of multivariate blockwise polynomial multiplication",

abstract = "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.",

keywords = "Algorithm, Evaluation-interpolation, Multivariate power series, Sparse polynomial multiplication",

author = "\{Van Der Hoeven\}, Joris and Gr{\'e}goire Lecerf",

year = "2012",

month = dec,

day = "1",

doi = "10.1145/2442829.2442861",

language = "English",

isbn = "9781450312691",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

pages = "211--218",

booktitle = "ISSAC 2012 - Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation",

note = "37th International Symposium on Symbolic and Algebraic Computation, ISSAC 2012 ; Conference date: 22-07-2012 Through 25-07-2012",

}

Van Der Hoeven, J & Lecerf, G 2012, On the complexity of multivariate blockwise polynomial multiplication. in ISSAC 2012 - Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 211-218, 37th International Symposium on Symbolic and Algebraic Computation, ISSAC 2012, Grenoble, France, 22/07/12. https://doi.org/10.1145/2442829.2442861

On the complexity of multivariate blockwise polynomial multiplication. / Van Der Hoeven, Joris ; Lecerf, Grégoire.
ISSAC 2012 - Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. 2012. p. 211-218 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the complexity of multivariate blockwise polynomial multiplication

AU - Van Der Hoeven, Joris

AU - Lecerf, Grégoire

PY - 2012/12/1

Y1 - 2012/12/1

N2 - 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.

AB - 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.

KW - Algorithm

KW - Evaluation-interpolation

KW - Multivariate power series

KW - Sparse polynomial multiplication

U2 - 10.1145/2442829.2442861

DO - 10.1145/2442829.2442861

M3 - Conference contribution

AN - SCOPUS:84870247099

SN - 9781450312691

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 211

EP - 218

BT - ISSAC 2012 - Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation

T2 - 37th International Symposium on Symbolic and Algebraic Computation, ISSAC 2012

Y2 - 22 July 2012 through 25 July 2012

ER -

On the complexity of multivariate blockwise polynomial multiplication

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this