508
R. Ahrens et al.
The function F is rewritten in the form
F(
φ) =
2n−1
s=0
φ s ·
d int
q=1
e
iπs q j q /n
=
2n−1
s d int =0
· · ·
2n−1
s 1 =0
φ · e
iπs 1 j 1 /n
· · · e
iπs d int j d int /n
= F
d int ◦ F
d int −1
◦ · · · ◦ F
1
(
φ),
(3.12)
reducing it to a composition of uni-variate Fourier transforms in the qth dimension,
F
q
: C
2n×···×2n
→ C
2n×···×2n
,
φ → F
q
(
φ)
with
(3.13)
(F(
φ))
q
j :=
2n−1
s=0
φ j 1 ,··· ,j m−1 ,s,j m+1 ,...,j d int · e
iπsj q /n
.
The implication is that the complete Fourier transform of
φ can be computed via
a sequence of one-dimensional Fourier transforms. Every F
q can be calculated via
multiple applications of the FFT-algorithm [20]. This reduces the complexity of each
one-dimensional Fourier transform to O(n log n) and hence reduces the complexity
of F down to O(d int n
d int log n) = O(N log N ). The same techniques are employed for
the inverse Fourier transform to calculate the complete convolution in O(N log N )
instead of O(N
2
) without using FFT.
An additional acceleration of the calculation is achieved by exploiting the zeropadding, which is necessary to obtain the full convolution result. When computing
F
1
(
φ), one needs to calculate (2n)
d int −1 fast Fourier transforms of length 2n, each
one over d int − 1 fixed indices j 2 through j d int from 0 to 2n − 1. By taking the zeropattern of
φ into account, many one-dimensional Fourier transforms are applied to
zero-vectors which can be skipped to save computational time. These superfluous
Fourier transforms are characterized by a multi-index j with at least one j q > n for
q > 1. This reduces the number of one-dimensional FFTs during the computation of
F
1 from (2n)
d int −1 to n
d int −1 , a factor of 2
d int −1 compared to the straightforward implementation. The same argument can be used to reduce the number of one-dimensional
Fourier transforms in the subsequent calculations of F
2 to F
d int −1 as part of the zeropattern is preserved. An illustration of this zero-pattern for d int = 3 is shown in
Fig. 16. The number of one-dimensional Fourier transforms for the computation of
F
q is reduced to 2
q
· n
d int −1 , reducing the total number of one-dimensional Fourier
transforms from d · (2n)
d int −1 to (2
d int − 1)n
d int −1 . The total complexity is thereby
reduced to O(N log n). Further details can be found in [1].
R. Ahrens et al.
The function F is rewritten in the form
F(
φ) =
2n−1
s=0
φ s ·
d int
q=1
e
iπs q j q /n
=
2n−1
s d int =0
· · ·
2n−1
s 1 =0
φ · e
iπs 1 j 1 /n
· · · e
iπs d int j d int /n
= F
d int ◦ F
d int −1
◦ · · · ◦ F
1
(
φ),
(3.12)
reducing it to a composition of uni-variate Fourier transforms in the qth dimension,
F
q
: C
2n×···×2n
→ C
2n×···×2n
,
φ → F
q
(
φ)
with
(3.13)
(F(
φ))
q
j :=
2n−1
s=0
φ j 1 ,··· ,j m−1 ,s,j m+1 ,...,j d int · e
iπsj q /n
.
The implication is that the complete Fourier transform of
φ can be computed via
a sequence of one-dimensional Fourier transforms. Every F
q can be calculated via
multiple applications of the FFT-algorithm [20]. This reduces the complexity of each
one-dimensional Fourier transform to O(n log n) and hence reduces the complexity
of F down to O(d int n
d int log n) = O(N log N ). The same techniques are employed for
the inverse Fourier transform to calculate the complete convolution in O(N log N )
instead of O(N
2
) without using FFT.
An additional acceleration of the calculation is achieved by exploiting the zeropadding, which is necessary to obtain the full convolution result. When computing
F
1
(
φ), one needs to calculate (2n)
d int −1 fast Fourier transforms of length 2n, each
one over d int − 1 fixed indices j 2 through j d int from 0 to 2n − 1. By taking the zeropattern of
φ into account, many one-dimensional Fourier transforms are applied to
zero-vectors which can be skipped to save computational time. These superfluous
Fourier transforms are characterized by a multi-index j with at least one j q > n for
q > 1. This reduces the number of one-dimensional FFTs during the computation of
F
1 from (2n)
d int −1 to n
d int −1 , a factor of 2
d int −1 compared to the straightforward implementation. The same argument can be used to reduce the number of one-dimensional
Fourier transforms in the subsequent calculations of F
2 to F
d int −1 as part of the zeropattern is preserved. An illustration of this zero-pattern for d int = 3 is shown in
Fig. 16. The number of one-dimensional Fourier transforms for the computation of
F
q is reduced to 2
q
· n
d int −1 , reducing the total number of one-dimensional Fourier
transforms from d · (2n)
d int −1 to (2
d int − 1)n
d int −1 . The total complexity is thereby
reduced to O(N log n). Further details can be found in [1].