Changeset 316

Timestamp:

Mar 30, 2004, 2:41:29 PM (22 years ago)

Author:

Paul Price

Message:

Added FFT draft.

File:

• trunk/doc/pslib/psLibADD.tex (modified) (2 diffs)

trunk/doc/pslib/psLibADD.tex

@@ -482 +482 @@
 \subsection{(Fast) Fourier Transforms}
 
-(Fast) Fourier Transforms (FFTs) shall be implemented using the FFTW
-package (www.fftw.org).
+(Fast) Fourier Transforms (FFTs) shall be implemented using the {\em
+Fastest Fourier Transform in the West} (FFTW) library
+(\href{www.fftw.org}).
 
 \subsubsection{FFTW Plans}
@@ -494 +495 @@
 In the \PS{} IPP, we will want to perform FFTs on images of common
 sizes (e.g.\ $512 \times 512$) regularly.  This means that we would
-gain from determining a FFTW plan for each of these common sizes.
-PSLib should therefore maintain a library of these plans, which can be
-loaded and employed as required.  The location of this library on disk
-will be specified as a configuration variable for the IPP.
-
-A program to generate plans for a list of common image sizes should be
-provided.  For example:
-\begin{verbatim}
-machine01% cat myImageSizes.txt
-512 512
-256 256
-32 32
-machine01% psMakeFFTPlans myImageSizes.txt
-machine01% ls
-fftw.machine01.512.512.plan
-fftw.machine01.256.256.plan
-fftw.machine01.32.32.plan
-\end{verbatim}
-
-Plans should be generated using the \code{FFTW_MEASURE} flag of FFTW.
-
-The list of known plans should be read in upon initialisation of the
-PSLib FFT functions, and the appropriate plan should be used for
-transformations.
+gain from determining an FFTW plan for each of these common sizes.
+FFTW provides a binary, \code{fftw-wisdom} which may be used to
+generate and save ``wisdom''.  The location of the \code{wisdom} file
+will be specified as a configuration variable for the IPP (defaulting
+to \code{/etc/fftw/wisdom}).  The \code{wisdom} should be read in upon
+initialisation of the PSLib FFT functions and saved at the conclusion.
 
 \subsubsection{Function mapping}
 
-
+The forward and reverse transforms call the corresponding
+FFTW function to plan the transform:
+
+\begin{tabular}{ll}
+  PSLib function           & Major FFTW call \\ \hline
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+  psFFTForward()           & fftw_plan_dft_r2c_2d()
+  psFFTReverse()           & fftw_plan_dft_c2r_2d()
+\end{tabular}
+
+These plans should be formulated using the \code{FFTW_ESTIMATE} flag,
+which will allow FFTW to default to a short planning time if the
+wisdom has not been loaded.  Transforms should be performed out of
+place to avoid the need to pad the input array.
+
+\subsubsection{More Complicated Functions}
+
+The \code{psFFTFilter} and \code{psFFTFilterComplex} functions provide
+a means to apply a filter (purely real and imaginary multipliers,
+respectively) to the data in the Fourier plane.  If the filter
+function specified for \code{psFFTFilter} returns a real value, $r$,
+then the corresponding value in the Fourier plane should be multiplied
+by $r$.  If the real and imaginary filter functions specified for
+\code{psFFTFilterComplex} returns the values $r$ and $s$,
+respectively, then the corresponding value in the Fourier plane should be
+multiplied by the complex number $(r + si)$.
+
+\code{psFFTCrossCorrelate()} and \code{psFFTConvolve()} both involve
+multiplication of two Fourier transforms.  In the former, the first
+Fourier transform is multiplied by the complex conjugate of the second
+Fourier transform to yield the Fourier transform of the cross-correlation.
+In the latter, the two Fourier transforms are multiplied directly to yield
+the Fourier transform of the convolution.
+
+If the elements of the discrete Fourier transform are $C_k$, then the
+the elements of the power spectrum are defined (NR 13.4):
+\begin{eqnarray}
+P_0     & = & \| C_0 \|^2 / N^2 \\
+P_j     & = & \left( \| C_j \|^2 + \| C_{N-j} \|^2 \right)/ N^2 & j = 1, 2, \ldots, (N/2 - 1) \\
+P_{N/2} & = & \| C_{N/2} \|^2 / N^2 \\
+\end{eqnarray}
+
+Note that we leave the issue of ``windowing'' the data up to the
+caller, and choose to normalise by $1/N^2$.
 
 \subsection{Astronomy Utilities}