Regular estimates for the complexity of polynomial multiplication and truncated Fourier transform

I. S. Sergeev

Prikladnaâ diskretnaâ matematika, no. 4 (2011), pp. 72-88.

Résumé

In the present paper, some polynomial multiplication circuits being efficient either in complexity and depth or in complexity and memory size are proposed. Consequently, for instance, the multiplication of polynomials of the sum degree $n-1$, where $n=2^{n_1}+\dots+2^{n_s}$, $n_1>\dots>n_s$, over a ring with invertible 2 can be implemented via $M(n_1)+\dots+M(n_s)+\mathrm O(n)$ arithmetic operations over the ring with the depth $\max_i\{D(n_i)\}+\mathrm O(\log n)$, where $M(k)$ and $D(k)$ are respectively the complexity and the depth of the modulo $x^{2^k}+1$ multiplication circuit. As another example, the truncated DFT of order $n$ (i.e. the DFT of order $2^{\lceil\log_2n\rceil}$ reduced to the vectors of dimension $n$) can be implemented by a circuit of complexity $1,5n\log_2n+\mathrm O(n)$ and memory size $n+1$.

Détail

Keywords: arithmetic circuits, complexity, depth, memory size
Mots-clés : multiplication, Discrete Fourier Transform.

Bibliographie

[1] Van der Hoeven J., “The truncated Fourier transform and applications”, Proc. ISSAC 2004 (Santander, Spain), ACM Press, NY, 2004, 290–296 | MR | Zbl

[2] Harvey D., Roche D. S., “An in-place truncated Fourier transform and application to polynomial multiplication”, Proc. ISSAC 2010 (Munich, Germany), ACM Press, NY, 2010, 325–329

[3] Schönhage A., “Schnelle multiplikation von polynomen über körpern der charakteristik 2”, Acta Inf., 7 (1977), 395–398 | DOI | MR

[4] Cantor D., Kaltofen E., “On fast multiplication of polynomials over arbitrary algebras”, Acta Inf., 28:7 (1991), 693–701 | DOI | MR | Zbl

[5] Bernstein D. J., “Fast multiplication and its applications”, Algorithmic Number Theory (MSRI Publ.), 44 (2008), 325–384 | MR | Zbl

[6] Von zur Gathen J., Gerhard J., Modern computer algebra, Cambridge University Press, Cambridge, 1999, 768 pp. | MR

[7] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, M., 1984, 138 pp.

[8] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986, 384 pp. | MR

[9] Cooley J., Tukew J., “An algorithm for the machine calculation of complex Fourier series”, Math. Comp., 19 (1965), 297–301 | DOI | MR | Zbl

[10] Schönhage A., “Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients”, Proc. EuroCAM-82 (Marseille, France), LNCS, 144, Springer, Berlin–Heidelberg–NY, 1982, 3–15 | MR

[11] Sergeev I. S., “Regulyarizatsiya nekotorykh otsenok slozhnosti umnozheniya mnogochlenov”, Materialy VII molodezhnoi nauchnoi shkoly po diskretnoi matematike i ee prilozheniyam, Ch. II (Moskva, 2009 g.), Izd-vo Instituta prikladnoi matematiki RAN, M., 2009, 26–32

[12] Van der Hoeven J., Notes on the truncated Fourier transform, Tech. Report, Univ. Paris-Sud, Orsay, France, 2005

[13] Crandall R., Fagin B., “Discrete weighted transforms and large-integer arithmetic”, Math. Comput., 62 (1994), 305–324 | DOI | MR | Zbl

[14] Mateer T., Fast Fourier algorithms with applications, Ph. D. Thesis, Clemson University, 2008

[15] Gashkov S. B., Sergeev I. S., “Algoritmy bystrogo preobrazovaniya Fure”, Diskretnaya matematika i ee prilozheniya, Ch. V, Izd-vo Instituta prikladnoi matematiki RAN, M., 2009, 3–23

[16] Gashkov S. B., Sergeev I. S., “O slozhnosti i glubine bulevykh skhem dlya umnozheniya i invertirovaniya v nekotorykh polyakh $GF(2^n)$”, Vestnik MGU. Ser. 1. Matematika. Mekhanika, 2009, no. 4, 3–7 | MR