\input texinfo   @c -*- texinfo -*-@c % $Id: fftw.texi,v 1.256 2003/01/15 21:09:33 stevenj Exp $@c %**start of header@setfilename fftw.info@settitle FFTW@c %**end of header@include version.texi@setchapternewpage odd@c define constant index (ct)@defcodeindex ct@syncodeindex ct fn@syncodeindex vr fn@syncodeindex pg fn@syncodeindex tp fn@c define foreign function index (ff)@defcodeindex ff@syncodeindex ff cp@c define foreign constant index (fc)@defcodeindex fc@syncodeindex fc cp@c define foreign program index (fp)@defcodeindex fp@syncodeindex fp cp@ifinfoThis is the FFTW User's manual.Copyright @copyright{} 1997--1999 Massachusetts Institute of TechnologyPermission is granted to make and distribute verbatim copies of thismanual provided the copyright notice and this permission notice arepreserved on all copies.Permission is granted to copy and distribute modified versions of thismanual under the conditions for verbatim copying, provided that theentire resulting derived work is distributed under the terms of apermission notice identical to this one.Permission is granted to copy and distribute translations of this manualinto another language, under the above conditions for modified versions,except that this permission notice may be stated in a translationapproved by the Free Software Foundation.@end ifinfo@titlepage@sp 10@comment The title is printed in a large font.@title{FFTW User's Manual}@subtitle For version @value{VERSION}, @value{UPDATED}@author{Matteo Frigo}@author{Steven G. Johnson}@c The following two commands start the copyright page.@page@vskip 0pt plus 1filllCopyright @copyright{} 1997--1999 Massachusetts Institute of Technology.Permission is granted to make and distribute verbatim copies of thismanual provided the copyright notice and this permission notice arepreserved on all copies.Permission is granted to copy and distribute modified versions of thismanual under the conditions for verbatim copying, provided that theentire resulting derived work is distributed under the terms of apermission notice identical to this one.Permission is granted to copy and distribute translations of this manualinto another language, under the above conditions for modified versions,except that this permission notice may be stated in a translationapproved by the Free Software Foundation.@end titlepage@node    Top, Introduction, (dir), (dir)@ifinfo@top FFTW User ManualWelcome to FFTW, the Fastest Fourier Transform in the West.  FFTW is acollection of fast C routines to compute the discrete Fourier transform.This manual documents FFTW version @value{VERSION}.@end ifinfo@menu* Introduction::                * Tutorial::                    * FFTW Reference::              * Parallel FFTW::               * Calling FFTW from Fortran::   * Installation and Customization::  * Acknowledgments::             * License and Copyright::       * Concept Index::               * Library Index::               @detailmenu --- The Detailed Node Listing ---Tutorial* Complex One-dimensional Transforms Tutorial::  * Complex Multi-dimensional Transforms Tutorial::  * Real One-dimensional Transforms Tutorial::  * Real Multi-dimensional Transforms Tutorial::  * Multi-dimensional Array Format::  * Words of Wisdom::             Multi-dimensional Array Format* Row-major Format::            * Column-major Format::         * Static Arrays in C::          * Dynamic Arrays in C::         * Dynamic Arrays in C-The Wrong Way::  Words of Wisdom* Caveats in Using Wisdom::     What you should worry about in using wisdom* Importing and Exporting Wisdom::  I/O of wisdom to disk and other mediaFFTW Reference* Data Types::                  real, complex, and halfcomplex numbers* One-dimensional Transforms Reference::  * Multi-dimensional Transforms Reference::  * Real One-dimensional Transforms Reference::  * Real Multi-dimensional Transforms Reference::  * Wisdom Reference::            * Memory Allocator Reference::  * Thread safety::               One-dimensional Transforms Reference* fftw_create_plan::            Plan Creation* Discussion on Specific Plans::  * fftw::                        Plan Execution* fftw_destroy_plan::           Plan Destruction* What FFTW Really Computes::   Definition of the DFT.Multi-dimensional Transforms Reference* fftwnd_create_plan::          Plan Creation* fftwnd::                      Plan Execution* fftwnd_destroy_plan::         Plan Destruction* What FFTWND Really Computes::  Real One-dimensional Transforms Reference* rfftw_create_plan::           Plan Creation   * rfftw::                       Plan Execution  * rfftw_destroy_plan::          Plan Destruction* What RFFTW Really Computes::  Real Multi-dimensional Transforms Reference* rfftwnd_create_plan::         Plan Creation* rfftwnd::                     Plan Execution* Array Dimensions for Real Multi-dimensional Transforms::  * Strides in In-place RFFTWND::  * rfftwnd_destroy_plan::        Plan Destruction* What RFFTWND Really Computes::  Wisdom Reference* fftw_export_wisdom::          * fftw_import_wisdom::          * fftw_forget_wisdom::          Parallel FFTW* Multi-threaded FFTW::         * MPI FFTW::                    Multi-threaded FFTW* Installation and Supported Hardware/Software::  * Usage of Multi-threaded FFTW::  * How Many Threads to Use?::    * Using Multi-threaded FFTW in a Multi-threaded Program::  * Tips for Optimal Threading::  MPI FFTW* MPI FFTW Installation::       * Usage of MPI FFTW for Complex Multi-dimensional Transforms::  * MPI Data Layout::             * Usage of MPI FFTW for Real Multi-dimensional Transforms::  * Usage of MPI FFTW for Complex One-dimensional Transforms::  * MPI Tips::                    Calling FFTW from Fortran* Wrapper Routines::            * FFTW Constants in Fortran::   * Fortran Examples::            Installation and Customization* Installation on Unix::        * Installation on non-Unix Systems::  * Installing FFTW in both single and double precision::  * gcc and Pentium hacks::  * Customizing the timer::       * Generating your own code::    @end detailmenu@end menu@c ************************************************************@node    Introduction, Tutorial, Top, Top@chapter IntroductionThis manual documents version @value{VERSION} of FFTW, the @emph{FastestFourier Transform in the West}.  FFTW is a comprehensive collection offast C routines for computing the discrete Fourier transform (DFT) inone or more dimensions, of both real and complex data, and of arbitraryinput size.  FFTW also includes parallel transforms for both shared- anddistributed-memory systems.  We assume herein that the reader is alreadyfamiliar with the properties and uses of the DFT that are relevant toher application.  Otherwise, see e.g. @cite{The Fast Fourier Transform}by E. O. Brigham (Prentice-Hall, Englewood Cliffs, NJ, 1974).@uref{http://www.fftw.org, Our web page} also has links toFFT-related information online.@cindex FFTWFFTW is usually faster (and sometimes much faster) than all otherfreely-available Fourier transform programs found on the Net.  Fortransforms whose size is a power of two, it compares favorably with theFFT codes in Sun's Performance Library and IBM's ESSL library, which aretargeted at specific machines.  Moreover, FFTW's performance is@emph{portable}.  Indeed, FFTW is unique in that it automatically adaptsitself to your machine, your cache, the size of your memory, the numberof registers, and all the other factors that normally make it impossibleto optimize a program for more than one machine.  An extensivecomparison of FFTW's performance with that of other Fourier transformcodes has been made. The results are available on the Web at@uref{http://theory.lcs.mit.edu/~benchfft, the benchFFT home page}.@cindex benchmark@fpindex benchfftIn order to use FFTW effectively, you need to understand one basicconcept of FFTW's internal structure.  FFTW does not used a fixedalgorithm for computing the transform, but it can adapt the DFTalgorithm to details of the underlying hardware in order to achieve bestperformance.  Hence, the computation of the transform is split into twophases.  First, FFTW's @dfn{planner} is called, which ``learns'' the@cindex planfastest way to compute the transform on your machine.  The planner@cindex plannerproduces a data structure called a @dfn{plan} that contains thisinformation.  Subsequently, the plan is passed to FFTW's @dfn{executor},@cindex executoralong with an array of input data.  The executor computes the actualtransform, as dictated by the plan.  The plan can be reused as manytimes as needed.  In typical high-performance applications, manytransforms of the same size are computed, and consequently arelatively-expensive initialization of this sort is acceptable.  On theother hand, if you need a single transform of a given size, the one-timecost of the planner becomes significant.  For this case, FFTW providesfast planners based on heuristics or on previously computed plans.The pattern of planning/execution applies to all four operation modes ofFFTW, that is, @w{I) one-dimensional} complex transforms (FFTW), @w{II)multi-dimensional} complex transforms (FFTWND), @w{III) one-dimensional}transforms of real data (RFFTW), @w{IV) multi-dimensional} transforms ofreal data (RFFTWND).  Each mode comes with its own planner and executor.Besides the automatic performance adaptation performed by the planner,it is also possible for advanced users to customize FFTW for theirspecial needs.  As distributed, FFTW works most efficiently for arrayswhose size can be factored into small primes (@math{2}, @math{3},@math{5}, and @math{7}), and uses a slower general-purpose routine forother factors.  FFTW, however, comes with a code generator that canproduce fast C programs for any particular array size you may careabout.@cindex code generatorFor example, if you need transforms of size@ifinfo@math{513 = 19 x 3^3},@end ifinfo@tex$513 = 19 \cdot 3^3$,@end tex@ifhtml513&nbsp;=&nbsp;19*3<sup>3</sup>,@end ifhtmlyou can customize FFTW to support the factor @math{19} efficiently.FFTW can exploit multiple processors if you have them.  FFTW comes witha shared-memory implementation on top of POSIX (and similar) threads, aswell as a distributed-memory implementation based on MPI.@cindex parallel transform@cindex threads@cindex MPIWe also provide an experimental parallel implementation written in Cilk,@emph{the superior programming tool of choice for discriminatinghackers} (Olin Shivers).  (See @uref{http://supertech.lcs.mit.edu/cilk,the Cilk home page}.)@cindex CilkFor more information regarding FFTW, see the paper, ``The FastestFourier Transform in the West,'' by M. Frigo and S. G. Johnson, which isthe technical report MIT-LCS-TR-728 (Sep. '97).  See also, ``FFTW: AnAdaptive Software Architecture for the FFT,'' by M. Frigo andS. G. Johnson, which appeared in the 23rd International Conference onAcoustics, Speech, and Signal Processing (@cite{Proc. ICASSP 1998}@b{3}, p. 1381).  The code generator is described in the paper ``A FastFourier Transform Compiler'', @cindex compilerby M. Frigo, to appear in the @cite{Proceedings of the 1999 ACM SIGPLANConference on Programming Language Design and Implementation (PLDI),Atlanta, Georgia, May 1999}.  These papers, along with the latestversion of FFTW, the FAQ, benchmarks, and other links, are available at@uref{http://www.fftw.org, the FFTW home page}.  The currentversion of FFTW incorporates many good ideas from the past thirty yearsof FFT literature.  In one way or another, FFTW uses the Cooley-Tukeyalgorithm, the Prime Factor algorithm, Rader's algorithm for primesizes, and the split-radix algorithm (with a variation due to DanBernstein).  Our code generator also produces new algorithms that we donot yet completely understand.@cindex algorithmThe reader is referred to the cited papers for the appropriatereferences.The rest of this manual is organized as follows.  We first discuss thesequential (one-processor) implementation.  We start by describing thebasic features of FFTW in @ref{Tutorial}.  This discussion includes thestorage scheme of multi-dimensional arrays (@ref{Multi-dimensional ArrayFormat}) and FFTW's mechanisms for storing plans on disk (@ref{Words ofWisdom}).  Next, @ref{FFTW Reference} provides comprehensivedocumentation of all FFTW's features.  Parallel transforms are discussedin their own chapter @ref{Parallel FFTW}.  Fortran programmers can also