Simple multivariate polynomial multiplication (Q1346473): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jsco.1994.1042 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2028444458 / rank | |||
Normal rank |
Latest revision as of 00:12, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Simple multivariate polynomial multiplication |
scientific article |
Statements
Simple multivariate polynomial multiplication (English)
0 references
4 April 1995
0 references
Let \(u= u(x_1, \dots, x_m)\) and \(v= v(x_1, \dots, x_m)\) be \(m\)-variate polynomials over a field \(F\) and let \(N= c^m\), where \(c\) is chosen so that \(c\geq 2\deg_{x_i} (u)+ 1,2 \deg_{x_i} (v)+ 1\) \((1\leq i\leq m)\). It is known that the product \(uv\) can be computed in time \(O(N \log N\log \log N)\). In this note it is shown that it can be computed in time \(O(N \log N)\), the bound already known to hold when \(F\) supports FFT at \(2^{\lceil \log_2 N\rceil}\).
0 references
multivariate polynomials
0 references
product
0 references