УДК

517.9

Сведения об авторах

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

Аннотация

Метод Фурье на коммутативных группах давно применяется во многих областях математики, физики и технических наук. В настоящее время растет применение этого метода и для некоммутативных групп: в частности, в области анализа ранжированной информации, при разработке методов помехоустойчивого кодирования, в теории и практике сетей передачи данных, при анализе изображений, в задаче дифракции на телах с некоммутативной группой симметрий. Особый интерес представляет разработка быстрого преобразования Фурье, позволяющего значительно ускорить решение практически важных задач. Но по сравнению с коммутативным случаем построение быстрого преобразования Фурье для некоммутативных групп существенно затрудняется из-за сложного строения дуальных объектов групп, в терминах которых это преобразование конструируется. Разработка эффективных алгоритмов быстрого преобразования Фурье и алгоритмов, оптимизированных под различные компьютерные архитектуры, для некоммутативных групп интенсивно ведется и в настоящее время. В данной статье исследуется метод Фурье решения сверточных уравнений на диэдральных группах Dm. Построено быстрое преобразование Фурье на диэдральных группах на основе редукции к быстрому преобразованию Фурье на циклических группах, получены явные численные формулы для прямого и обратного преобразований. На основе доказанных формул разработан эффективный алгоритм решения сверточных уравнений на диэдральных группах со сложностью O(mlogm), где m – порядок максимальной циклической подгруппы диэдральной группы. Полученные теоретические результаты позволили на основе использования языка программирования C# разработать программную реализацию численного метода решения сверточных уравнений на произвольной группе Dm. В заключение приведены результаты численных экспериментов.

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

диэдральная группа, сверточные уравнения, метод Фурье, быстрое преобразование Фурье.

Список литературы

1. Cooley J.W., Tukey J.W. An Algorithm for Machine Calculation of Complex Fourier Series // Mathematics of Computation. 1965. Vol. 19, № 90. P. 297–301. 
2. Willsky A. On the Algebraic Structure of Certain Partially Observable Finite-State Markov Processes // Information and Control. 1978. Vol. 38. P. 179–212. 
3. Beth T. On the Computational Complexity of the General Discrete Fourier Transform // Theor. Comp. Sci. 1987. Vol. 51. P. 331–339. 
4. Clausen M. Fast Generalized Fourier Transforms // Theor. Comp. Sci. 1989. Vol. 67, № 1. P. 55–63. 
5. Diaconis P., Rockmore D. Efficient Computation of Fourier Inversion for Finite Groups // J. of the ACM. 1994. Vol. 41, № 1. P. 31–66. 
6. Baum U. Existence and Efficient Construction of Fast Fourier Transforms for Supersolvable Groups // Computational Complexity. 1991. Vol. 1. P. 235–256. 
7. Brigham E. The Fast Fourier Transform and its Applications. Prentice Hall, Upper Saddle River, NJ, USA, 1988. 
8. Diaconis P. Group Representations in Probability and Statistics. IMS, Hayward, CA, 1988. 
9. Lafferty J., Rockmore D. Codes and Iterative Decoding on Algebraic Expander Graphs // Proceedings of International Symposium on Information Theory and its Application, Honolulu, November 5–8 2000. Honolulu, Hawaii, USA, 2000. 
10. Rockmore D. Recent Progress and Applications in Group FFTs // Computational Noncommutative Algebra and Applications. 2004. Vol. 136. P. 227–254. 
11. Leinz R. Using Representations of the Dihedral Groups in the Design of Early Vision Filters. Kyoto, 1993. 
12. Загороднов И.А., Тарасов Р.П. Задача дифракции на телах с некоммутативной конечной группой симметрий и численное ее решение // Журн. вычисл. математики и матем. физики. 1997. Т. 37, № 10. С. 1246– 1262. 
13. Глазман И.М., Любич Ю.И. Конечномерный линейный анализ в задачах. М., 1969. 
14. Кириллов А.А. Элементы теории представлений. М., 1978. 
15. Хьюитт Э., Росс К. Абстрактный гармонический анализ. Т. 2. М., 1975.