Changeset 315 for trunk/doc/pslib/psLibADD.tex

Timestamp:

Mar 29, 2004, 8:02:57 PM (22 years ago)

Author:

Paul Price

Message:

Starting to define the FFT algorithms.

File:

• trunk/doc/pslib/psLibADD.tex (modified) (1 diff)

trunk/doc/pslib/psLibADD.tex

@@ -476 +476 @@
 \subsubsection{Multi-dimensional polynomials}
 
-Multi-dimensional polynomials shall be composed of multiplications of 1D polynomials.
+Multi-dimensional polynomials shall be composed of multiplications of
+1D Chebyshev polynomials.
+
+
+\subsection{(Fast) Fourier Transforms}
+
+(Fast) Fourier Transforms (FFTs) shall be implemented using the FFTW
+package (www.fftw.org).
+
+\subsubsection{FFTW Plans}
+
+FFTW requires the user to create a ``plan'' for each transform size,
+the time to create which is a function of the desired speed of the
+transform --- faster transforms for a given size (and machine) may be
+performed if more time is spent testing plans.
+
+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.
+
+\subsubsection{Function mapping}
+