its input array.  (The real-to-complex transform, on the other hand,leaves its input array untouched.)  If you use RFFTWND for a rank-onetransform, however, this side-effect does not occur.  Because of thisfact (and the simpler output format), users may find the RFFTWNDinterface more convenient than RFFTW for one-dimensional transforms.However, RFFTWND in one dimension is slightly slower than RFFTW becauseRFFTWND uses an extra buffer array internally.@c ------------------------------------------------------------@node Multi-dimensional Array Format, Words of Wisdom, Real Multi-dimensional Transforms Tutorial, Tutorial@section Multi-dimensional Array FormatThis section describes the format in which multi-dimensional arrays arestored.  We felt that a detailed discussion of this topic was necessary,since it is often a source of confusion among users and severaldifferent formats are common.  Although the comments below refer to@code{fftwnd}, they are also applicable to the @code{rfftwnd} routines.@menu* Row-major Format::            * Column-major Format::         * Static Arrays in C::          * Dynamic Arrays in C::         * Dynamic Arrays in C-The Wrong Way::  @end menu@node Row-major Format, Column-major Format, Multi-dimensional Array Format, Multi-dimensional Array Format@subsection Row-major Format@cindex row-majorThe multi-dimensional arrays passed to @code{fftwnd} are expected to bestored as a single contiguous block in @dfn{row-major} order (sometimescalled ``C order'').  Basically, this means that as you step throughadjacent memory locations, the first dimension's index varies mostslowly and the last dimension's index varies most quickly.To be more explicit, let us consider an array of rank @mathdbbjljt whosedimensions are@tex$n_1 \times n_2 \times n_3 \times \cdots \times n_d$.@end tex@ifinfon1 x n2 x n3 x ... x nd.@end ifinfo@ifhtmln<sub>1</sub> x n<sub>2</sub> x n<sub>3</sub> x ... x n<sub>d</sub>.@end ifhtmlNow, we specify a location in the array by a sequence of (zero-based) indices,one for each dimension:@tex$(i_1, i_2, i_3, \ldots, i_d)$.@end tex@ifinfo(i1, i2, ..., id).@end ifinfo@ifhtml(i<sub>1</sub>, i<sub>2</sub>, i<sub>3</sub>,..., i<sub>d</sub>).@end ifhtmlIf the array is stored in row-majororder, then this element is located at the position@tex$i_d + n_d (i_{d-1} + n_{d-1} (\ldots + n_2 i_1))$.@end tex@ifinfoid + nd * (id-1 + nd-1 * (... + n2 * i1)).@end ifinfo@ifhtmli<sub>d</sub> + n<sub>d</sub> * (i<sub>d-1</sub> + n<sub>d-1</sub> * (... + n<sub>2</sub> * i<sub>1</sub>)).@end ifhtmlNote that each element of the array must be of type @code{fftw_complex};i.e. a (real, imaginary) pair of (double-precision) numbers. Note alsothat, in @code{fftwnd}, the expression above is multiplied by the strideto get the actual array index---this is useful in situations where eachelement of the multi-dimensional array is actually a data structure oranother array, and you just want to transform a single field. In mostcases, however, you use a stride of 1.@cindex stride@node Column-major Format, Static Arrays in C, Row-major Format, Multi-dimensional Array Format@subsection Column-major Format@cindex column-majorReaders from the Fortran world are used to arrays stored in@dfn{column-major} order (sometimes called ``Fortran order'').  This isessentially the exact opposite of row-major order in that, here, the@emph{first} dimension's index varies most quickly.If you have an array stored in column-major order and wish to transformit using @code{fftwnd}, it is quite easy to do.  When creating the plan,simply pass the dimensions of the array to @code{fftwnd_create_plan} in@emph{reverse order}.  For example, if your array is a rank three@code{N x M x L} matrix in column-major order, you should pass thedimensions of the array as if it were an @code{L x M x N} matrix (whichit is, from the perspective of @code{fftwnd}).  This is done for youautomatically by the FFTW Fortran wrapper routines (@pxref{Calling FFTWfrom Fortran}).@cindex Fortran-callable wrappers@node Static Arrays in C, Dynamic Arrays in C, Column-major Format, Multi-dimensional Array Format@subsection Static Arrays in C@cindex C multi-dimensional arraysMulti-dimensional arrays declared statically (that is, at compile time,not necessarily with the @code{static} keyword) in C are @emph{already}in row-major order.  You don't have to do anything special to transformthem.  (@xref{Complex Multi-dimensional Transforms Tutorial}, for anexample of this sort of code.)@node Dynamic Arrays in C, Dynamic Arrays in C-The Wrong Way, Static Arrays in C, Multi-dimensional Array Format@subsection Dynamic Arrays in COften, especially for large arrays, it is desirable to allocate thearrays dynamically, at runtime.  This isn't too hard to do, although itis not as straightforward for multi-dimensional arrays as it is forone-dimensional arrays.Creating the array is simple: using a dynamic-allocation routine like@code{malloc}, allocate an array big enough to store N @code{fftw_complex}values, where N is the product of the sizes of the array dimensions(i.e. the total number of complex values in the array).  For example,here is code to allocate a 5x12x27 rank 3 array:@ffindex malloc@examplefftw_complex *an_array;an_array = (fftw_complex *) malloc(5 * 12 * 27 * sizeof(fftw_complex));@end exampleAccessing the array elements, however, is more tricky---you can't simplyuse multiple applications of the @samp{[]} operator like you could forstatic arrays.  Instead, you have to explicitly compute the offset intothe array using the formula given earlier for row-major arrays.  Forexample, to reference the @math{(i,j,k)}-th element of the arrayallocated above, you would use the expression @code{an_array[k + 27 * (j+ 12 * i)]}.This pain can be alleviated somewhat by defining appropriate macros, or,in C++, creating a class and overloading the @samp{()} operator.@node Dynamic Arrays in C-The Wrong Way,  , Dynamic Arrays in C, Multi-dimensional Array Format@subsection Dynamic Arrays in C---The Wrong WayA different method for allocating multi-dimensional arrays in C is oftensuggested that is incompatible with @code{fftwnd}: @emph{using it willcause FFTW to die a painful death}.  We discuss the technique here,however, because it is so commonly known and used.  This method is tocreate arrays of pointers of arrays of pointers of @dots{}etcetera.  Forexample, the analogue in this method to the example above is:@exampleint i,j;fftw_complex ***a_bad_array;  /* another way to make a 5x12x27 array */a_bad_array = (fftw_complex ***) malloc(5 * sizeof(fftw_complex **));for (i = 0; i < 5; ++i) @{     a_bad_array[i] =         (fftw_complex **) malloc(12 * sizeof(fftw_complex *));     for (j = 0; j < 12; ++j)          a_bad_array[i][j] =                (fftw_complex *) malloc(27 * sizeof(fftw_complex));@}@end exampleAs you can see, this sort of array is inconvenient to allocate (anddeallocate).  On the other hand, it has the advantage that the@math{(i,j,k)}-th element can be referenced simply by@code{a_bad_array[i][j][k]}.If you like this technique and want to maximize convenience in accessingthe array, but still want to pass the array to FFTW, you can use ahybrid method.  Allocate the array as one contiguous block, but alsodeclare an array of arrays of pointers that point to appropriate placesin the block.  That sort of trick is beyond the scope of thisdocumentation; for more information on multi-dimensional arrays in C,see the @code{comp.lang.c}@uref{http://www.eskimo.com/~scs/C-faq/s6.html, FAQ}.@c ------------------------------------------------------------@node Words of Wisdom,  , Multi-dimensional Array Format, Tutorial@section Words of Wisdom@cindex wisdom@cindex saving plans to diskFFTW implements a method for saving plans to disk and restoring them.In fact, what FFTW does is more general than just saving and loadingplans.  The mechanism is called @dfn{@code{wisdom}}.  Here, we describethis feature at a high level. @xref{FFTW Reference}, for a less casual(but more complete) discussion of how to use @code{wisdom} in FFTW.Plans created with the @code{FFTW_MEASURE} option produce near-optimalFFT performance, but it can take a long time to compute a plan becauseFFTW must actually measure the runtime of many possible plans and selectthe best one.  This is designed for the situations where so manytransforms of the same size must be computed that the start-up time isirrelevant.  For short initialization times but slightly slowertransforms, we have provided @code{FFTW_ESTIMATE}.  The @code{wisdom}mechanism is a way to get the best of both worlds.  There are, however,certain caveats that the user must be aware of in using @code{wisdom}.For this reason, @code{wisdom} is an optional feature which is notenabled by default.At its simplest, @code{wisdom} provides a way of saving plans to disk sothat they can be reused in other program runs.  You create a plan withthe flags @code{FFTW_MEASURE} and @code{FFTW_USE_WISDOM}, and then savethe @code{wisdom} using @code{fftw_export_wisdom}:@ctindex FFTW_USE_WISDOM@example     plan = fftw_create_plan(..., ... | FFTW_MEASURE | FFTW_USE_WISDOM);     fftw_export_wisdom(...);@end example@findex fftw_export_wisdomThe next time you run the program, you can restore the @code{wisdom}with @code{fftw_import_wisdom}, and then recreate the plan using thesame flags as before.  This time, however, the same optimal plan will becreated very quickly without measurements. (FFTW still needs some timeto compute trigonometric tables, however.)  The basic outline is:@example     fftw_import_wisdom(...);     plan = fftw_create_plan(..., ... | FFTW_USE_WISDOM);@end example@findex fftw_import_wisdomWisdom is more than mere rote memorization, however.  FFTW's@code{wisdom} encompasses all of the knowledge and measurements thatwere used to create the plan for a given size.  Therefore, existing@code{wisdom} is also applied to the creation of other plans ofdifferent sizes.Whenever a plan is created with the @code{FFTW_MEASURE} and@code{FFTW_USE_WISDOM} flags, @code{wisdom} is generated.  Thereafter,plans for any transform with a similar factorization will be computedmore quickly, so long as they use the @code{FFTW_USE_WISDOM} flag.  Infact, for transforms with the same factors and of equal or lesser size,no measurements at all need to be made and an optimal plan can becreated with negligible delay!For example, suppose that you create a plan for@tex$N = 2^{16}$.@end tex@ifinfoN = 2^16.@end ifinfo@ifhtmlN&nbsp;=&nbsp;2<sup>16</sup>.@end ifhtmlThen, for any equal or smaller power of two, FFTW can create aplan (with the same direction and flags) quickly, using theprecomputed @code{wisdom}. Even for larger powers of two, or sizes thatare a power of two times some other prime factors, plans will becomputed more quickly than they would otherwise (although somemeasurements still have to be made).The @code{wisdom} is cumulative, and is stored in a global, private datastructure managed internally by FFTW.  The storage space required isminimal, proportional to the logarithm of the sizes the @code{wisdom} wasgenerated from.  The @code{wisdom} can be forgotten (and its associatedmemory freed) by a call to @code{fftw_forget_wisdom()}; otherwise, it isremembered until the program terminates.  It can also be exported to afile, a string, or any other medium using @code{fftw_export_wisdom} andrestored during a subsequent execution of the program (or a differentprogram) using @code{fftw_import_wisdom} (these functions are describedbelow).Because @code{wisdom} is incorporated into FFTW at a very low level, thesame @code{wisdom} can be used for one-dimensional transforms,multi-dimensional transforms, and even the parallel extensions to FFTW.Just include @code{FFTW_USE_WISDOM} in the flags for whatever plans youcreate (i.e., always plan wisely).Plans created with the @code{FFTW_ESTIMATE} plan can use @code{wisdom},but cannot generate it;  only @code{FFTW_MEASURE} plans actually produce@code{wisdom}.  Also, plans can only use @code{wisdom} generated fromplans created with the same direction and flags.  For example, a size@code{42} @code{FFTW_BACKWARD} transform will not use @code{wisdom}produced by a size @code{42} @code{FFTW_FORWARD} transform.  The onlyexception to this rule is that @code{FFTW_ESTIMATE} plans can use@code{wisdom} from @code{FFTW_MEASURE} plans.@menu* Caveats in Using Wisdom::     What you should worry about in using wisdom* Importing and Exporting Wisdom::  I/O of wisdom to disk and other media@end menu@node Caveats in Using Wisdom, Importing and Exporting Wisdom, Words of Wisdom, Words of Wisdom@subsection Caveats in Using Wisdom@cindex wisdom, problems with@quotation@ifhtml<i>@end ifhtmlFor in much wisdom is much grief, and he that increaseth knowledgeincreaseth sorrow.@ifhtml</i>@end ifhtml[Ecclesiastes 1:18]@cindex Ecclesiastes@end quotationThere are pitfalls to using @code{wisdom}, in that it can negate FFTW'sability to adapt to changing hardware and other conditions. For example,it would be perfectly possible to export @code{wisdom} from a programrunning on one processor and import it into a program running on anotherprocessor.  Doing so, however, would mean that the second program woulduse plans optimized for the first processor, instead of the one it isrunning on.It should be safe to reuse @code{wisdom} as long as the hardware andprogram binaries remain unchanged. (Actually, the optimal plan maychange even between runs of the same binary on identical hardware, dueto differences in the virtual memory environment, etcetera.  Usersseriously interested in performance should worry about this problem,too.)  It is likely that, if the same @code{wisdom} is used for twodifferent program binaries, even running on the same machine, the plansmay be sub-optimal because of differing code alignments.  It istherefore wise to recreate @code{wisdom} every time an application isrecompiled.  The more the underlying hardware and software changesbetween the creation of @code{wisdom} and its use, the greater grows therisk of sub-optimal plans.@node Importing and Exporting Wisdom,  , Caveats in Using Wisdom, Words of Wisdom