RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Prikl. Diskr. Mat., 2011, Number 4(14), Pages 72–88 (Mi pdm347)

Computational Methods in Discrete Mathematics

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

I. S. Sergeev

M. V. Lomonosov Moscow State University, Moscow, Russia

Abstract: 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}+…+2^{n_s}$, $n_1>…>n_s$, over a ring with invertible 2 can be implemented via $M(n_1)+…+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$.

Keywords: arithmetic circuits, complexity, depth, memory size, multiplication, Discrete Fourier Transform.

Full text: PDF file (669 kB)
References: PDF file   HTML file
UDC: 519.7

Citation: I. S. Sergeev, “Regular estimates for the complexity of polynomial multiplication and truncated Fourier transform”, Prikl. Diskr. Mat., 2011, no. 4(14), 72–88

Citation in format AMSBIB
\Bibitem{Ser11} \by I.~S.~Sergeev \paper Regular estimates for the complexity of polynomial multiplication and truncated Fourier transform \jour Prikl. Diskr. Mat. \yr 2011 \issue 4(14) \pages 72--88 \mathnet{http://mi.mathnet.ru/pdm347} 

• http://mi.mathnet.ru/eng/pdm347
• http://mi.mathnet.ru/eng/pdm/y2011/i4/p72

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Veretekhina S.V., Zhuravlyov M.S., Shmakova E.G., Soldatov A.A., Kotenev A.V., Kashirin S.V., Medvedeva A.V., “Analog Sound Signals Digitalization and Processing”, Mod. J. Lang. Teach. Methods, 8:3 (2018), 45–63
2. S. B. Gashkov, I. S. Sergeev, “Umnozhenie”, Chebyshevskii sb., 21:1 (2020), 101–134
•  Number of views: This page: 204 Full text: 62 References: 25