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

Авторы

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

УДК

517.9

Аннотация

Исследуется метод Фурье решения сверточных уравнений на конечной группе Гейзенберга H(Fp) над простым полем Галуа Fp. На этой группе построено быстрое преобразование Фурье на основе редукции к быстрому преобразованию Фурье на циклических группах, получены явные формулы для прямого и обратного преобразований, разработан алгоритм решения сверточных уравнений со сложностью O(n4/3), где n=p3 — мощность группы H(Fp). На основе полученных теоретических результатов разработана программная реализация численного метода решения сверточных уравнений на H(Fp) и приведены результаты численных экспериментов.

Ключевые слова:

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

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

  • Владимир Михайлович Деундяк

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

  • Дмитрий Александрович Леонов

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

Библиографические ссылки

  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. [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. 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. [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. Кириллов А.А. Элементы теории представлений. М.: Наука, 1978. 343 c. [Kirillov A.A. Elementy teorii predstavleniy [Elements of Theory of Representations]. Moscow, Nauka Publ., 1978, 343 p. (In Russian)]
  12. Кириллов А.А. Введение в теорию представлений и некоммутативный гармонический анализ // Итоги науки и техн. Сер. Соврем. пробл. мат. Фундам. направления. 1988. Т. 22. С. 5-162. [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. Хьюитт Э., Росс К. Абстрактный гармонический анализ. М.: Наука, Т. 2. 1975. 900 c. [Hewitt E., Ross K. Abstract Harmonic Analysis. Moscow, Science, vol. 2, 1975, 900 p.]

Скачивания

Загрузки

Выпуск

Страницы

46-53

Раздел

Статьи

Даты

Поступила в редакцию

22 марта 2016

Принята к публикации

12 мая 2016

Публикация

30 июня 2016

Как цитировать

[1]
Деундяк, В.М., Леонов, Д.А. , Быстрое преобразование Фурье и решение свёрточных уравнений на группе Гейзенберга над простым полем Галуа. Экологический вестник научных центров Черноморского экономического сотрудничества, 2016, № 2, pp. 46–53.

Похожие статьи

31-40 из 428

Вы также можете начать расширенный поиск похожих статей для этой статьи.