WebSVN - shark - Blame - Rev 1618 - /shark/branches/xen/ports/fftw/doc/fftw

Rev	Author	Line No.	Line
2	pj	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
		2	<HTML>
		3	<HEAD>
		4	<!-- This HTML file has been created by texi2html 1.52
		5	from fftw.texi on 18 May 1999 -->
		6
		7	<TITLE>FFTW - FFTW Reference</TITLE>
		8	</HEAD>
		9	<BODY TEXT="#000000" BGCOLOR="#FFFFFF">
		10	Go to the <A HREF="fftw_1.html">first</A>, <A HREF="fftw_2.html">previous</A>, <A HREF="fftw_4.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>.
		11	<P><HR><P>
		12
		13
		14	<H1><A NAME="SEC16">FFTW Reference</A></H1>
		15
		16	<P>
		17	This chapter provides a complete reference for all sequential (i.e.,
		18	one-processor) FFTW functions. We first define the data types upon
		19	which FFTW operates, that is, real, complex, and "halfcomplex" numbers
		20	(see Section <A HREF="fftw_3.html#SEC17">Data Types</A>). Then, in four sections, we explain the FFTW
		21	program interface for complex one-dimensional transforms
		22	(see Section <A HREF="fftw_3.html#SEC18">One-dimensional Transforms Reference</A>), complex
		23	multi-dimensional transforms (see Section <A HREF="fftw_3.html#SEC24">Multi-dimensional Transforms Reference</A>), and real one-dimensional transforms (see Section <A HREF="fftw_3.html#SEC29">Real One-dimensional Transforms Reference</A>), real multi-dimensional
		24	transforms (see Section <A HREF="fftw_3.html#SEC34">Real Multi-dimensional Transforms Reference</A>).
		25	Section <A HREF="fftw_3.html#SEC41">Wisdom Reference</A> describes the <CODE>wisdom</CODE> mechanism for
		26	exporting and importing plans. Finally, Section <A HREF="fftw_3.html#SEC45">Memory Allocator Reference</A> describes how to change FFTW's default memory allocator.
		27	For parallel transforms, See Section <A HREF="fftw_4.html#SEC47">Parallel FFTW</A>.
		28
		29
		30
		31
		32	<H2><A NAME="SEC17">Data Types</A></H2>
		33	<P>
		34	<A NAME="IDX98"></A>
		35	<A NAME="IDX99"></A>
		36	<A NAME="IDX100"></A>
		37
		38
		39	<P>
		40	The routines in the FFTW package use three main kinds of data types.
		41	<EM>Real</EM> and <EM>complex</EM> numbers should be already known to the
		42	reader. We also use the term <EM>halfcomplex</EM> to describe complex
		43	arrays in a special packed format used by the one-dimensional real
		44	transforms (taking advantage of the <EM>hermitian</EM> symmetry that arises
		45	in those cases).
		46
		47
		48	<P>
		49	By including <CODE><fftw.h></CODE> or <CODE><rfftw.h></CODE>, you will have access
		50	to the following definitions:
		51
		52
		53
		54	<PRE>
		55	typedef double fftw_real;
		56
		57	typedef struct {
		58	fftw_real re, im;
		59	} fftw_complex;
		60
		61	#define c_re(c) ((c).re)
		62	#define c_im(c) ((c).im)
		63	</PRE>
		64
		65	<P>
		66	<A NAME="IDX101"></A>
		67	<A NAME="IDX102"></A>
		68
		69
		70	<P>
		71	All FFTW operations are performed on the <CODE>fftw_real</CODE> and
		72	<CODE>fftw_complex</CODE> data types. For <CODE>fftw_complex</CODE> numbers, the
		73	two macros <CODE>c_re</CODE> and <CODE>c_im</CODE> retrieve, respectively, the real
		74	and imaginary parts of the number.
		75
		76
		77	<P>
		78	A <EM>real array</EM> is an array of real numbers. A <EM>complex array</EM>
		79	is an array of complex numbers. A one-dimensional array X of
		80	n complex numbers is <EM>hermitian</EM> if the following property
		81	holds:
		82	for all 0 <= i < n, we have X<sub>i</sub> = conj(X<sub>n-i</sub>)}.
		83	Hermitian arrays are relevant to FFTW because the Fourier transform of a
		84	real array is hermitian.
		85
		86
		87	<P>
		88	Because of its symmetry, a hermitian array can be stored in half the
		89	space of a complex array of the same size. FFTW's one-dimensional real
		90	transforms store hermitian arrays as <EM>halfcomplex</EM> arrays. A
		91	halfcomplex array of size n is
		92	<A NAME="IDX103"></A>
		93	a one-dimensional array of n <CODE>fftw_real</CODE> numbers. A
		94	hermitian array X in stored into a halfcomplex array Y as
		95	follows.
		96	For all integers i such that 0 <= i <= n / 2, we have
		97	Y<sub>i</sub> = Re(X<sub>i</sub>). For all integers i such that 0
		98	< i < n / 2, we have Y<sub>n-i</sub> = Im(X<sub>i</sub>).
		99
		100
		101	<P>
		102	We now illustrate halfcomplex storage for n = 4 and n = 5,
		103	since the scheme depends on the parity of n. Let n = 4.
		104	In this case, we have
		105	Y<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),
		106	Y<sub>2</sub> = Re(X<sub>2</sub>), and Y<sub>3</sub> = Im(X<sub>1</sub>).
		107	Let now n = 5. In this case, we have
		108	Y<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),
		109	Y<sub>2</sub> = Re(X<sub>2</sub>), Y<sub>3</sub> = Im(X<sub>2</sub>),
		110	and Y<sub>4</sub> = Im(X<sub>1</sub>).
		111
		112
		113	<P>
		114	<A NAME="IDX104"></A>
		115	By default, the type <CODE>fftw_real</CODE> equals the C type <CODE>double</CODE>.
		116	To work in single precision rather than double precision, <CODE>#define</CODE>
		117	the symbol <CODE>FFTW_ENABLE_FLOAT</CODE> in <CODE>fftw.h</CODE> and then recompile
		118	the library. On Unix systems, you can instead use <CODE>configure
		119	--enable-float</CODE> at installation time (see Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>).
		120	<A NAME="IDX105"></A>
		121	<A NAME="IDX106"></A>
		122
		123
		124	<P>
		125	In version 1 of FFTW, the data types were called <CODE>FFTW_REAL</CODE> and
		126	<CODE>FFTW_COMPLEX</CODE>. We changed the capitalization for consistency with
		127	the rest of FFTW's conventions. The old names are still supported, but
		128	their use is deprecated.
		129	<A NAME="IDX107"></A>
		130	<A NAME="IDX108"></A>
		131
		132
		133
		134
		135	<H2><A NAME="SEC18">One-dimensional Transforms Reference</A></H2>
		136
		137	<P>
		138	The one-dimensional complex routines are generally prefixed with
		139	<CODE>fftw_</CODE>. Programs using FFTW should be linked with <CODE>-lfftw
		140	-lm</CODE> on Unix systems, or with the FFTW and standard math libraries in
		141	general.
		142
		143
		144
		145
		146	<H3><A NAME="SEC19">Plan Creation for One-dimensional Transforms</A></H3>
		147
		148
		149	<PRE>
		150	#include <fftw.h>
		151
		152	fftw_plan fftw_create_plan(int n, fftw_direction dir,
		153	int flags);
		154
		155	fftw_plan fftw_create_plan_specific(int n, fftw_direction dir,
		156	int flags,
		157	fftw_complex *in, int istride,
		158	fftw_complex *out, int ostride);
		159	</PRE>
		160
		161	<P>
		162	<A NAME="IDX109"></A>
		163	<A NAME="IDX110"></A>
		164	<A NAME="IDX111"></A>
		165	<A NAME="IDX112"></A>
		166
		167
		168	<P>
		169	The function <CODE>fftw_create_plan</CODE> creates a plan, which is
		170	a data structure containing all the information that <CODE>fftw</CODE>
		171	needs in order to compute the 1D Fourier transform. You can
		172	create as many plans as you need, but only one plan for a given
		173	array size is required (a plan can be reused many times).
		174
		175
		176	<P>
		177	<CODE>fftw_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE>
		178	if, for some reason, the plan can't be created. In the
		179	default installation, this cannot happen, but it is possible
		180	to configure FFTW in such a way that some input sizes are
		181	forbidden, and FFTW cannot create a plan.
		182
		183
		184	<P>
		185	The <CODE>fftw_create_plan_specific</CODE> variant takes as additional
		186	arguments specific input/output arrays and their strides. For the last
		187	four arguments, you should pass the arrays and strides that you will
		188	eventually be passing to <CODE>fftw</CODE>. The resulting plans will be
		189	optimized for those arrays and strides, although they may be used on
		190	other arrays as well. Note: the contents of the in and out arrays are
		191	<EM>destroyed</EM> by the specific planner (the initial contents are
		192	ignored, so the arrays need not have been initialized).
		193
		194
		195
		196	<H4>Arguments</H4>
		197
		198	<UL>
		199	<LI>
		200
		201	<CODE>n</CODE> is the size of the transform. It can be
		202	any positive integer.
		203
		204
		205	<UL>
		206	<LI>
		207
		208	FFTW is best at handling sizes of the form
		209	2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP>
		210	11<SUP>e</SUP> 13<SUP>f</SUP>,
		211	where e+f is either 0 or
		212	1, and the other exponents are arbitrary. Other sizes are
		213	computed by means of a slow, general-purpose routine (which nevertheless
		214	retains
		215	O(n lg n)
		216	performance, even for prime sizes). (It is
		217	possible to customize FFTW for different array sizes.
		218	See Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A> for more information.) Transforms
		219	whose sizes are powers of 2 are especially fast.
		220	</UL>
		221
		222	<LI>
		223
		224	<CODE>dir</CODE> is the sign of the exponent in the formula that
		225	defines the Fourier transform. It can be -1 or +1.
		226	The aliases <CODE>FFTW_FORWARD</CODE> and <CODE>FFTW_BACKWARD</CODE>
		227	are provided, where <CODE>FFTW_FORWARD</CODE> stands for -1.
		228
		229	<LI>
		230
		231	<A NAME="IDX113"></A>
		232	<CODE>flags</CODE> is a boolean OR (<SAMP>`\|'</SAMP>) of zero or more of the following:
		233
		234	<UL>
		235	<LI>
		236
		237	<CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by
		238	actually <EM>computing</EM> several FFTs and measuring their
		239	execution time. Depending on the installation, this can take some
		240	time. <A NAME="DOCF2" HREF="fftw_foot.html#FOOT2">(2)</A>
		241
		242	<LI>
		243
		244	<CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"
		245	plan (for a RISC processor with many registers). If neither
		246	<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is
		247	<CODE>FFTW_ESTIMATE</CODE>.
		248
		249	<LI>
		250
		251	<CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input and
		252	output arrays will be distinct (this is the default).
		253	<A NAME="IDX114"></A>
		254
		255	<LI>
		256
		257	<A NAME="IDX115"></A>
		258	<CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want the output
		259	in the input array. The algorithm used is not necessarily in place:
		260	FFTW is able to compute true in-place transforms only for small values
		261	of <CODE>n</CODE>. If FFTW is not able to compute the transform in-place, it
		262	will allocate a temporary array (unless you provide one yourself),
		263	compute the transform out of place, and copy the result back.
		264	<EM>Warning: This option changes the meaning of some parameters of
		265	<CODE>fftw</CODE></EM> (see Section <A HREF="fftw_3.html#SEC21">Computing the One-dimensional Transform</A>).
		266
		267	The in-place option is mainly provided for people who want to write
		268	their own in-place multi-dimensional Fourier transform, using FFTW as a
		269	base. For example, consider a three-dimensional <CODE>n * n * n</CODE>
		270	transform. An out-of-place algorithm will need another array (which may
		271	be huge). However, FFTW can compute the in-place transform along
		272	each dimension using only a temporary array of size <CODE>n</CODE>.
		273	Moreover, if FFTW happens to be able to compute the transform truly
		274	in-place, no temporary array and no copying are needed. As distributed,
		275	FFTW `knows' how to compute in-place transforms of size 1, 2, 3, 4, 5, 6,
		276	7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32 and 64.
		277
		278	The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.
		279
		280	<LI>
		281
		282	<A NAME="IDX116"></A>
		283	<CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help
		284	in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)
		285	This can greatly speed the creation of plans, especially with the
		286	<CODE>FFTW_MEASURE</CODE> option. <CODE>FFTW_ESTIMATE</CODE> plans can also take
		287	advantage of <CODE>wisdom</CODE> to produce a more optimal plan (based on past
		288	measurements) than the estimation heuristic would normally
		289	generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>
		290	will also be generated if the current transform size is not completely
		291	understood by existing <CODE>wisdom</CODE>.
		292
		293	</UL>
		294
		295	<LI>
		296
		297	<CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for
		298	<CODE>fftw_create_plan_specific</CODE>): see corresponding arguments in the
		299	description of <CODE>fftw</CODE>. (See Section <A HREF="fftw_3.html#SEC21">Computing the One-dimensional Transform</A>.) In particular, the <CODE>out</CODE> and <CODE>ostride</CODE>
		300	parameters have the same special meaning for <CODE>FFTW_IN_PLACE</CODE>
		301	transforms as they have for <CODE>fftw</CODE>.
		302
		303	</UL>
		304
		305
		306
		307	<H3><A NAME="SEC20">Discussion on Specific Plans</A></H3>
		308	<P>
		309	<A NAME="IDX117"></A>
		310	We recommend the use of the specific planners, even in cases where you
		311	will be transforming arrays different from those passed to the specific
		312	planners, as they confer the following advantages:
		313
		314
		315
		316	<UL>
		317
		318	<LI>
		319
		320	The resulting plans will be optimized for your specific arrays and
		321	strides. This may or may not make a significant difference, but it
		322	certainly doesn't hurt. (The ordinary planner does its planning based
		323	upon a stride-one temporary array that it allocates.)
		324
		325	<LI>
		326
		327	Less intermediate storage is required during the planning process. (The
		328	ordinary planner uses O(<CODE>N</CODE>) temporary storage, where <CODE>N</CODE> is
		329	the maximum dimension, while it is creating the plan.)
		330
		331	<LI>
		332
		333	For multi-dimensional transforms, new parameters become accessible for
		334	optimization by the planner. (Since multi-dimensional arrays can be
		335	very large, we don't dare to allocate one in the ordinary planner for
		336	experimentation. This prevents us from doing certain optimizations
		337	that can yield dramatic improvements in some cases.)
		338
		339	</UL>
		340
		341	<P>
		342	On the other hand, note that <EM>the specific planner destroys the
		343	contents of the <CODE>in</CODE> and <CODE>out</CODE> arrays</EM>.
		344
		345
		346
		347
		348	<H3><A NAME="SEC21">Computing the One-dimensional Transform</A></H3>
		349
		350
		351	<PRE>
		352	#include <fftw.h>
		353
		354	void fftw(fftw_plan plan, int howmany,
		355	fftw_complex *in, int istride, int idist,
		356	fftw_complex *out, int ostride, int odist);
		357
		358	void fftw_one(fftw_plan plan, fftw_complex *in,
		359	fftw_complex *out);
		360	</PRE>
		361
		362	<P>
		363	<A NAME="IDX118"></A>
		364	<A NAME="IDX119"></A>
		365
		366
		367	<P>
		368	The function <CODE>fftw</CODE> computes the one-dimensional Fourier transform,
		369	using a plan created by <CODE>fftw_create_plan</CODE> (See Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>.) The function
		370	<CODE>fftw_one</CODE> provides a simplified interface for the common case of
		371	single input array of stride 1.
		372	<A NAME="IDX120"></A>
		373
		374
		375
		376	<H4>Arguments</H4>
		377
		378	<UL>
		379	<LI>
		380
		381	<CODE>plan</CODE> is the plan created by <CODE>fftw_create_plan</CODE>
		382	(see Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>).
		383
		384	<LI>
		385
		386	<CODE>howmany</CODE> is the number of transforms <CODE>fftw</CODE> will compute.
		387	It is faster to tell FFTW to compute many transforms, instead of
		388	simply calling <CODE>fftw</CODE> many times.
		389
		390	<LI>
		391
		392	<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
		393	There are <CODE>howmany</CODE> input arrays; the first one is pointed to by
		394	<CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on,
		395	up to <CODE>in + (howmany - 1) * idist</CODE>. Each input array consists of
		396	complex numbers (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>), which are not necessarily
		397	contiguous in memory. Specifically, <CODE>in[0]</CODE> is the first element
		398	of the first array, <CODE>in[istride]</CODE> is the second element of the
		399	first array, and so on. In general, the <CODE>i</CODE>-th element of the
		400	<CODE>j</CODE>-th input array will be in position <CODE>in[i * istride + j *
		401	idist]</CODE>.
		402
		403	<LI>
		404
		405	<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output
		406	array(s). The format is the same as for the input array.
		407
		408
		409	<UL>
		410	<LI><EM>In-place transforms</EM>:
		411
		412	<A NAME="IDX121"></A>
		413	If the <CODE>plan</CODE> specifies an in-place transform, <CODE>ostride</CODE> and
		414	<CODE>odist</CODE> are always ignored. If <CODE>out</CODE> is <CODE>NULL</CODE>,
		415	<CODE>out</CODE> is ignored, too. Otherwise, <CODE>out</CODE> is interpreted as a
		416	pointer to an array of <CODE>n</CODE> complex numbers, that FFTW will use as
		417	temporary space to perform the in-place computation. <CODE>out</CODE> is used
		418	as scratch space and its contents destroyed. In this case, <CODE>out</CODE>
		419	must be an ordinary array whose elements are contiguous in memory (no
		420	striding).
		421	</UL>
		422
		423	</UL>
		424
		425	<P>
		426	The function <CODE>fftw_one</CODE> transforms a single, contiguous input array
		427	to a contiguous output array. By definition, the call
		428
		429	<PRE>
		430	fftw_one(plan, in, out)
		431	</PRE>
		432
		433	<P>
		434	is equivalent to
		435
		436	<PRE>
		437	fftw(plan, 1, in, 1, 1, out, 1, 1)
		438	</PRE>
		439
		440
		441
		442	<H3><A NAME="SEC22">Destroying a One-dimensional Plan</A></H3>
		443
		444
		445	<PRE>
		446	#include <fftw.h>
		447
		448	void fftw_destroy_plan(fftw_plan plan);
		449	</PRE>
		450
		451	<P>
		452	<A NAME="IDX122"></A>
		453
		454
		455	<P>
		456	The function <CODE>fftw_destroy_plan</CODE> frees the plan <CODE>plan</CODE> and
		457	releases all the memory associated with it. After destruction, a plan
		458	is no longer valid.
		459
		460
		461
		462
		463	<H3><A NAME="SEC23">What FFTW Really Computes</A></H3>
		464	<P>
		465	<A NAME="IDX123"></A>
		466	In this section, we define precisely what FFTW computes. Please be
		467	warned that different authors and software packages might employ
		468	different conventions than FFTW does.
		469
		470
		471	<P>
		472	The forward transform of a complex array X of size
		473	n computes an array Y, where
		474	<center><IMG SRC="equation-1.gif" ALIGN="top"></center>
		475
		476
		477	<P>
		478	The backward transform computes
		479	<center><IMG SRC="equation-2.gif" ALIGN="top"></center>
		480
		481
		482	<P>
		483	<A NAME="IDX124"></A>
		484	FFTW computes an unnormalized transform, that is, the equation
		485	IFFT(FFT(X)) = n X holds. In other words, applying the forward
		486	and then the backward transform will multiply the input by n.
		487
		488
		489	<P>
		490	<A NAME="IDX125"></A>
		491	An <CODE>FFTW_FORWARD</CODE> transform corresponds to a sign of -1 in
		492	the exponent of the DFT. Note also that we use the standard
		493	"in-order" output ordering--the k-th output corresponds to the
		494	frequency k/n (or k/T, where T is your total
		495	sampling period). For those who like to think in terms of positive and
		496	negative frequencies, this means that the positive frequencies are
		497	stored in the first half of the output and the negative frequencies are
		498	stored in backwards order in the second half of the output. (The
		499	frequency -k/n is the same as the frequency (n-k)/n.)
		500
		501
		502
		503
		504	<H2><A NAME="SEC24">Multi-dimensional Transforms Reference</A></H2>
		505	<P>
		506	<A NAME="IDX126"></A>
		507	<A NAME="IDX127"></A>
		508	The multi-dimensional complex routines are generally prefixed with
		509	<CODE>fftwnd_</CODE>. Programs using FFTWND should be linked with <CODE>-lfftw
		510	-lm</CODE> on Unix systems, or with the FFTW and standard math libraries in
		511	general.
		512	<A NAME="IDX128"></A>
		513
		514
		515
		516
		517	<H3><A NAME="SEC25">Plan Creation for Multi-dimensional Transforms</A></H3>
		518
		519
		520	<PRE>
		521	#include <fftw.h>
		522
		523	fftwnd_plan fftwnd_create_plan(int rank, const int *n,
		524	fftw_direction dir, int flags);
		525
		526	fftwnd_plan fftw2d_create_plan(int nx, int ny,
		527	fftw_direction dir, int flags);
		528
		529	fftwnd_plan fftw3d_create_plan(int nx, int ny, int nz,
		530	fftw_direction dir, int flags);
		531
		532	fftwnd_plan fftwnd_create_plan_specific(int rank, const int *n,
		533	fftw_direction dir,
		534	int flags,
		535	fftw_complex *in, int istride,
		536	fftw_complex *out, int ostride);
		537
		538	fftwnd_plan fftw2d_create_plan_specific(int nx, int ny,
		539	fftw_direction dir,
		540	int flags,
		541	fftw_complex *in, int istride,
		542	fftw_complex *out, int ostride);
		543
		544	fftwnd_plan fftw3d_create_plan_specific(int nx, int ny, int nz,
		545	fftw_direction dir, int flags,
		546	fftw_complex *in, int istride,
		547	fftw_complex *out, int ostride);
		548	</PRE>
		549
		550	<P>
		551	<A NAME="IDX129"></A>
		552	<A NAME="IDX130"></A>
		553	<A NAME="IDX131"></A>
		554	<A NAME="IDX132"></A>
		555	<A NAME="IDX133"></A>
		556	<A NAME="IDX134"></A>
		557	<A NAME="IDX135"></A>
		558	<A NAME="IDX136"></A>
		559
		560
		561	<P>
		562	The function <CODE>fftwnd_create_plan</CODE> creates a plan, which is a data
		563	structure containing all the information that <CODE>fftwnd</CODE> needs in
		564	order to compute a multi-dimensional Fourier transform. You can create
		565	as many plans as you need, but only one plan for a given array size is
		566	required (a plan can be reused many times). The functions
		567	<CODE>fftw2d_create_plan</CODE> and <CODE>fftw3d_create_plan</CODE> are optional,
		568	alternative interfaces to <CODE>fftwnd_create_plan</CODE> for two and three
		569	dimensions, respectively.
		570
		571
		572	<P>
		573	<CODE>fftwnd_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for
		574	some reason, the plan can't be created. This can happen if memory runs
		575	out or if the arguments are invalid in some way (e.g. if <CODE>rank</CODE> <
		576	0).
		577
		578
		579	<P>
		580	The <CODE>create_plan_specific</CODE> variants take as additional arguments
		581	specific input/output arrays and their strides. For the last four
		582	arguments, you should pass the arrays and strides that you will
		583	eventually be passing to <CODE>fftwnd</CODE>. The resulting plans will be
		584	optimized for those arrays and strides, although they may be used on
		585	other arrays as well. Note: the contents of the in and out arrays are
		586	<EM>destroyed</EM> by the specific planner (the initial contents are
		587	ignored, so the arrays need not have been initialized).
		588	See Section <A HREF="fftw_3.html#SEC20">Discussion on Specific Plans</A>, for a discussion on specific plans.
		589
		590
		591
		592	<H4>Arguments</H4>
		593
		594	<UL>
		595	<LI>
		596
		597	<CODE>rank</CODE> is the dimensionality of the arrays to be transformed. It
		598	can be any non-negative integer.
		599
		600	<LI>
		601
		602	<CODE>n</CODE> is a pointer to an array of <CODE>rank</CODE> integers, giving the
		603	size of each dimension of the arrays to be transformed. These sizes,
		604	which must be positive integers, correspond to the dimensions of
		605	<A NAME="IDX137"></A>
		606	row-major arrays--i.e. <CODE>n[0]</CODE> is the size of the dimension whose
		607	indices vary most slowly, and so on. (See Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>, for more information on row-major storage.)
		608	See Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>,
		609	for more information regarding optimal array sizes.
		610
		611	<LI>
		612
		613	<CODE>nx</CODE> and <CODE>ny</CODE> in <CODE>fftw2d_create_plan</CODE> are positive
		614	integers specifying the dimensions of the rank 2 array to be
		615	transformed. i.e. they specify that the transform will operate on
		616	<CODE>nx x ny</CODE> arrays in row-major order, where <CODE>nx</CODE> is the number
		617	of rows and <CODE>ny</CODE> is the number of columns.
		618
		619	<LI>
		620
		621	<CODE>nx</CODE>, <CODE>ny</CODE> and <CODE>nz</CODE> in <CODE>fftw3d_create_plan</CODE> are
		622	positive integers specifying the dimensions of the rank 3 array to be
		623	transformed. i.e. they specify that the transform will operate on
		624	<CODE>nx x ny x nz</CODE> arrays in row-major order.
		625
		626	<LI>
		627
		628	<CODE>dir</CODE> is the sign of the exponent in the formula that defines the
		629	Fourier transform. It can be -1 or +1. The aliases
		630	<CODE>FFTW_FORWARD</CODE> and <CODE>FFTW_BACKWARD</CODE> are provided, where
		631	<CODE>FFTW_FORWARD</CODE> stands for -1.
		632
		633	<LI>
		634
		635	<A NAME="IDX138"></A>
		636	<CODE>flags</CODE> is a boolean OR (<SAMP>`\|'</SAMP>) of zero or more of the following:
		637
		638	<UL>
		639	<LI>
		640
		641	<CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by
		642	actually <EM>computing</EM> several FFTs and measuring their execution
		643	time.
		644
		645	<LI>
		646
		647	<CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"
		648	plan (for a RISC processor with many registers). If neither
		649	<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is
		650	<CODE>FFTW_ESTIMATE</CODE>.
		651
		652	<LI>
		653
		654	<CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input
		655	and output arrays will be distinct (this is the default).
		656
		657	<LI>
		658
		659	<CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want to perform
		660	the transform in-place. (Unlike the one-dimensional transform, this
		661	"really" <A NAME="DOCF3" HREF="fftw_foot.html#FOOT3">(3)</A> performs the
		662	transform in-place.) Note that, if you want to perform in-place
		663	transforms, you <EM>must</EM> use a plan created with this option.
		664
		665	The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.
		666
		667	<LI>
		668
		669	<A NAME="IDX139"></A>
		670	<CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help
		671	in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.) This can greatly
		672	speed the creation of plans, especially with the <CODE>FFTW_MEASURE</CODE>
		673	option. <CODE>FFTW_ESTIMATE</CODE> plans can also take advantage of
		674	<CODE>wisdom</CODE> to produce a more optimal plan (based on past
		675	measurements) than the estimation heuristic would normally
		676	generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>
		677	will also be generated if the current transform size is not completely
		678	understood by existing <CODE>wisdom</CODE>. Note that the same <CODE>wisdom</CODE>
		679	is shared between one-dimensional and multi-dimensional transforms.
		680
		681	</UL>
		682
		683	<LI>
		684
		685	<CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for the
		686	<CODE>_create_plan_specific</CODE> variants): see corresponding arguments in
		687	the description of <CODE>fftwnd</CODE>. (See Section <A HREF="fftw_3.html#SEC26">Computing the Multi-dimensional Transform</A>.)
		688
		689	</UL>
		690
		691
		692
		693	<H3><A NAME="SEC26">Computing the Multi-dimensional Transform</A></H3>
		694
		695
		696	<PRE>
		697	#include <fftw.h>
		698
		699	void fftwnd(fftwnd_plan plan, int howmany,
		700	fftw_complex *in, int istride, int idist,
		701	fftw_complex *out, int ostride, int odist);
		702
		703	void fftwnd_one(fftwnd_plan p, fftw_complex *in,
		704	fftw_complex *out);
		705	</PRE>
		706
		707	<P>
		708	<A NAME="IDX140"></A>
		709	<A NAME="IDX141"></A>
		710
		711
		712	<P>
		713	The function <CODE>fftwnd</CODE> computes the multi-dimensional Fourier
		714	Transform, using a plan created by <CODE>fftwnd_create_plan</CODE>
		715	(see Section <A HREF="fftw_3.html#SEC25">Plan Creation for Multi-dimensional Transforms</A>). (Note that the plan determines the rank and dimensions of
		716	the array to be transformed.) The function <CODE>fftwnd_one</CODE> provides a
		717	simplified interface for the common case of single input array of stride
		718	1.
		719	<A NAME="IDX142"></A>
		720
		721
		722
		723	<H4>Arguments</H4>
		724
		725	<UL>
		726	<LI>
		727
		728	<CODE>plan</CODE> is the plan created by <CODE>fftwnd_create_plan</CODE>.
		729	(see Section <A HREF="fftw_3.html#SEC25">Plan Creation for Multi-dimensional Transforms</A>). In the case of two and three-dimensional transforms, it
		730	could also have been created by <CODE>fftw2d_create_plan</CODE> or
		731	<CODE>fftw3d_create_plan</CODE>, respectively.
		732
		733	<LI>
		734
		735	<CODE>howmany</CODE> is the number of transforms <CODE>fftwnd</CODE> will compute.
		736
		737	<LI>
		738
		739	<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
		740	There are <CODE>howmany</CODE> input arrays; the first one is pointed to by
		741	<CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on,
		742	up to <CODE>in + (howmany - 1) * idist</CODE>. Each input array consists of
		743	complex numbers (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>), stored in row-major format
		744	(see Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>), which are not necessarily
		745	contiguous in memory. Specifically, <CODE>in[0]</CODE> is the first element
		746	of the first array, <CODE>in[istride]</CODE> is the second element of the
		747	first array, and so on. In general, the <CODE>i</CODE>-th element of the
		748	<CODE>j</CODE>-th input array will be in position <CODE>in[i * istride + j *
		749	idist]</CODE>. Note that, here, <CODE>i</CODE> refers to an index into the row-major
		750	format for the multi-dimensional array, rather than an index in any
		751	particular dimension.
		752
		753
		754	<UL>
		755	<LI><EM>In-place transforms</EM>:
		756
		757	<A NAME="IDX143"></A>
		758	For plans created with the <CODE>FFTW_IN_PLACE</CODE> option, the transform is
		759	computed in-place--the output is returned in the <CODE>in</CODE> array, using
		760	the same strides, etcetera, as were used in the input.
		761	</UL>
		762
		763	<LI>
		764
		765	<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output array(s).
		766	The format is the same as for the input array.
		767
		768
		769	<UL>
		770	<LI><EM>In-place transforms</EM>:
		771
		772	These parameters are ignored for plans created with the
		773	<CODE>FFTW_IN_PLACE</CODE> option.
		774	</UL>
		775
		776	</UL>
		777
		778	<P>
		779	The function <CODE>fftwnd_one</CODE> transforms a single, contiguous input
		780	array to a contiguous output array. By definition, the call
		781
		782	<PRE>
		783	fftwnd_one(plan, in, out)
		784	</PRE>
		785
		786	<P>
		787	is equivalent to
		788
		789	<PRE>
		790	fftwnd(plan, 1, in, 1, 1, out, 1, 1)
		791	</PRE>
		792
		793
		794
		795	<H3><A NAME="SEC27">Destroying a Multi-dimensional Plan</A></H3>
		796
		797
		798	<PRE>
		799	#include <fftw.h>
		800
		801	void fftwnd_destroy_plan(fftwnd_plan plan);
		802	</PRE>
		803
		804	<P>
		805	<A NAME="IDX144"></A>
		806
		807
		808	<P>
		809	The function <CODE>fftwnd_destroy_plan</CODE> frees the plan <CODE>plan</CODE>
		810	and releases all the memory associated with it. After destruction,
		811	a plan is no longer valid.
		812
		813
		814
		815
		816	<H3><A NAME="SEC28">What FFTWND Really Computes</A></H3>
		817	<P>
		818	<A NAME="IDX145"></A>
		819
		820
		821	<P>
		822	The conventions that we follow for the multi-dimensional transform are
		823	analogous to those for the one-dimensional transform. In particular, the
		824	forward transform has a negative sign in the exponent and neither the
		825	forward nor the backward transforms will perform any normalization.
		826	Computing the backward transform of the forward transform will multiply
		827	the array by the product of its dimensions. The output is in-order, and
		828	the zeroth element of the output is the amplitude of the zero frequency
		829	component.
		830
		831
		832	The Gods forbade using HTML to display mathematical formulas. Please
		833	see the TeX or Postscript version of this manual for the proper
		834	definition of the n-dimensional Fourier transform that FFTW
		835	uses. For completeness, we include a bitmap of the TeX output below:
		836	<P><center><IMG SRC="equation-3.gif" ALIGN="top"></center>
		837
		838
		839
		840	<H2><A NAME="SEC29">Real One-dimensional Transforms Reference</A></H2>
		841
		842	<P>
		843	The one-dimensional real routines are generally prefixed with
		844	<CODE>rfftw_</CODE>. <A NAME="DOCF4" HREF="fftw_foot.html#FOOT4">(4)</A> Programs using RFFTW
		845	should be linked with <CODE>-lrfftw -lfftw -lm</CODE> on Unix systems, or with
		846	the RFFTW, the FFTW, and the standard math libraries in general.
		847	<A NAME="IDX146"></A>
		848	<A NAME="IDX147"></A>
		849	<A NAME="IDX148"></A>
		850
		851
		852
		853
		854	<H3><A NAME="SEC30">Plan Creation for Real One-dimensional Transforms</A></H3>
		855
		856
		857	<PRE>
		858	#include <rfftw.h>
		859
		860	rfftw_plan rfftw_create_plan(int n, fftw_direction dir, int flags);
		861
		862	rfftw_plan rfftw_create_plan_specific(int n, fftw_direction dir,
		863	int flags, fftw_real *in, int istride,
		864	fftw_real *out, int ostride);
		865	</PRE>
		866
		867	<P>
		868	<A NAME="IDX149"></A>
		869	<A NAME="IDX150"></A>
		870	<A NAME="IDX151"></A>
		871
		872
		873	<P>
		874	The function <CODE>rfftw_create_plan</CODE> creates a plan, which is a data
		875	structure containing all the information that <CODE>rfftw</CODE> needs in
		876	order to compute the 1D real Fourier transform. You can create as many
		877	plans as you need, but only one plan for a given array size is required
		878	(a plan can be reused many times).
		879
		880
		881	<P>
		882	<CODE>rfftw_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for
		883	some reason, the plan can't be created. In the default installation,
		884	this cannot happen, but it is possible to configure RFFTW in such a way
		885	that some input sizes are forbidden, and RFFTW cannot create a plan.
		886
		887
		888	<P>
		889	The <CODE>rfftw_create_plan_specific</CODE> variant takes as additional
		890	arguments specific input/output arrays and their strides. For the last
		891	four arguments, you should pass the arrays and strides that you will
		892	eventually be passing to <CODE>rfftw</CODE>. The resulting plans will be
		893	optimized for those arrays and strides, although they may be used on
		894	other arrays as well. Note: the contents of the in and out arrays are
		895	<EM>destroyed</EM> by the specific planner (the initial contents are
		896	ignored, so the arrays need not have been initialized).
		897	See Section <A HREF="fftw_3.html#SEC20">Discussion on Specific Plans</A>, for a discussion on specific plans.
		898
		899
		900
		901	<H4>Arguments</H4>
		902
		903	<UL>
		904	<LI>
		905
		906	<CODE>n</CODE> is the size of the transform. It can be
		907	any positive integer.
		908
		909
		910	<UL>
		911	<LI>
		912
		913	RFFTW is best at handling sizes of the form
		914	2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP>
		915	11<SUP>e</SUP> 13<SUP>f</SUP>,
		916	where e+f is either 0 or
		917	1, and the other exponents are arbitrary. Other sizes are
		918	computed by means of a slow, general-purpose routine (reducing to
		919	O(n<sup>2</sup>)
		920	performance for prime sizes). (It is possible to customize RFFTW for
		921	different array sizes. See Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>, for more
		922	information.) Transforms whose sizes are powers of 2 are
		923	especially fast.
		924	</UL>
		925
		926	<LI>
		927
		928	<CODE>dir</CODE> is the direction of the desired transform, either
		929	<CODE>FFTW_REAL_TO_COMPLEX</CODE> or <CODE>FFTW_COMPLEX_TO_REAL</CODE>,
		930	corresponding to <CODE>FFTW_FORWARD</CODE> or <CODE>FFTW_BACKWARD</CODE>,
		931	respectively.
		932	<A NAME="IDX152"></A>
		933	<A NAME="IDX153"></A>
		934
		935	<LI>
		936
		937	<A NAME="IDX154"></A>
		938	<CODE>flags</CODE> is a boolean OR (<SAMP>`\|'</SAMP>) of zero or more of the following:
		939
		940	<UL>
		941	<LI>
		942
		943	<CODE>FFTW_MEASURE</CODE>: this flag tells RFFTW to find the optimal plan by
		944	actually <EM>computing</EM> several FFTs and measuring their
		945	execution time. Depending on the installation, this can take some
		946	time.
		947
		948	<LI>
		949
		950	<CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"
		951	plan (for a RISC processor with many registers). If neither
		952	<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is
		953	<CODE>FFTW_ESTIMATE</CODE>.
		954
		955	<LI>
		956
		957	<CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input
		958	and output arrays will be distinct (this is the default).
		959
		960	<LI>
		961
		962	<CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want the output
		963	in the input array. The algorithm used is not necessarily in place:
		964	RFFTW is able to compute true in-place transforms only for small values
		965	of <CODE>n</CODE>. If RFFTW is not able to compute the transform in-place, it
		966	will allocate a temporary array (unless you provide one yourself),
		967	compute the transform out of place, and copy the result back.
		968	<EM>Warning: This option changes the meaning of some parameters of
		969	<CODE>rfftw</CODE></EM> (see Section <A HREF="fftw_3.html#SEC31">Computing the Real One-dimensional Transform</A>).
		970
		971	The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.
		972
		973	<LI>
		974
		975	<CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help
		976	in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)
		977	This can greatly speed the creation of plans, especially with the
		978	<CODE>FFTW_MEASURE</CODE> option. <CODE>FFTW_ESTIMATE</CODE> plans can also take
		979	advantage of <CODE>wisdom</CODE> to produce a more optimal plan (based on past
		980	measurements) than the estimation heuristic would normally
		981	generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>
		982	will also be generated if the current transform size is not completely
		983	understood by existing <CODE>wisdom</CODE>.
		984
		985	</UL>
		986
		987	<LI>
		988
		989	<CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for
		990	<CODE>rfftw_create_plan_specific</CODE>): see corresponding arguments in the
		991	description of <CODE>rfftw</CODE>. (See Section <A HREF="fftw_3.html#SEC31">Computing the Real One-dimensional Transform</A>.) In particular, the <CODE>out</CODE> and
		992	<CODE>ostride</CODE> parameters have the same special meaning for
		993	<CODE>FFTW_IN_PLACE</CODE> transforms as they have for <CODE>rfftw</CODE>.
		994
		995	</UL>
		996
		997
		998
		999	<H3><A NAME="SEC31">Computing the Real One-dimensional Transform</A></H3>
		1000
		1001
		1002	<PRE>
		1003	#include <rfftw.h>
		1004
		1005	void rfftw(rfftw_plan plan, int howmany,
		1006	fftw_real *in, int istride, int idist,
		1007	fftw_real *out, int ostride, int odist);
		1008
		1009	void rfftw_one(rfftw_plan plan, fftw_real in, fftw_real out);
		1010	</PRE>
		1011
		1012	<P>
		1013	<A NAME="IDX155"></A>
		1014	<A NAME="IDX156"></A>
		1015
		1016
		1017	<P>
		1018	The function <CODE>rfftw</CODE> computes the Real One-dimensional Fourier
		1019	Transform, using a plan created by <CODE>rfftw_create_plan</CODE>
		1020	(see Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>). The function <CODE>rfftw_one</CODE> provides a simplified
		1021	interface for the common case of single input array of stride 1.
		1022	<A NAME="IDX157"></A>
		1023
		1024
		1025	<P>
		1026	<EM>Important:</EM> When invoked for an out-of-place,
		1027	<CODE>FFTW_COMPLEX_TO_REAL</CODE> transform, the input array is overwritten
		1028	with scratch values by these routines. The input array is not modified
		1029	for <CODE>FFTW_REAL_TO_COMPLEX</CODE> transforms.
		1030
		1031
		1032
		1033	<H4>Arguments</H4>
		1034
		1035	<UL>
		1036	<LI>
		1037
		1038	<CODE>plan</CODE> is the plan created by <CODE>rfftw_create_plan</CODE>
		1039	(see Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>).
		1040
		1041	<LI>
		1042
		1043	<CODE>howmany</CODE> is the number of transforms <CODE>rfftw</CODE> will compute.
		1044	It is faster to tell RFFTW to compute many transforms, instead of
		1045	simply calling <CODE>rfftw</CODE> many times.
		1046
		1047	<LI>
		1048
		1049	<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
		1050	There are two cases. If the <CODE>plan</CODE> defines a
		1051	<CODE>FFTW_REAL_TO_COMPLEX</CODE> transform, <CODE>in</CODE> is a real array.
		1052	Otherwise, for <CODE>FFTW_COMPLEX_TO_REAL</CODE> transforms, <CODE>in</CODE> is a
		1053	halfcomplex array <EM>whose contents will be destroyed</EM>.
		1054
		1055	<LI>
		1056
		1057	<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output
		1058	array(s), and have the same meaning as the corresponding parameters for
		1059	the input array.
		1060
		1061
		1062	<UL>
		1063	<LI><EM>In-place transforms</EM>:
		1064
		1065	If the <CODE>plan</CODE> specifies an in-place transform, <CODE>ostride</CODE> and
		1066	<CODE>odist</CODE> are always ignored. If <CODE>out</CODE> is <CODE>NULL</CODE>,
		1067	<CODE>out</CODE> is ignored, too. Otherwise, <CODE>out</CODE> is interpreted as a
		1068	pointer to an array of <CODE>n</CODE> complex numbers, that FFTW will use as
		1069	temporary space to perform the in-place computation. <CODE>out</CODE> is used
		1070	as scratch space and its contents destroyed. In this case, <CODE>out</CODE>
		1071	must be an ordinary array whose elements are contiguous in memory (no
		1072	striding).
		1073	</UL>
		1074
		1075	</UL>
		1076
		1077	<P>
		1078	The function <CODE>rfftw_one</CODE> transforms a single, contiguous input array
		1079	to a contiguous output array. By definition, the call
		1080
		1081	<PRE>
		1082	rfftw_one(plan, in, out)
		1083	</PRE>
		1084
		1085	<P>
		1086	is equivalent to
		1087
		1088	<PRE>
		1089	rfftw(plan, 1, in, 1, 1, out, 1, 1)
		1090	</PRE>
		1091
		1092
		1093
		1094	<H3><A NAME="SEC32">Destroying a Real One-dimensional Plan</A></H3>
		1095
		1096
		1097	<PRE>
		1098	#include <rfftw.h>
		1099
		1100	void rfftw_destroy_plan(rfftw_plan plan);
		1101	</PRE>
		1102
		1103	<P>
		1104	<A NAME="IDX158"></A>
		1105
		1106
		1107	<P>
		1108	The function <CODE>rfftw_destroy_plan</CODE> frees the plan <CODE>plan</CODE> and
		1109	releases all the memory associated with it. After destruction, a plan
		1110	is no longer valid.
		1111
		1112
		1113
		1114
		1115	<H3><A NAME="SEC33">What RFFTW Really Computes</A></H3>
		1116	<P>
		1117	<A NAME="IDX159"></A>
		1118	In this section, we define precisely what RFFTW computes.
		1119
		1120
		1121	<P>
		1122	The real to complex (<CODE>FFTW_REAL_TO_COMPLEX</CODE>) transform of a real
		1123	array X of size n computes an hermitian array Y,
		1124	where
		1125	<center><IMG SRC="equation-1.gif" ALIGN="top"></center>
		1126	(That Y is a hermitian array is not intended to be obvious,
		1127	although the proof is easy.) The hermitian array Y is stored in
		1128	halfcomplex order (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>). Currently, RFFTW provides no
		1129	way to compute a real to complex transform with a positive sign in the
		1130	exponent.
		1131
		1132
		1133	<P>
		1134	The complex to real (<CODE>FFTW_COMPLEX_TO_REAL</CODE>) transform of a hermitian
		1135	array X of size n computes a real array Y, where
		1136	<center><IMG SRC="equation-2.gif" ALIGN="top"></center>
		1137	(That Y is a real array is not intended to be obvious, although
		1138	the proof is easy.) The hermitian input array X is stored in
		1139	halfcomplex order (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>). Currently, RFFTW provides no
		1140	way to compute a complex to real transform with a negative sign in the
		1141	exponent.
		1142
		1143
		1144	<P>
		1145	<A NAME="IDX160"></A>
		1146	Like FFTW, RFFTW computes an unnormalized transform. In other words,
		1147	applying the real to complex (forward) and then the complex to real
		1148	(backward) transform will multiply the input by n.
		1149
		1150
		1151
		1152
		1153	<H2><A NAME="SEC34">Real Multi-dimensional Transforms Reference</A></H2>
		1154	<P>
		1155	<A NAME="IDX161"></A>
		1156	<A NAME="IDX162"></A>
		1157
		1158
		1159	<P>
		1160	The multi-dimensional real routines are generally prefixed with
		1161	<CODE>rfftwnd_</CODE>. Programs using RFFTWND should be linked with
		1162	<CODE>-lrfftw -lfftw -lm</CODE> on Unix systems, or with the FFTW, RFFTW, and
		1163	standard math libraries in general.
		1164	<A NAME="IDX163"></A>
		1165
		1166
		1167
		1168
		1169	<H3><A NAME="SEC35">Plan Creation for Real Multi-dimensional Transforms</A></H3>
		1170
		1171
		1172	<PRE>
		1173	#include <rfftw.h>
		1174
		1175	rfftwnd_plan rfftwnd_create_plan(int rank, const int *n,
		1176	fftw_direction dir, int flags);
		1177
		1178	rfftwnd_plan rfftw2d_create_plan(int nx, int ny,
		1179	fftw_direction dir, int flags);
		1180
		1181	rfftwnd_plan rfftw3d_create_plan(int nx, int ny, int nz,
		1182	fftw_direction dir, int flags);
		1183	</PRE>
		1184
		1185	<P>
		1186	<A NAME="IDX164"></A>
		1187	<A NAME="IDX165"></A>
		1188	<A NAME="IDX166"></A>
		1189	<A NAME="IDX167"></A>
		1190	<A NAME="IDX168"></A>
		1191
		1192
		1193	<P>
		1194	The function <CODE>rfftwnd_create_plan</CODE> creates a plan, which is a data
		1195	structure containing all the information that <CODE>rfftwnd</CODE> needs in
		1196	order to compute a multi-dimensional real Fourier transform. You can
		1197	create as many plans as you need, but only one plan for a given array
		1198	size is required (a plan can be reused many times). The functions
		1199	<CODE>rfftw2d_create_plan</CODE> and <CODE>rfftw3d_create_plan</CODE> are optional,
		1200	alternative interfaces to <CODE>rfftwnd_create_plan</CODE> for two and three
		1201	dimensions, respectively.
		1202
		1203
		1204	<P>
		1205	<CODE>rfftwnd_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for
		1206	some reason, the plan can't be created. This can happen if the
		1207	arguments are invalid in some way (e.g. if <CODE>rank</CODE> < 0).
		1208
		1209
		1210
		1211	<H4>Arguments</H4>
		1212
		1213	<UL>
		1214	<LI>
		1215
		1216	<CODE>rank</CODE> is the dimensionality of the arrays to be transformed. It
		1217	can be any non-negative integer.
		1218
		1219	<LI>
		1220
		1221	<CODE>n</CODE> is a pointer to an array of <CODE>rank</CODE> integers, giving the
		1222	size of each dimension of the arrays to be transformed. Note that these
		1223	are always the dimensions of the <EM>real</EM> arrays; the complex arrays
		1224	have different dimensions (see Section <A HREF="fftw_3.html#SEC37">Array Dimensions for Real Multi-dimensional Transforms</A>). These sizes, which must be positive
		1225	integers, correspond to the dimensions of row-major
		1226	arrays--i.e. <CODE>n[0]</CODE> is the size of the dimension whose indices
		1227	vary most slowly, and so on. (See Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>, for
		1228	more information.)
		1229
		1230	<UL>
		1231	<LI>
		1232
		1233	See Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>,
		1234	for more information regarding optimal array sizes.
		1235	</UL>
		1236
		1237	<LI>
		1238
		1239	<CODE>nx</CODE> and <CODE>ny</CODE> in <CODE>rfftw2d_create_plan</CODE> are positive
		1240	integers specifying the dimensions of the rank 2 array to be
		1241	transformed. i.e. they specify that the transform will operate on
		1242	<CODE>nx x ny</CODE> arrays in row-major order, where <CODE>nx</CODE> is the number
		1243	of rows and <CODE>ny</CODE> is the number of columns.
		1244
		1245	<LI>
		1246
		1247	<CODE>nx</CODE>, <CODE>ny</CODE> and <CODE>nz</CODE> in <CODE>rfftw3d_create_plan</CODE> are
		1248	positive integers specifying the dimensions of the rank 3 array to be
		1249	transformed. i.e. they specify that the transform will operate on
		1250	<CODE>nx x ny x nz</CODE> arrays in row-major order.
		1251
		1252	<LI>
		1253
		1254	<CODE>dir</CODE> is the direction of the desired transform, either
		1255	<CODE>FFTW_REAL_TO_COMPLEX</CODE> or <CODE>FFTW_COMPLEX_TO_REAL</CODE>,
		1256	corresponding to <CODE>FFTW_FORWARD</CODE> or <CODE>FFTW_BACKWARD</CODE>,
		1257	respectively.
		1258
		1259	<LI>
		1260
		1261	<A NAME="IDX169"></A>
		1262	<CODE>flags</CODE> is a boolean OR (<SAMP>`\|'</SAMP>) of zero or more of the following:
		1263
		1264	<UL>
		1265	<LI>
		1266
		1267	<CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by
		1268	actually <EM>computing</EM> several FFTs and measuring their execution
		1269	time.
		1270
		1271	<LI>
		1272
		1273	<CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"
		1274	plan (for a RISC processor with many registers). If neither
		1275	<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is
		1276	<CODE>FFTW_ESTIMATE</CODE>.
		1277
		1278	<LI>
		1279
		1280	<CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input
		1281	and output arrays will be distinct (this is the default).
		1282
		1283	<LI>
		1284
		1285	<A NAME="IDX170"></A>
		1286	<CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want to perform
		1287	the transform in-place. (Unlike the one-dimensional transform, this
		1288	"really" performs the transform in-place.) Note that, if you want to
		1289	perform in-place transforms, you <EM>must</EM> use a plan created with
		1290	this option. The use of this option has important implications for the
		1291	size of the input/output array (see Section <A HREF="fftw_3.html#SEC36">Computing the Real Multi-dimensional Transform</A>).
		1292
		1293	The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.
		1294
		1295	<LI>
		1296
		1297	<A NAME="IDX171"></A>
		1298	<CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help
		1299	in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.) This can greatly
		1300	speed the creation of plans, especially with the <CODE>FFTW_MEASURE</CODE>
		1301	option. <CODE>FFTW_ESTIMATE</CODE> plans can also take advantage of
		1302	<CODE>wisdom</CODE> to produce a more optimal plan (based on past
		1303	measurements) than the estimation heuristic would normally
		1304	generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>
		1305	will also be generated if the current transform size is not completely
		1306	understood by existing <CODE>wisdom</CODE>. Note that the same <CODE>wisdom</CODE>
		1307	is shared between one-dimensional and multi-dimensional transforms.
		1308
		1309	</UL>
		1310
		1311	</UL>
		1312
		1313
		1314
		1315	<H3><A NAME="SEC36">Computing the Real Multi-dimensional Transform</A></H3>
		1316
		1317
		1318	<PRE>
		1319	#include <rfftw.h>
		1320
		1321	void rfftwnd_real_to_complex(rfftwnd_plan plan, int howmany,
		1322	fftw_real *in, int istride, int idist,
		1323	fftw_complex *out, int ostride, int odist);
		1324	void rfftwnd_complex_to_real(rfftwnd_plan plan, int howmany,
		1325	fftw_complex *in, int istride, int idist,
		1326	fftw_real *out, int ostride, int odist);
		1327
		1328	void rfftwnd_one_real_to_complex(rfftwnd_plan p, fftw_real *in,
		1329	fftw_complex *out);
		1330	void rfftwnd_one_complex_to_real(rfftwnd_plan p, fftw_complex *in,
		1331	fftw_real *out);
		1332	</PRE>
		1333
		1334	<P>
		1335	<A NAME="IDX172"></A>
		1336	<A NAME="IDX173"></A>
		1337	<A NAME="IDX174"></A>
		1338	<A NAME="IDX175"></A>
		1339
		1340
		1341	<P>
		1342	These functions compute the real multi-dimensional Fourier Transform,
		1343	using a plan created by <CODE>rfftwnd_create_plan</CODE>
		1344	(see Section <A HREF="fftw_3.html#SEC35">Plan Creation for Real Multi-dimensional Transforms</A>). (Note that the plan determines the rank and dimensions of
		1345	the array to be transformed.) The <SAMP>`<CODE>rfftwnd_one_</CODE>'</SAMP> functions
		1346	provide a simplified interface for the common case of single input array
		1347	of stride 1. Unlike other transform routines in FFTW, we here use
		1348	separate functions for the two directions of the transform in order to
		1349	correctly express the datatypes of the parameters.
		1350
		1351
		1352	<P>
		1353	<EM>Important:</EM> When invoked for an out-of-place,
		1354	<CODE>FFTW_COMPLEX_TO_REAL</CODE> transform with <CODE>rank > 1</CODE>, the input
		1355	array is overwritten with scratch values by these routines. The input
		1356	array is not modified for <CODE>FFTW_REAL_TO_COMPLEX</CODE> transforms or for
		1357	<CODE>FFTW_COMPLEX_TO_REAL</CODE> with <CODE>rank == 1</CODE>.
		1358
		1359
		1360
		1361	<H4>Arguments</H4>
		1362
		1363	<UL>
		1364	<LI>
		1365
		1366	<CODE>plan</CODE> is the plan created by <CODE>rfftwnd_create_plan</CODE>.
		1367	(see Section <A HREF="fftw_3.html#SEC35">Plan Creation for Real Multi-dimensional Transforms</A>). In the case of two and three-dimensional transforms, it
		1368	could also have been created by <CODE>rfftw2d_create_plan</CODE> or
		1369	<CODE>rfftw3d_create_plan</CODE>, respectively.
		1370
		1371	<CODE>FFTW_REAL_TO_COMPLEX</CODE> plans must be used with the
		1372	<SAMP>`<CODE>real_to_complex</CODE>'</SAMP> functions, and <CODE>FFTW_COMPLEX_TO_REAL</CODE>
		1373	plans must be used with the <SAMP>`<CODE>complex_to_real</CODE>'</SAMP> functions. It
		1374	is an error to mismatch the plan direction and the transform function.
		1375
		1376	<LI>
		1377
		1378	<CODE>howmany</CODE> is the number of transforms to be computed.
		1379
		1380	<LI>
		1381
		1382	<A NAME="IDX176"></A>
		1383	<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
		1384	There are <CODE>howmany</CODE> input arrays; the first one is pointed to by
		1385	<CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on,
		1386	up to <CODE>in + (howmany - 1) * idist</CODE>. Each input array is stored in
		1387	row-major format (see Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>), and is not
		1388	necessarily contiguous in memory. Specifically, <CODE>in[0]</CODE> is the
		1389	first element of the first array, <CODE>in[istride]</CODE> is the second
		1390	element of the first array, and so on. In general, the <CODE>i</CODE>-th
		1391	element of the <CODE>j</CODE>-th input array will be in position <CODE>in[i *
		1392	istride + j * idist]</CODE>. Note that, here, <CODE>i</CODE> refers to an index into
		1393	the row-major format for the multi-dimensional array, rather than an
		1394	index in any particular dimension.
		1395
		1396	The dimensions of the arrays are different for real and complex data,
		1397	and are discussed in more detail below (see Section <A HREF="fftw_3.html#SEC37">Array Dimensions for Real Multi-dimensional Transforms</A>).
		1398
		1399
		1400	<UL>
		1401	<LI><EM>In-place transforms</EM>:
		1402
		1403	For plans created with the <CODE>FFTW_IN_PLACE</CODE> option, the transform is
		1404	computed in-place--the output is returned in the <CODE>in</CODE> array. The
		1405	meaning of the <CODE>stride</CODE> and <CODE>dist</CODE> parameters in this case is
		1406	subtle and is discussed below (see Section <A HREF="fftw_3.html#SEC38">Strides in In-place RFFTWND</A>).
		1407	</UL>
		1408
		1409	<LI>
		1410
		1411	<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output
		1412	array(s). The format is the same as that for the input array. See
		1413	below for a discussion of the dimensions of the output array for real
		1414	and complex data.
		1415
		1416
		1417	<UL>
		1418	<LI><EM>In-place transforms</EM>:
		1419
		1420	These parameters are ignored for plans created with the
		1421	<CODE>FFTW_IN_PLACE</CODE> option.
		1422	</UL>
		1423
		1424	</UL>
		1425
		1426	<P>
		1427	The function <CODE>rfftwnd_one</CODE> transforms a single, contiguous input
		1428	array to a contiguous output array. By definition, the call
		1429
		1430	<PRE>
		1431	rfftwnd_one_...(plan, in, out)
		1432	</PRE>
		1433
		1434	<P>
		1435	is equivalent to
		1436
		1437	<PRE>
		1438	rfftwnd_...(plan, 1, in, 1, 1, out, 1, 1)
		1439	</PRE>
		1440
		1441
		1442
		1443	<H3><A NAME="SEC37">Array Dimensions for Real Multi-dimensional Transforms</A></H3>
		1444
		1445	<P>
		1446	<A NAME="IDX177"></A>
		1447	The output of a multi-dimensional transform of real data contains
		1448	symmetries that, in principle, make half of the outputs redundant
		1449	(see Section <A HREF="fftw_3.html#SEC40">What RFFTWND Really Computes</A>). In practice, it is not
		1450	possible to entirely realize these savings in an efficient and
		1451	understandable format. Instead, the output of the rfftwnd transforms is
		1452	<EM>slightly</EM> over half of the output of the corresponding complex
		1453	transform. We do not "pack" the data in any way, but store it as an
		1454	ordinary array of <CODE>fftw_complex</CODE> values. In fact, this data is
		1455	simply a subsection of what would be the array in the corresponding
		1456	complex transform.
		1457
		1458
		1459	<P>
		1460	Specifically, for a real transform of dimensions
		1461	n<sub>1</sub> x n<sub>2</sub> x ... x n<sub>d</sub>,
		1462	the complex data is an
		1463	n<sub>1</sub> x n<sub>2</sub> x ... x (n<sub>d</sub>/2+1)
		1464	array of <CODE>fftw_complex</CODE> values in row-major order (with the
		1465	division rounded down). That is, we only store the lower half (plus one
		1466	element) of the last dimension of the data from the ordinary complex
		1467	transform. (We could have instead taken half of any other dimension,
		1468	but implementation turns out to be simpler if the last, contiguous,
		1469	dimension is used.)
		1470
		1471
		1472	<P>
		1473	<A NAME="IDX178"></A>
		1474	<A NAME="IDX179"></A>
		1475	Since the complex data is slightly larger than the real data, some
		1476	complications arise for in-place transforms. In this case, the final
		1477	dimension of the real data must be padded with extra values to
		1478	accommodate the size of the complex data--two extra if the last
		1479	dimension is even and one if it is odd. That is, the last dimension of
		1480	the real data must physically contain
		1481	2 * (n<sub>d</sub>/2+1)
		1482	<CODE>fftw_real</CODE> values (exactly enough to hold the complex data).
		1483	This physical array size does not, however, change the <EM>logical</EM>
		1484	array size--only
		1485	n<sub>d</sub>
		1486	values are actually stored in the last dimension, and
		1487	n<sub>d</sub>
		1488	is the last dimension passed to <CODE>rfftwnd_create_plan</CODE>.
		1489
		1490
		1491
		1492
		1493	<H3><A NAME="SEC38">Strides in In-place RFFTWND</A></H3>
		1494
		1495	<P>
		1496	<A NAME="IDX180"></A>
		1497	<A NAME="IDX181"></A>
		1498	The fact that the input and output datatypes are different for rfftwnd
		1499	complicates the meaning of the <CODE>stride</CODE> and <CODE>dist</CODE> parameters
		1500	of in-place transforms--are they in units of <CODE>fftw_real</CODE> or
		1501	<CODE>fftw_complex</CODE> elements? When reading the input, they are
		1502	interpreted in units of the datatype of the input data. When writing
		1503	the output, the <CODE>istride</CODE> and <CODE>idist</CODE> are translated to the
		1504	output datatype's "units" in one of two ways, corresponding to the two
		1505	most common situations in which <CODE>stride</CODE> and <CODE>dist</CODE> parameters
		1506	are useful. Below, we refer to these "translated" parameters as
		1507	<CODE>ostride_t</CODE> and <CODE>odist_t</CODE>. (Note that these are computed
		1508	internally by rfftwnd; the actual <CODE>ostride</CODE> and <CODE>odist</CODE>
		1509	parameters are ignored for in-place transforms.)
		1510
		1511
		1512	<P>
		1513	First, there is the case where you are transforming a number of
		1514	contiguous arrays located one after another in memory. In this
		1515	situation, <CODE>istride</CODE> is <CODE>1</CODE> and <CODE>idist</CODE> is the product of
		1516	the physical dimensions of the array. <CODE>ostride_t</CODE> and
		1517	<CODE>odist_t</CODE> are then chosen so that the output arrays are contiguous
		1518	and lie on top of the input arrays. <CODE>ostride_t</CODE> is therefore
		1519	<CODE>1</CODE>. For a real-to-complex transform, <CODE>odist_t</CODE> is
		1520	<CODE>idist/2</CODE>; for a complex-to-real transform, <CODE>odist_t</CODE> is
		1521	<CODE>idist*2</CODE>.
		1522
		1523
		1524	<P>
		1525	The second case is when you have an array in which each element has
		1526	<CODE>nc</CODE> components (e.g. a structure with <CODE>nc</CODE> numeric fields),
		1527	and you want to transform all of the components at once. Here,
		1528	<CODE>istride</CODE> is <CODE>nc</CODE> and <CODE>idist</CODE> is <CODE>1</CODE>. For this
		1529	case, it is natural to want the output to also have <CODE>nc</CODE>
		1530	consecutive components, now of the output data type; this is exactly
		1531	what rfftwnd does. Specifically, it uses an <CODE>ostride_t</CODE> equal to
		1532	<CODE>istride</CODE>, and an <CODE>odist_t</CODE> of <CODE>1</CODE>. (Astute readers will
		1533	realize that some extra buffer space is required in order to perform
		1534	such a transform; this is handled automatically by rfftwnd.)
		1535
		1536
		1537	<P>
		1538	The general rule is as follows. <CODE>ostride_t</CODE> equals <CODE>istride</CODE>.
		1539	If <CODE>idist</CODE> is <CODE>1</CODE>, then <CODE>odist_t</CODE> is <CODE>1</CODE>.
		1540	Otherwise, for a real-to-complex transform <CODE>odist_t</CODE> is
		1541	<CODE>idist/2</CODE> and for a complex-to-real transform <CODE>odist_t</CODE> is
		1542	<CODE>idist*2</CODE>.
		1543
		1544
		1545
		1546
		1547	<H3><A NAME="SEC39">Destroying a Multi-dimensional Plan</A></H3>
		1548
		1549
		1550	<PRE>
		1551	#include <rfftw.h>
		1552
		1553	void rfftwnd_destroy_plan(rfftwnd_plan plan);
		1554	</PRE>
		1555
		1556	<P>
		1557	<A NAME="IDX182"></A>
		1558
		1559
		1560	<P>
		1561	The function <CODE>rfftwnd_destroy_plan</CODE> frees the plan <CODE>plan</CODE>
		1562	and releases all the memory associated with it. After destruction,
		1563	a plan is no longer valid.
		1564
		1565
		1566
		1567
		1568	<H3><A NAME="SEC40">What RFFTWND Really Computes</A></H3>
		1569	<P>
		1570	<A NAME="IDX183"></A>
		1571
		1572
		1573	<P>
		1574	The conventions that we follow for the real multi-dimensional transform
		1575	are analogous to those for the complex multi-dimensional transform. In
		1576	particular, the forward transform has a negative sign in the exponent
		1577	and neither the forward nor the backward transforms will perform any
		1578	normalization. Computing the backward transform of the forward
		1579	transform will multiply the array by the product of its dimensions (that
		1580	is, the logical dimensions of the real data). The forward transform is
		1581	real-to-complex and the backward transform is complex-to-real.
		1582
		1583
		1584	<P>
		1585	<A NAME="IDX184"></A>
		1586	<A NAME="IDX185"></A>
		1587	The Gods forbade using HTML to display mathematical formulas. Please
		1588	see the TeX or Postscript version of this manual for the proper
		1589	definition of the n-dimensional real Fourier transform that RFFTW
		1590	uses. For completeness, we include a bitmap of the TeX output below:
		1591	<P><center><IMG SRC="equation-4.gif" ALIGN="top"></center>
		1592
		1593
		1594
		1595
		1596	<H2><A NAME="SEC41">Wisdom Reference</A></H2>
		1597
		1598	<P>
		1599	<A NAME="IDX186"></A>
		1600
		1601
		1602	<H3><A NAME="SEC42">Exporting Wisdom</A></H3>
		1603
		1604
		1605	<PRE>
		1606	#include <fftw.h>
		1607
		1608	void fftw_export_wisdom(void (emitter)(char c, void ), void *data);
		1609	void fftw_export_wisdom_to_file(FILE *output_file);
		1610	char *fftw_export_wisdom_to_string(void);
		1611	</PRE>
		1612
		1613	<P>
		1614	<A NAME="IDX187"></A>
		1615	<A NAME="IDX188"></A>
		1616	<A NAME="IDX189"></A>
		1617
		1618
		1619	<P>
		1620	These functions allow you to export all currently accumulated
		1621	<CODE>wisdom</CODE> in a form from which it can be later imported and
		1622	restored, even during a separate run of the program. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.) The current store of <CODE>wisdom</CODE> is not
		1623	affected by calling any of these routines.
		1624
		1625
		1626	<P>
		1627	<CODE>fftw_export_wisdom</CODE> exports the <CODE>wisdom</CODE> to any output
		1628	medium, as specified by the callback function
		1629	<CODE>emitter</CODE>. <CODE>emitter</CODE> is a <CODE>putc</CODE>-like function that
		1630	writes the character <CODE>c</CODE> to some output; its second parameter is
		1631	the <CODE>data</CODE> pointer passed to <CODE>fftw_export_wisdom</CODE>. For
		1632	convenience, the following two "wrapper" routines are provided:
		1633
		1634
		1635	<P>
		1636	<CODE>fftw_export_wisdom_to_file</CODE> writes the <CODE>wisdom</CODE> to the
		1637	current position in <CODE>output_file</CODE>, which should be open with write
		1638	permission. Upon exit, the file remains open and is positioned at the
		1639	end of the <CODE>wisdom</CODE> data.
		1640
		1641
		1642	<P>
		1643	<CODE>fftw_export_wisdom_to_string</CODE> returns a pointer to a
		1644	<CODE>NULL</CODE>-terminated string holding the <CODE>wisdom</CODE> data. This
		1645	string is dynamically allocated, and it is the responsibility of the
		1646	caller to deallocate it with <CODE>fftw_free</CODE> when it is no longer
		1647	needed.
		1648
		1649
		1650	<P>
		1651	All of these routines export the wisdom in the same format, which we
		1652	will not document here except to say that it is LISP-like ASCII text
		1653	that is insensitive to white space.
		1654
		1655
		1656
		1657
		1658	<H3><A NAME="SEC43">Importing Wisdom</A></H3>
		1659
		1660
		1661	<PRE>
		1662	#include <fftw.h>
		1663
		1664	fftw_status fftw_import_wisdom(int (get_input)(void ), void *data);
		1665	fftw_status fftw_import_wisdom_from_file(FILE *input_file);
		1666	fftw_status fftw_import_wisdom_from_string(const char *input_string);
		1667	</PRE>
		1668
		1669	<P>
		1670	<A NAME="IDX190"></A>
		1671	<A NAME="IDX191"></A>
		1672	<A NAME="IDX192"></A>
		1673
		1674
		1675	<P>
		1676	These functions import <CODE>wisdom</CODE> into a program from data stored by
		1677	the <CODE>fftw_export_wisdom</CODE> functions above. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)
		1678	The imported <CODE>wisdom</CODE> supplements rather than replaces any
		1679	<CODE>wisdom</CODE> already accumulated by the running program (except when
		1680	there is conflicting <CODE>wisdom</CODE>, in which case the existing wisdom is
		1681	replaced).
		1682
		1683
		1684	<P>
		1685	<CODE>fftw_import_wisdom</CODE> imports <CODE>wisdom</CODE> from any input medium,
		1686	as specified by the callback function <CODE>get_input</CODE>. <CODE>get_input</CODE>
		1687	is a <CODE>getc</CODE>-like function that returns the next character in the
		1688	input; its parameter is the <CODE>data</CODE> pointer passed to
		1689	<CODE>fftw_import_wisdom</CODE>. If the end of the input data is reached
		1690	(which should never happen for valid data), it may return either
		1691	<CODE>NULL</CODE> (ASCII 0) or <CODE>EOF</CODE> (as defined in <CODE><stdio.h></CODE>).
		1692	For convenience, the following two "wrapper" routines are provided:
		1693
		1694
		1695	<P>
		1696	<CODE>fftw_import_wisdom_from_file</CODE> reads <CODE>wisdom</CODE> from the
		1697	current position in <CODE>input_file</CODE>, which should be open with read
		1698	permission. Upon exit, the file remains open and is positioned at the
		1699	end of the <CODE>wisdom</CODE> data.
		1700
		1701
		1702	<P>
		1703	<CODE>fftw_import_wisdom_from_string</CODE> reads <CODE>wisdom</CODE> from the
		1704	<CODE>NULL</CODE>-terminated string <CODE>input_string</CODE>.
		1705
		1706
		1707	<P>
		1708	The return value of these routines is <CODE>FFTW_SUCCESS</CODE> if the wisdom
		1709	was read successfully, and <CODE>FFTW_FAILURE</CODE> otherwise. Note that, in
		1710	all of these functions, any data in the input stream past the end of the
		1711	<CODE>wisdom</CODE> data is simply ignored (it is not even read if the
		1712	<CODE>wisdom</CODE> data is well-formed).
		1713
		1714
		1715
		1716
		1717	<H3><A NAME="SEC44">Forgetting Wisdom</A></H3>
		1718
		1719
		1720	<PRE>
		1721	#include <fftw.h>
		1722
		1723	void fftw_forget_wisdom(void);
		1724	</PRE>
		1725
		1726	<P>
		1727	<A NAME="IDX193"></A>
		1728
		1729
		1730	<P>
		1731	Calling <CODE>fftw_forget_wisdom</CODE> causes all accumulated <CODE>wisdom</CODE>
		1732	to be discarded and its associated memory to be freed. (New
		1733	<CODE>wisdom</CODE> can still be gathered subsequently, however.)
		1734
		1735
		1736
		1737
		1738	<H2><A NAME="SEC45">Memory Allocator Reference</A></H2>
		1739
		1740
		1741	<PRE>
		1742	#include <fftw.h>
		1743
		1744	void (fftw_malloc_hook) (size_t n);
		1745	void (fftw_free_hook) (void p);
		1746	</PRE>
		1747
		1748	<P>
		1749	<A NAME="IDX194"></A>
		1750	<A NAME="IDX195"></A>
		1751	<A NAME="IDX196"></A>
		1752	<A NAME="IDX197"></A>
		1753
		1754
		1755	<P>
		1756	Whenever it has to allocate and release memory, FFTW ordinarily calls
		1757	<CODE>malloc</CODE> and <CODE>free</CODE>.
		1758	If <CODE>malloc</CODE> fails, FFTW prints an error message and exits. This
		1759	behavior may be undesirable in some applications. Also, special
		1760	memory-handling functions may be necessary in certain
		1761	environments. Consequently, FFTW provides means by which you can install
		1762	your own memory allocator and take whatever error-correcting action you
		1763	find appropriate. The variables <CODE>fftw_malloc_hook</CODE> and
		1764	<CODE>fftw_free_hook</CODE> are pointers to functions, and they are normally
		1765	<CODE>NULL</CODE>. If you set those variables to point to other functions,
		1766	then FFTW will use your routines instead of <CODE>malloc</CODE> and
		1767	<CODE>free</CODE>. <CODE>fftw_malloc_hook</CODE> must point to a <CODE>malloc</CODE>-like
		1768	function, and <CODE>fftw_free_hook</CODE> must point to a <CODE>free</CODE>-like
		1769	function.
		1770
		1771
		1772
		1773
		1774	<H2><A NAME="SEC46">Thread safety</A></H2>
		1775
		1776	<P>
		1777	<A NAME="IDX198"></A>
		1778	<A NAME="IDX199"></A>
		1779	Users writing multi-threaded programs must concern themselves with the
		1780	<EM>thread safety</EM> of the libraries they use--that is, whether it is
		1781	safe to call routines in parallel from multiple threads. FFTW can be
		1782	used in such an environment, but some care must be taken because certain
		1783	parts of FFTW use private global variables to share data between calls.
		1784	In particular, the plan-creation functions share trigonometric tables
		1785	and accumulated <CODE>wisdom</CODE>. (Users should note that these comments
		1786	only apply to programs using shared-memory threads. Parallelism using
		1787	MPI or forked processes involves a separate address-space and global
		1788	variables for each process, and is not susceptible to problems of this
		1789	sort.)
		1790
		1791
		1792	<P>
		1793	The central restriction of FFTW is that it is not safe to create
		1794	multiple plans in parallel. You must either create all of your plans
		1795	from a single thread, or instead use a semaphore, mutex, or other
		1796	mechanism to ensure that different threads don't attempt to create plans
		1797	at the same time. The same restriction also holds for destruction of
		1798	plans and importing/forgetting <CODE>wisdom</CODE>. Once created, a plan may
		1799	safely be used in any thread.
		1800
		1801
		1802	<P>
		1803	The actual transform routines in FFTW (<CODE>fftw_one</CODE>, etcetera) are
		1804	re-entrant and thread-safe, so it is fine to call them simultaneously
		1805	from multiple threads. Another question arises, however--is it safe to
		1806	use the <EM>same plan</EM> for multiple transforms in parallel? (It would
		1807	be unsafe if, for example, the plan were modified in some way by the
		1808	transform.) We address this question by defining an additional planner
		1809	flag, <CODE>FFTW_THREADSAFE</CODE>.
		1810	<A NAME="IDX200"></A>
		1811	When included in the flags for any of the plan-creation routines,
		1812	<CODE>FFTW_THREADSAFE</CODE> guarantees that the resulting plan will be
		1813	read-only and safe to use in parallel by multiple threads.
		1814
		1815
		1816	<P><HR><P>
		1817	Go to the <A HREF="fftw_1.html">first</A>, <A HREF="fftw_2.html">previous</A>, <A HREF="fftw_4.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>.
		1818	</BODY>
		1819	</HTML>

Subversion Repositories shark

(root)/shark/branches/xen/ports/fftw/doc/fftw_3.htm - Rev 1618