Быстрое преобразование Фурье и решение свёрточных уравнений на группе Гейзенберга над простым полем Галуа
УДК
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.
- 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.
- Кириллов А.А. Элементы теории представлений. М.: Наука, 1978. 343 c.
- Кириллов А.А. Введение в теорию представлений и некоммутативный гармонический анализ // Итоги науки и техн. Сер. Соврем. пробл. мат. Фундам. направления. 1988. Т. 22. С. 5-162.
- Хьюитт Э., Росс К. Абстрактный гармонический анализ. М.: Наука, Т. 2. 1975. 900 c.
Загрузки
Выпуск
Страницы
Отправлено
Опубликовано
Как цитировать
Copyright (c) 2016 Деундяк В.М., Леонов Д..
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.