Inthe present paper, some polynomial multiplication circuits being efficient either in complexityand 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о1 + ... + 2°s,n1 > ... > ns, over a ring with invertible 2 can be implemented via M(n1) + ... + M(ns) ++O(n) arithmetic operations over the ring with the depth max(D(ni)} + O(log n), where iM(k) and D(k) are respectively the complexity and the depth of the modulo x2 + 1 multiplicationcircuit. As another example, the truncated DFT of order n (i. e. the DFT oforder 2^log2 reduced to the vectors of dimension n) can be implemented by a circuit ofcomplexity 1,5n log2 n + O(n) and memory size n +1.
Download file
Counter downloads: 70
- Title Regular estimates for the complexity of polynomial multiplication and truncated Fourier transform
- Headline Regular estimates for the complexity of polynomial multiplication and truncated Fourier transform
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(14)
- Date:
- DOI
Keywords
арифметические схемы, сложность, глубина, объем памяти, умножение, дискретное преобразование Фурье (ДПФ), arithmetic circuits, complexity, depth, memory size, multiplication, Discrete Fourier TransformAuthors
References
Гашков С. Б., Сергеев И. С. О сложности и глубине булевых схем для умножения и инвертирования в некоторых полях GF(2n) // Вестник МГУ. Сер. 1. Математика. Механика. 2009. №4. С. 3-7.
Mateer T. Fast Fourier algorithms with applications // Ph. D. Thesis. Clemson University, 2008.
Гашков С. Б., Сергеев И. С. Алгоритмы быстрого преобразования Фурье // Дискретная математика и ее приложения. Ч. V. М.: Изд-во Института прикладной математики РАН, 2009. С. 3-23.
Van der Hoeven J. Notes on the truncated Fourier transform // Tech. Report. Univ. Paris- Sud, Orsay, France, 2005.
Crandall R. and Fagin B. Discrete weighted transforms and large-integer arithmetic // Math. Comput. 1994. V.62. P. 305-324.
Сергеев И. С. Регуляризация некоторых оценок сложности умножения многочленов // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (Москва, 2009 г.). Ч. II. М.: Изд-во Института прикладной математики РАН, 2009. С. 26-32.
Schonhage A. Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients // Proc. EuroCAM-82 (Marseille, France). LNCS. V. 144. Berlin; Heidelberg; NY: Springer, 1982. P. 3-15.
Cooley J. and Tukew J. An algorithm for the machine calculation of complex Fourier series // Math. Comp. 1965. V. 19. P. 297-301.
Von zur Gathen J. and Gerhard J. Modern computer algebra. Cambridge: Cambridge University Press, 1999. 768 p.
Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во Моск. ун-та, 1984. 138 с.
Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
Bernstein D. J. Fast multiplication and its applications // Algorithmic Number Theory, MSRI Publ. 2008. V. 44. P. 325-384.
Schonhage A. Schnelle multiplikation von polynomen tiber ktirpern der charakteristik 2 // Acta Inf. 1977. V. 7. P. 395-398.
Cantor D. and Kaltofen E. On fast multiplication of polynomials over arbitrary algebras // Acta Inf. 1991. V. 28. No. 7. P. 693-701.
Harvey D. and Roche D. S. An in-place truncated Fourier transform and application to polynomial multiplication // Proc. ISSAC 2010 (Munich, Germany). NY: ACM Press, 2010. P. 325-329.
Van der Hoeven J. The truncated Fourier transform and applications // Proc. ISSAC 2004 (Santander, Spain). NY: ACM Press, 2004. P. 290-296.
Regular estimates for the complexity of polynomial multiplication and truncated Fourier transform | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 4(14).
Download full-text version
Download fileCounter downloads: 211