Быстрое преобразование Фурье и решение свёрточных уравнений на группе Гейзенберга над простым полем Галуа

  • Деундяк В.М. Южный федеральный университет, Ростов-на-Дону, Россия
  • Леонов Д.А. Южный федеральный университет, Ростов-на-Дону, Россия
УДК: 517.9

Аннотация

Исследуется метод Фурье решения сверточных уравнений на конечной группе Гейзенберга $\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)$ и приведены результаты численных экспериментов.

Ключевые слова: группа Гейзенберга, свёрточные уравнения, метод Фурье, быстрое преобразование Фурье

Информация об авторах

Владимир Михайлович Деундяк
канд. физ.-мат. наук, доцент кафедры алгебры и дискретной математики института математики, механики и компьютерных наук имени И.И. Воровича Южного федерального университета
e-mail: vlade@math.rsu.ru
Дмитрий Александрович Леонов
аспирант кафедры алгебры и дискретной математики института математики, механики и компьютерных наук имени И.И. Воровича Южного федерального университета
e-mail: tori_92@inbox.ru

Литература

  1. Rockmore D. Recent Progress and Applications in Group FFTs // Computational Noncommutative Algebra and Applications. 2004. Vol. 136. P. 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. P. 165-168.
  3. Загороднов И.А., Тарасов Р.П. Задача дифракции на телах с некоммутативной конечной группой симметрий и численное ее решение // Журн. вычисл. математики и матем. физики. 1997. Т. 37. No 10. С. 1246-1262.
  4. 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.
  5. 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.
  6. Terras A. Fourier analysis on finite groups and applications. Cambridge University Press, 1999. 456 c.
  7. Beth T. On the Computational Complexity of the General Discrete Fourier Transform // Theor. Comp. Sci. 1987. Vol. 51. P. 331-339.
  8. Clausen M. Fast Generalized Fourier Transforms // Theor. Comp. Sci. 1989. Vol. 67. No 1. P. 55-63.
  9. Rockmore D. Efficient computation of Fourier Inversion for finite groups // J. of the ACM. 1994. Vol. 41. No 1. P. 31-66.
  10. Деундяк В.М., Леонов Д.А. Применение быстрого преобразования Фурье для решения сверточных уравнений на диэдральных группах // Вестник САФУ. 2015. No 3. С. 97–107.
  11. Кириллов А.А. Элементы теории представлений. М.: Наука, 1978. 343 c.
  12. Кириллов А.А. Введение в теорию представлений и некоммутативный гармонический анализ // Итоги науки и техн. Сер. Соврем. пробл. мат. Фундам. направления. 1988. Т. 22. С. 5-162.
  13. Хьюитт Э., Росс К. Абстрактный гармонический анализ. М.: Наука, Т. 2. 1975. 900 c.
Выпуск
Страницы
46-53
Прислано
2016-03-22
Опубликовано
2016-06-30