HP MLIB User's Guide Vol. 2 7th Ed.

Chapter 5 Fast Fourier Transforms 553
Three-dimensional FFT S3DFFT/D3DFFT
Name S3DFFT/D3DFFT
Three-dimensional FFT
Purpose Given a set of complex data with real and imaginary parts in separate real
arrays, these subprograms compute the three-dimensional forward or inverse
DFT. Two companion subprograms, C3DFFT and Z3DFFT, perform the same
operation but with the complex data presented in a complex array.
The three-dimensional forward DFT of z(n
1
, n
2
,n
3
), for n
1
= 1, 2, ..., l
1
,
n
2
= 1, 2, ..., l
2
, and n
3
= 1, 2, ..., l
3
, is defined by
e
−2πi(m
1
−1)(n
1
−1)/l
1
e
−2πi(m
2
−1)(n
2
−1)/l
2
e
−2πi(m
3
−1)(n
3
−1)/l
3
for m
1
= 1, 2, ..., l
1
, m
2
= 1, 2, ..., l
2
, m
3
= 1, 2, ..., l
3
, and .
Alternatively, the three-dimensional inverse DFT of Z(m
1
,m
2
,m
3
), for
m
1
= 1, 2, ..., l
1
, m
2
= 1, 2, ..., l
2
, and m
3
= 1, 2, ..., l
3
, is defined by
e
+2πi(m
1
−1)(n
1
−1)/l
1
e
+2πi(m
2
−1)(n
2
−1)/l
2
e
+2πi(m
3
−1)(n
3
−1)/l
3
for n
1
= 1, 2, ..., l
1
, n
2
= 1, 2, ..., l
2
, and n
3
= 1, 2, ..., l
3
.
The complex data, z or Z, are stored with real and imaginary parts in separate
real arrays, x and y, respectively.
For best performance, these subprograms require that l
1
, l
2
, and l
3
be products
of powers of 2, 3, and 5, that is, of the form
l
k
=2
p
k
3
q
k
5
r
k
,
where p
k
, q
k
, r
k
≥ 0, k = 1, 2, 3.
Z(m
1
,m
2
,m
3
)
n
1
1=
l
1
∑
n
2
1=
l
2
∑
n
3
1=
l
3
∑
z(n
1
,n
2
,n
3
) ×=
i 1–=
z(n
1
,n
2
,n
3
)
1
l
1
l
2
l
3
--------------
m
1
1=
l
1
∑
m
2
1=
l
2
∑
m
3
1=
l
3
∑
Z(m
1
,m
2
,m
3
) ×=