Calculating the n-dimensional fast Fourier transform

Тип публикации: статья из журнала

Год издания: 2013

Идентификатор DOI: 10.1134/S1054661813030140

Ключевые слова: Cooley-Tukey FFT, multiple fast Fourier transform, parallel FFT algorithm, Computing devices, Conventional algorithms, Cooley-Tukey FFT, Fast calculations, FFT algorithm, Multidimensional Fourier transform, Multiplication operations, Parallel calculation, Cluster computing, Clustering algorithms, Fast Fourier transforms

Аннотация: The one-dimensional fast Fourier transform (FFT) is the most popular tool for calculating the multidimensional Fourier transform. As a rule, to estimate the n-dimensional FFT, a standard method of combining one-dimensional FFTs, the so-called "by rows and columns" algorithm, is used in the literature. For fast calculations, different researchers try to use parallel calculation tools, the most successful of which are searches for the algorithms related to the computing device architecture: cluster, video card, GPU, etc. [1, 2]. The possibility of paralleling another algorithm for FFT calculation, which is an n-dimensional analog of the Cooley-Tukey algorithm [3, 4], is studied in this paper. The focus is on studying the analog of the Cooley-Tukey algorithm because the number of operations applied to calculate the n-dimensional FFT is considerably less than in the conventional algorithm nN nlog2 N of addition operations and 1/2N n + 1log2 N of multiplication operations of addition operations and 1/2Nn + 1log 2 N of multiplication operations against: N n + 1log2 N of addition operations and 1/2N n + 1log2 N of in combining one-dimensional FFTs. © 2013 Pleiades Publishing, Ltd.

Ссылки на полный текст

Издание

Журнал: Pattern Recognition and Image Analysis

Выпуск журнала: Vol. 23, Is. 3

Номера страниц: 429-433

ISSN журнала: 10546618

Авторы

  • Tutatchikov V.S. (Institute of Space and Information Technology, Siberian Federal University, ul. Akademika Kirenskogo 26, Krasnoyarsk, 660074, Russian Federation)
  • Kiselev O.I. (Institute of Space and Information Technology, Siberian Federal University, ul. Akademika Kirenskogo 26, Krasnoyarsk, 660074, Russian Federation)
  • Noskov M.V. (Institute of Space and Information Technology, Siberian Federal University, ul. Akademika Kirenskogo 26, Krasnoyarsk, 660074, Russian Federation)

Вхождение в базы данных

Информация о публикациях загружается с сайта службы поддержки публикационной активности СФУ. Сообщите, если заметили неточности.

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