FFT and solving of convolution equations on Heisenber group over prime Galua field

Authors

  • Deundyak V.M. Southern Federal University, Rostov-on-Don, Российская Федерация
  • Leonov D.A. Southern Federal University, Rostov-on-Don, Российская Федерация

UDC

517.9

Abstract

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.

Keywords:

Heisenberg group, convolution equations, Fourier method, fast Fourier transformation

Author Infos

Vladimir M. Deundyak

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

e-mail: vlade@math.rsu.ru

Dmitriy A. Leonov

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

e-mail: tori_92@inbox.ru

References

  1. Rockmore D. Recent Progress and Applications in Group FFTs. Computational Noncommutative Algebra and Applications, 2004, vol. 136, pp. 227-254.
  2. Leinz R. Using representations of the dihedral groups in the design of early vision filters. Acoustics, Speech, and Signal Processing, 1993, vol. 5, pp. 165-168.
  3. Zagorodnov I.A., Tarasov R.P. Zadacha difraktsii na telakh s nekommutativnoy konechnoy gruppoy simmetriy i chislennoe ee reshenie [The Problem of Diffraction on Bodies with Non-Commutative Finite Group of Symmetries and Numerical Solution]. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki [Computational mathematics and mathematical physics], 1997, vol. 37, no. 10, pp. 1246-1262. (In Russian)
  4. Howe R. On The role of the Heisenberg group in harmonic analysis. Bulletin of the American Mathematical Society, 1980, vol. 3, no. 2, pp. 821-843.
  5. Bump D., Diaconis P., Hicks A., Miclo L., Widom H. An exercise(?) in Fourier analysis on the Heisenberg group. ArXiv e-prints, 2015, pp. 1-24.
  6. Terras A. Fourier analysis on finite groups and applications. Cambridge University Press, 1999, 456 p.
  7. Beth T. On the Computational Complexity of the General Discrete Fourier Transform. Theor. Comp. Sci., 1987, vol. 51, pp. 331-339.
  8. Clausen M. Fast Generalized Fourier Transforms. Theor. Comp. Sci., 1989, vol. 67, no. 1, pp. 55-63.
  9. Rockmore D. Efficient computation of Fourier Inversion for finite groups. J. of the ACM, 1994, vol. 41, no. 1, pp. 31-66.
  10. Deundyak V.M., Leonov D.A. Primenenie bistrogo preobrazovania Fourier dlya reshenia svertochnih uravneni' na diedral'nih groppah [Fast Fourier Transform for solution of convolution equations on Dihedral Groups]. Vestnik Severnogo (Arkticheskogo) federal'nogo universiteta [Bull. of Northern (Arctic) Federal University], 2015, no. 3, pp. 97-107. (In Russian)
  11. Kirillov A.A. Elementy teorii predstavleniy [Elements of Theory of Representations]. Moscow, Nauka Publ., 1978, 343 p. (In Russian)
  12. Kirillov A.A. Vvedenie v teoriu predstavleni' i nekommutativni' garmonicheski' analis [Introduction to the theory of representations and noncommutative harmonic analysis]. Itogi nauki i tekhniki. Seriya Sovremennye problemy matematiki. Fundamental'nye napravleniya [The results of science and technology. Series `Modern problems of mathematics. Fundamental directions'], 1988, vol. 22, pp. 5-162. (In Russian)
  13. Hewitt E., Ross K. Abstract Harmonic Analysis. Moscow, Science, vol. 2, 1975, 900 p.

Downloads

Issue

2016. No. 2

Pages

46-53

Submitted

2016-03-22

Published

2016-06-30

How to Cite

Deundyak V.M., Leonov D.A. FFT and solving of convolution equations on Heisenber group over prime Galua field. Ecological Bulletin of Research Centers of the Black Sea Economic Cooperation, 2016, no. 2, pp. 46-53. (In Russian)

Copyright (c) 2016 Deundyak V.M., Leonov D.A.

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.