ГлавнаяАрхивРегулярные оценки сложности умножения многочленов и усеченного ДПФ

Регулярные оценки сложности умножения многочленов и усеченного ДПФ | Прикладная дискретная математика. 2011. № 4(14).

Строятся схемы для умножения многочленов и усеченного ДПФ (дискретного преобразования Фурье), эффективные с точки зрения сложности и глубины или сложности и объема памяти. Как следствие, умножение многочленов суммарной степени n - 1, где n = 2ni + . . . + 2ns, ni > . . . > ns , над кольцом, в котором обратима двойка, можно выполнить со сложностью M(ni) + . . . + M(ns ) + O(n)арифметических операций в этом кольце и глубиной max{D(ni)} + O(logn), где i M(k) и D(k) - соответственно сложность и глубина схемы умножения по модулю x2 +1. Усеченное ДПФ порядка n (т.е. ДПФ порядка 2^og2nl, приведенное к векторам длины n) можно реализовать схемой сложности 1,5n log2 n + O(n) и объема памяти n + 1.
  • Title Регулярные оценки сложности умножения многочленов и усеченного ДПФ
  • Headline Регулярные оценки сложности умножения многочленов и усеченного ДПФ
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 4(14)
  • Date:
  • DOI
Ключевые слова
арифметические схемы, сложность, глубина, объем памяти, умножение, дискретное преобразование Фурье (ДПФ), arithmetic circuits, complexity, depth, memory size, multiplication, Discrete Fourier Transform
Авторы
Ссылки
Гашков С. Б., Сергеев И. С. О сложности и глубине булевых схем для умножения и инвертирования в некоторых полях 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.
Регулярные оценки сложности умножения многочленов и усеченного ДПФ | Прикладная дискретная математика. 2011. № 4(14).
Регулярные оценки сложности умножения многочленов и усеченного ДПФ | Прикладная дискретная математика. 2011. № 4(14).
Полнотекстовая версия