Geodesic
A differential Fourier method
Sibirskij žurnal industrialʹnoj matematiki, Tome 20 (2017) no. 1, pp. 21-30.

Voir la notice de l'article provenant de la source Math-Net.Ru

We propose two new discrete sine and cosine differential Fourier transforms of a complex vector which are based on the finite-difference solution of inhomogeneous harmonic differential equations of the first order with complex coefficients and of the second order with real coefficients respectively. In basic form, the differential Fourier methods need less arithmetic operations as compared to the classical discrete Fourier transform method. The matrix of the sine differential Fourier transform is a complex matrix with alternating real and imaginary entries, and the matrix of the cosine transform is real. As in the classical case, both matrices transform into cyclic convolution matrices, and to them we can apply all fast convolution algorithms including the Winograd and Rader algorithms. The differential Fourier methods are compatible with the Good–Thomas fast Fourier transform algorithm and, if combined with fast convolution algorithms, it can potentially be faster than all known methods of acceleration of the fast Fourier transform.
Mots-clés : discrete Fourier transform, fast Fourier transform
Keywords: harmonic differential equation, Good–Thomas algorithm, Winograd method. 
@article{SJIM_2017_20_1_a2,
     author = {V. G. Gasenko},
     title = {A differential {Fourier} method},
     journal = {Sibirskij \v{z}urnal industrialʹnoj matematiki},
     pages = {21--30},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJIM_2017_20_1_a2/}
}
TY  - JOUR
AU  - V. G. Gasenko
TI  - A differential Fourier method
JO  - Sibirskij žurnal industrialʹnoj matematiki
PY  - 2017
SP  - 21
EP  - 30
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJIM_2017_20_1_a2/
LA  - ru
ID  - SJIM_2017_20_1_a2
ER  - 
%0 Journal Article
%A V. G. Gasenko
%T A differential Fourier method
%J Sibirskij žurnal industrialʹnoj matematiki
%D 2017
%P 21-30
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJIM_2017_20_1_a2/
%G ru
%F SJIM_2017_20_1_a2
V. G. Gasenko. A differential Fourier method. Sibirskij žurnal industrialʹnoj matematiki, Tome 20 (2017) no. 1, pp. 21-30. http://geodesic.mathdoc.fr/item/SJIM_2017_20_1_a2/

[1] Nussbaumer G., Bystroe preobrazovanie Fure i algoritmy vychisleniya svertok, Radio i svyaz, M., 1985

[2] Swarztrauber P. N., “Symmetric FFTs”, Math. Comp., 47:175 (1986), 323–346 | DOI | MR | Zbl

[3] Bleikhut R., Bystrye algoritmy tsifrovoi obrabotki signalov, Mir, M., 1989

[4] Cooley J. W., Tukey J. W., “An algorithm for machine calculation of complex Fourier series”, Math. Comp., 19 (1965), 297–301 | DOI | MR | Zbl

[5] Good I. J., “The interaction algorithm and practical Fourier analysis”, J. Roy. Statist. Soc. Ser. B, 20:2 (1958), 361–375 | MR

[6] Good I. J., “The interaction algorithm and practical Fourier analysis: An addendum”, J. Roy. Statist. Soc. Ser. B, 22:2 (1960), 372–375 | MR | Zbl

[7] Thomas L. H., Using a Computer to Solve Problems in Physics, Applications of Digital Computers, Ginn, Boston, 1963

[8] Winograd S., “On computing the discrete Fourier transform”, Math. Comp., 32 (1978), 175–199 | DOI | MR | Zbl