! BFFFT (Blazingly Fast Fourier Transform) Mathematical tool Copyright (C) 2004 Nicolas Riesz.
!
! This program is free software; you can redistribute it and/or modify it under the terms of the GNU General
! Public License as published by the Free Software Foundation; either version 2 of the License, or (at
! you option) any later version.
!
! BFFFT is distributed in the hope that it will be useful, but WITHOUT ANY
! WARRANTY; without even the implied warranty of MERCHANTABILITY or
! FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
! for more details.
!
! You should have received a copy of the GNU General Public License
! along with BFFFT. If not, write to the Free Software Foundation,
! 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
MODULE BFFFT
!
! Real-to-complex 2-D Vectorialized FFT
!
! Sample program to use VFFT2 :
!
! program main
! USE VFFT2
! integer :: s1(N,N), s2(N,N), s3(N,N), s4(N,N)
! real*8 :: w(N+15)
! real*8 :: a(N,N), b(N,N)
!
! call VRFFTINIT(N,w,s1,s2,s3,s4)
!
! ! 2D-FFT of a
! call FFT2(N,a,b,WSAVE,s1,s2,s3,s4)
!
! ! 2D-IFFT of a
! call IFFT2(N,a,b,WSAVE,s1,s2,s3,s4)
!
! end program
!
! FORMAT of after "FFT2" (2D Vectorialized Fast Fourier Transform)
!
! 1 2 3 4 5 ... N
!1 R(0,0) R(1,0) I(1,0) R(2,0) I(2,0) ... R(N/2,0)
!2 R(0,1) R11 -I(N-1,1) R21 -I(N-2,1) ... R(N/2,1)
!3 I(0,1) I11 R(N-1,1) I21 R(N-2,1) ... I(N/2,1)
!4 R(0,2) R12 -I(N-1,2) ... ... ... ...
!5 I(0,2) I12 R(N-1,2) ... ... ...
!6 ... ... ... ... ... ... ...
!7 ... ... ... ... ... ... ...
!. ... ... ... ... ... ... ...
!N-1 I(0,N/2-1) ... ... ... ... ... I(N/2,N/2-1)
!N R(0,N/2) R(1,N/2) I(1,N/2) ... ... ... R(N/2,N/2)
! where R(i,j) + sqrt(-1)*I(i,j) = Fourier coefficient on i, j.
!
! Other coefficients can be deduced by symmetric properties, given that :
!
! R(n1-k1,n2-k2) = R(k1,k2),
! I(n1-k1,n2-k2) = -I(k1,k2),
! R(n1-k1,0) = R(k1,0),
! I(n1-k1,0) = -I(k1,0),
! R(0,n2-k2) = R(0,k2),
! I(0,n2-k2) = -I(0,k2),
!
! for 0