vestnik Экологический вестник научных центров Черноморского экономического сотрудничества Ecological Bulletin of Research Centers of the Black Sea Economic Cooperation 1729-5459 Кубанский государственный университет RU 686 Научная статья Original article Статьи Article Быстрое преобразование Фурье и решение свёрточных уравнений на группе Гейзенберга над простым полем Галуа FFT and solving of convolution equations on Heisenber group over prime Galua field Деундяк В.М. Деундяк Владимир Михайлович Deundyak Vladimir M. vlade@math.rsu.ru

канд. физ.-мат. наук, доцент кафедры алгебры и дискретной математики института математики, механики и компьютерных наук имени И.И. Воровича Южного федерального университета

 Леонов Д.А. Леонов Дмитрий Александрович Leonov Dmitriy A. tori_92@inbox.ru

аспирант кафедры алгебры и дискретной математики института математики, механики и компьютерных наук имени И.И. Воровича Южного федерального университета

 Южный федеральный университет, Ростов-на-ДонуSouthern Federal University, Rostov-on-Don 30 06 2016 2 46 53 22 03 2016 12 05 2016 30 06 2016 Copyright (c) 2016 Деундяк В.М., Леонов Д.. 2016 Деундяк В.М., Леонов Д.. Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

Fourier method has been used for a long time in many fields of mathematics, physics and engineering sciences on commutative groups. The development of the fast Fourier transform that can significantly speed up the solution of important practical problems is of particular interest. But in comparison with the commutative variant the construction of the fast Fourier transforms for non-commutative groups is more difficult because of the complexity of the dual objects group in terms of which this transformation is constructed. This paper studies Fourier method of solution of convolution equations on finite Heisenberg group $\mathbb{H}(\mathbb{F}_p)$ over Galois field $\mathbb{F}_p$ of a prime power. The fast Fourier transform on this group is built on the basis of reduction to the fast Fourier transform on the cyclic groups, the explicit formulas for forward and inverse transformations are obtained. On the basis of proved formulas an effective algorithm has been developed for solution of convolution equations with the complexity $O(n^{\frac{4}{3}})$, where $n=p^3$ is the power of $\mathbb{H}(\mathbb{F}_p)$. Obtained theoretical results allowed us on the basis of the programming language C# to develop a software implementation of the numerical method for solution of convolution equations on $\mathbb{H}(\mathbb{F}_p)$. The results of numerical experiments are presented in the paper.

Исследуется метод Фурье решения сверточных уравнений на конечной группе Гейзенберга $\mathbb{H}(\mathbb{F}_p)$ над простым полем Галуа $\mathbb{F}_p$. На этой группе построено быстрое преобразование Фурье на основе редукции к быстрому преобразованию Фурье на циклических группах, получены явные формулы для прямого и обратного преобразований, разработан алгоритм решения сверточных уравнений со сложностью $O(n^{4/3})$, где $n=p^3$ — мощность группы $\mathbb{H}(\mathbb{F}_p)$. На основе полученных теоретических результатов разработана программная реализация численного метода решения сверточных уравнений на $\mathbb{H}(\mathbb{F}_p)$ и приведены результаты численных экспериментов.

 группа Гейзенберга свёрточные уравнения метод Фурье быстрое преобразование Фурье Heisenberg group convolution equations Fourier method fast Fourier transformation Rockmore D. Recent Progress and Applications in Group FFTs // Computational Noncommutative Algebra and Applications. 2004. Vol. 136. P. 227-254. Leinz R. Using representations of the dihedral groups in the design of early vision filters // Acoustics, Speech, and Signal Processing. 1993. Vol. 5. P. 165-168. Загороднов И.А., Тарасов Р.П. Задача дифракции на телах с некоммутативной конечной группой симметрий и численное ее решение // Журн. вычисл. математики и матем. физики. 1997. Т. 37. No 10. С. 1246-1262. . Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki , 1997, vol. 37, no. 10, pp. 1246-1262. (In Russian)] Howe R. On The role of the Heisenberg group in harmonic analysis // Bulletin of the American Mathematical Society. 1980. Vol. 3. No 2. P. 821-843. Bump D., Diaconis P., Hicks A., Miclo L., Widom H. An exercise (?) in Fourier analysis on the Heisenberg group // ArXiv e-prints. 2015. P. 1-24. Terras A. Fourier analysis on finite groups and applications. Cambridge University Press, 1999. 456 c. Beth T. On the Computational Complexity of the General Discrete Fourier Transform // Theor. Comp. Sci. 1987. Vol. 51. P. 331-339. Clausen M. Fast Generalized Fourier Transforms // Theor. Comp. Sci. 1989. Vol. 67. No 1. P. 55-63. Rockmore D. Efficient computation of Fourier Inversion for finite groups // J. of the ACM. 1994. Vol. 41. No 1. P. 31-66. Деундяк В.М., Леонов Д.А. Применение быстрого преобразования Фурье для решения сверточных уравнений на диэдральных группах // Вестник САФУ. 2015. No 3. С. 97–107. . Vestnik Severnogo (Arkticheskogo) federal'nogo universiteta , 2015, no. 3, pp. 97-107. (In Russian)] Кириллов А.А. Элементы теории представлений. М.: Наука, 1978. 343 c. . Moscow, Nauka Publ., 1978, 343 p. (In Russian)] Кириллов А.А. Введение в теорию представлений и некоммутативный гармонический анализ // Итоги науки и техн. Сер. Соврем. пробл. мат. Фундам. направления. 1988. Т. 22. С. 5-162. . Itogi nauki i tekhniki. Seriya Sovremennye problemy matematiki. Fundamental'nye napravleniya , 1988, vol. 22, pp. 5-162. (In Russian)] Хьюитт Э., Росс К. Абстрактный гармонический анализ. М.: Наука, Т. 2. 1975. 900 c.