Publication Details
Title: Simple Multivariate Polynomial Multiplication
Author: V. Pan
Group: ICSI Technical Reports
Date: August 1993
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-93-003.pdf
Overview:
We observe that polynomial evaluation and interpolation can be performed fast over a multidimensional grid (lattice), and we apply this observation in order to obtain the bounds M(c,m) ≤ (c^m)(1 + m + 1.5m + 2(log subscript 2)c) over the fields of constants supporting FFT on c points, c being a power of 2, and M (c, m) = 0[N log N log log c], over any field, where N = c^m, and M (c, m) denotes the number of arithmetic operations required in order to multiply (over any field F) a pair of m-variate polynomials whose product has degree at most c - 1 in each variable, so that M (c, m) = 0(N log N) if c=0(1), m → ∞ (over any field F), versus the known bound of O (N log N log log N).
Bibliographic Information:
ICSI Technical Report TR-93-003
Bibliographic Reference:
V. Pan. Simple Multivariate Polynomial Multiplication. ICSI Technical Report TR-93-003, August 1993
Author: V. Pan
Group: ICSI Technical Reports
Date: August 1993
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-93-003.pdf
Overview:
We observe that polynomial evaluation and interpolation can be performed fast over a multidimensional grid (lattice), and we apply this observation in order to obtain the bounds M(c,m) ≤ (c^m)(1 + m + 1.5m + 2(log subscript 2)c) over the fields of constants supporting FFT on c points, c being a power of 2, and M (c, m) = 0[N log N log log c], over any field, where N = c^m, and M (c, m) denotes the number of arithmetic operations required in order to multiply (over any field F) a pair of m-variate polynomials whose product has degree at most c - 1 in each variable, so that M (c, m) = 0(N log N) if c=0(1), m → ∞ (over any field F), versus the known bound of O (N log N log log N).
Bibliographic Information:
ICSI Technical Report TR-93-003
Bibliographic Reference:
V. Pan. Simple Multivariate Polynomial Multiplication. ICSI Technical Report TR-93-003, August 1993