Быстрое преобразование Фурье и решение свёрточных уравнений на группе Гейзенберга над простым полем Галуа
УДК
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)$ и приведены результаты численных экспериментов.
Ключевые слова:
группа Гейзенберга, свёрточные уравнения, метод Фурье, быстрое преобразование ФурьеБиблиографические ссылки
- 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. [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)]
- 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. [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)]
- Кириллов А.А. Элементы теории представлений. М.: Наука, 1978. 343 c. [Kirillov A.A. Elementy teorii predstavleniy [Elements of Theory of Representations]. Moscow, Nauka Publ., 1978, 343 p. (In Russian)]
- Кириллов А.А. Введение в теорию представлений и некоммутативный гармонический анализ // Итоги науки и техн. Сер. Соврем. пробл. мат. Фундам. направления. 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)]
- Хьюитт Э., Росс К. Абстрактный гармонический анализ. М.: Наука, Т. 2. 1975. 900 c. [Hewitt E., Ross K. Abstract Harmonic Analysis. Moscow, Science, vol. 2, 1975, 900 p.]
Скачивания
Данные по скачиваниям пока не доступны.
Загрузки
Даты
Поступление
22 марта 2016
После доработки
12 мая 2016
Публикация
30 июня 2016
Как цитировать
[1]
Деундяк, В.М., Леонов, Д.А. , Быстрое преобразование Фурье и решение свёрточных уравнений на группе Гейзенберга над простым полем Галуа. Экологический вестник научных центров Черноморского экономического сотрудничества, 2016, № 2, pp. 46–53.
Лицензия
Copyright (c) 2016 Деундяк В.М., Леонов Д..
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
