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

Авторы

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

УДК

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)$ и приведены результаты численных экспериментов.

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

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

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

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

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

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

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

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

  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.

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

21-30 из 428

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