fft2d(3F)

NAME
     cfft2d, zfft2d - 2D Complex-to-Complex Fast Fourier Transform.

SYNOPSYS
     Fortran :
     subroutine cfft2d( sign, n1, n2, array, lda, coef )
          integer            sign, n1, n2, lda
          complex        array(lda,n2), coef((n1+15)+(n2+15))

     subroutine zfft2d( sign, n1, n2, array, lda, coef )
          integer            sign, n1, n2, lda
          double complex  array(lda,n2), coef((n1+15)+(n2+15))


     C :
     #include <fft.h>
     int cfft2d ( int sign, int n1, int n2, complex *array,
                    int lda, complex *coef);
     int zfft2d ( int sign, int n1, int n2, zomplex *array,
                    int lda, zomplex *coef);


DESCRIPTION
     cfft2d and zfft2d compute in place the complex Fourier transform of
     complex 2D sequence of size N1 x N2.  The value F{k,l} of the transform
     of the 2D sequence f{i,j} is equal to:
          F{k,l} = Sum ( W1^(i*k) * W2^(j*l) * f{i,j} ),
                  for i =0,...,(N1-1), and j=0,...,(n2-1)
              W1 = exp( (Sign*2*sqrt(-1)*PI) / N1 )
              W2 = exp( (Sign*2*sqrt(-1)*PI) / N2 )


Storage
     It is assumed that the (N1 x N2) 2D sequence is stored along dimension
     N1.  So the index {i+1,j} has an offset of 1 element with respect to
     {i,j}, and {i,j+1} an offset of lda elements with respect to {i,j}.

Algorithm
     The complex-to-complex 2D Fourier transform is computed with a row-column
     approach.
      - First, N2 FFTs complex-to-complex of size N1 are evaluated, stride = 1
     and leading_dimension=lda.
      - then, N1 FFTs complex-to-complex of size N2 are preformed, stride=lda,
     and leading_dimension=1.

PARAMETERS
     SIGN - Integer specifying which sign to be used for the expression of W
     (see above) - must be either +1 or -1.
     Unchanged on exit.
     N1 - Integer, the first dimension size of the 2D sequence.
     Unchanged on exit.

     N2 - Integer, the second dimension size of the 2D sequence.
     Unchanged on exit.

     ARRAY - Array containing the samples of the 2D sequence to be
     transformed.
     On input, the element {i,j} of the sequence is stored as A(i,j) in
     Fortran , and A[i+j*lda] in C.
     On exit, the array is overwritten by its transform.

     LDA - Integer, leading dimension: increment between the samples of two
     consecutive sub-sequences (e.g between {i,j+1} and {i,j}).  lda >= N1
     Unchanged on exit.

     COEFF - Array of at least ( (N1+15)+(N2+15) ) elements.  On entry it
     contains the Sines/Cosines and factorization of N. COEFF needs to be
     initialized with a call to cfft2di or zfft2di. Unchanged on exit.


Example of Calling Sequence
     2D FFT computed for a 64*1024 complex value sequence. The elements of
     each sequence are stored with increment (stride) 1, and the offset
     between the first element of two succesive sequence (leading dimension)
     is 2049.
     Fortran
          complex array(0:2049-1,0:64-1), coeff(1024+15 + 64+15)
          call cfft2di( 1024, 64, coeff)
          call cfft2d( -1, 1024, 64, array, 2049, coeff)

     C
          #include <fft.h>
          complex array[64*2049], *coeff;
          coeff = cfft2di( 1024, 64, NULL);
          cfft2d( -1, 1024, 64, array, 2049, coeff);

SEE ALSO
     fft, cfft2di, zfft2di