Printer Friendly
The Free Library
22,719,120 articles and books

Time and memory requirements of the nonequispaced FFT.


We consider the fast Fourier transform See FFT.

(algorithm) Fast Fourier Transform - (FFT) An algorithm for computing the Fourier transform of a set of discrete data values. Given a finite set of data points, for example a periodic sampling taken from a real-world signal, the FFT expresses the data in terms of
 at nonequispaced nodes (NFFT NFFT Norsk Forening for Familieterapi
NFFT Nonequispaced Fast Fourier Transform
NFFT non-uniform fast Fourier transform
NFFT Nonequidistant Fast Fourier Transform
NFFT Non-Face-to-Face Transaction
NFFT National Flag Football Tournament
), and give detailed information on the time and memory requirements of its building blocks. This manuscript reviews the state of the art approaches and focuses within the most successful scheme on the most computationally involved part. Beside a rigorous derivation derivation, in grammar: see inflection.  of a lookup table An array or matrix of data that contains items that are searched. Lookup tables may be arranged as key-value pairs, where the keys are the data items being searched (looked up) and the values are either the actual data or pointers to where the data are located.  technique, we compare a wide range of precomputation schemes which lead to substantially different computation times In computational complexity theory, computation time is a measure of how many steps are used by some abstract machine in a particular computation. For any given model of abstract machine, the computation time used by that abstract machine is a computational resource which can be  of the NFFT. In particular, we show how to balance accuracy, memory usage, and computation time.

Key words and phrases Words and Phrases®

A multivolume set of law books published by West Group containing thousands of judicial definitions of words and phrases, arranged alphabetically, from 1658 to the present.
. Nonequispaced Fast Fourier Transform, FFT (Fast Fourier Transform) A class of algorithms used in digital signal processing that break down complex signals into elementary components.

FFT - Fast Fourier Transform

1 Introduction

This paper summarises algorithms for the discrete and fast Fourier transform at nonequispaced nodes. Generalising the famous fast Fourier transform (FFT), we evaluate for N [member of] 2N, M [member of] N, a vector of coefficients f = [([[??].sub.k]).sub.k = -N/2, ..., N/2 - 1] [member of] [C.sup.N], and a set of nodes [x.sub.j] [member of] R the sums

[MATHEMATICAL EXPRESSION A group of characters or symbols representing a quantity or an operation. See arithmetic expression.  NOT REPRODUCIBLE IN ASCII ASCII or American Standard Code for Information Interchange, a set of codes used to represent letters, numbers, a few symbols, and control characters. Originally designed for teletype operations, it has found wide application in computers. ].

In the multivariate The use of multiple variables in a forecasting model.  setting the discrete Fourier transform (mathematics) discrete Fourier transform - (DFT) A Fourier transform, specialized to the case where the abscissas are integers.

The DFT is central to many kinds of signal processing, including the analysis and compression of video and sound information.
 at nonequispaced nodes (NDFT) requires O([N.sub.[pi]]M) operations for [N.sub.[pi]] equispaced frequencies and M nonequispaced sampling nodes [x.sub.j] [member of] [R.sup.d]. In contrast, the approximate NFFT takes only O([N.sub.[pi]] log [N.sub.[pi]]+M) floating point operations (flops), where the constant of proportionality Noun 1. constant of proportionality - the constant value of the ratio of two proportional quantities x and y; usually written y = kx, where k is the factor of proportionality
factor of proportionality
 depends in theory solely on the prescribed target accuracy and on the space dimension d.

There is a variety of important applications which utilise the NDFT, e.g., in computerised tomography [18, 32, 34, 29, 28], for fast summation summation n. the final argument of an attorney at the close of a trial in which he/she attempts to convince the judge and/or jury of the virtues of the client's case. (See: closing argument)  algorithms [35, 36, 23], for moving least squares Moving least squares is a method of reconstructing continuous functions from a set of unorganized point samples via the calculation of a weighted least squares measure biased towards the region around the point at which the reconstructed value is requested.  approximation [12], as fast Fourier transform on the sphere [25], or as part of the ridgelet and curvelet transforms [27, 6]. Furthermore, the reconstruction from nonuniform samples is stated in [20, 13, 1, 26] as inversion of the NDFT and used, for example, in magnetic resonance imaging magnetic resonance imaging (MRI), noninvasive diagnostic technique that uses nuclear magnetic resonance to produce cross-sectional images of organs and other internal body structures.  [15, 39, 10] or as polar FFT [2, 14]. In each of these applications the actual computation of the NDFT is the computationally dominant task and one has to deal with different requirements on the NFFT with respect to the target accuracy, the usage of memory, and the actual computation time. An early review of several algorithms for the NFFT is given in [41]. Only later, a unified approach to fast algorithms for the present task was obtained in [38, 37] and recently a particular property of the Gaussian window function was utilised in [19] to speed up computations when no precomputation is possible.

Despite the fact that there exist a few tutorial papers for the NFFT (see also [21]), the aim of this manuscript is to give detailed information on the accuracy, memory, and time requirements of NFFT algorithms and to describe how to balance these factors. In particular, the O(M)-step of the NFFT hides a significant constant and we focus on a variety of precomputation schemes which lead to substantially different computation times of the whole NFFT.

The outline of the paper is as follows. In Section 2 minor improvements in the direct calculation of the NDFT are discussed; cf. [3]. Furthermore the unified approach to the NFFT is reviewed and alternative NFFTs are discussed. In Section 3 we compare different methods for the fast evaluation and precomputation of the window functions utilised in the most popular NFFT-approach. Finally, we compare the different NFFTs numerically in Section 4 and draw conclusions. All used algorithms are available in our widely used software [24].

2 Notation, the NDFT and the NFFT

This section summarises the mathematical theory and ideas behind the NFFT. For d, M [member of] N let the torus torus /to·rus/ (tor´us) pl. to´ri   [L.] a swelling or bulging projection.

n. pl.
 [T.sup.d] := [R.sup.d]/[Z.sup.d] ~ [[-1/2, 1/2).sup.d] and the sampling set x := {[x.sub.j] [member of] [T.sup.d] : j = 0, ..., M - 1} be given. Furthermore, let the multi degree N = [([N.sub.0], [N.sub.1], ..., [N.sub.d - 1]}).sup.T] [member of] 2[N.sup.d] and the index set for possible frequencies [I.sub.N] := {-[N.sub.0]/2, [N.sub.0]/2 - 1} x ... x {-[N.sub.d-1]/2, [N.sub.d-1]/2 - 1} be given. We define the space of d-variate trigonometric polynomials In the mathematical subfields of numerical analysis and mathematical analysis, a trigonometric polynomial is a finite linear combination of sin(nx) and cos(nx) with n a natural number.  [T.sub.N] of multi degree N by

[T.sub.N] := span {[e.sup.-2[pi]ikx] : k [member of] [I.sub.N]}

The dimension of this space and hence the total number of Fourier coefficients is [N.sub.[pi]] = [N.sub.0] ... [N.sub.d-1]. Note, that we abbreviate the inner product between the frequency k and the time/spatial node x by kx = [k.sup.T] x = [k.sub.0][x.sub.0] + [k.sub.1][x.sub.1] + ... + [k.sub.d-1][x.sub.d-1]. For clarity of presentation the multi index k addresses elements of vectors and matrices as well.

2.1 NDFT

For a finite number of given Fourier coefficients [[??].sub.k] [member of] C, k [member of [I.sub.N], one wants to evaluate the trigonometric polynomial

f(x) := [summation over [k [member of] [I.sub.N]] [[??].sub.k][e.sup.-2[pi]ikx] (2.1)

at given nonequispaced nodes [x.sub.j] [member of] [T.sup.d], j = 0, ..., M - 1. Thus, our concern is the computation of the matrix vector product

f = A [??] (2.2)



The straight forward algorithm for this matrix vector product, which is called NDFT in Algorithm 1, takes O(M [N.sub.[pi]]) arithmetical operations and stores no matrix elements at all, but rather uses M [N.sub.[pi]] direct calls of the function cexp() to evaluate the complex exponentials [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
Algorithm 1: NDFT

Input: d, M [member of] N, N [member of] 2[N.sup.d],
       [x.sub.j] [member of] [[-1/2, 1/2].sup.d], j = 0, ..., M - 1,
        and [[??].sub.k] [member of] C, k [member of] [I.sub.N].

  for j = 0 ..., M - 1 do
    [f.sub.j] = 0
    for k [member of] [I.sub.N] do
    end for
  end for

Output: values [f.sub.j] = f([x.sub.j]), j = 0, ..., M - 1.

Related matrix vector products axe the adjoint Ad´joint

n. 1. An adjunct; a helper.


where the update step in Algorithm 1 is simply changed to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the conjugated conjugated

estrogens, conjugated Warning - Hazardous drug!

 NDFT f = [bar.A][??], and the transposed trans·pose  
v. trans·posed, trans·pos·ing, trans·pos·es
1. To reverse or transfer the order or place of; interchange.

 NDFT [??] = [A.sup.T]f where [A.sup.H] = [[bar.A].sup.T]. Note, furthermore, that the inversion formula [F.sup.-1] = [F.sup.H] for the (equispaced and normalised normalised - normalisation ) Fourier matrix F does not hold in the general situation of arbitrary sampling nodes for the matrix A.

NDFT acceleration

Algorithm 1 evaluates M [N.sub.[pi]] complex exponentials. Due to the fact that these direct calls are more expensive than multiplications, we may basically change the update step to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], i.e., do a Hornet-like-scheme; see also [3]. Hence, in general 2dM direct calls are sufficient for the computations in Algorithm 1. Note, however, that this approach looses numerical stability In the mathematical subfield of numerical analysis, numerical stability is a desirable property of numerical algorithms. The precise definition of stability depends on the context, but it is related to the accuracy of the algorithm.  to some extend; cf. [40]. Trading even more memory for the acceleration of the computation, one might precompute all entries of the matrix A, which is only feasible for small [N.sub.[pi]] and M; see Example 4.1 in Section 4.

2.2 NFFT

The most successful approach for the fast computation of (2.2) [8, 5, 38, 37, 16, 15, 19] is based on the usage of an oversampled FFT and a window function which is simultaneously localised localised - localisation  in time/space and frequency. Basically, the scheme utilises the convolution theorem In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution is the point-wise product of Fourier transforms. In other words, convolution in one domain (e.g.  in the following three informal steps:

1. deconvolve the trigonometric polynomial f in (2.1) with the window function in frequency domain,

2. compute an oversampled FFT on the result of step 1., and

3. convolve con·volve  
v. con·volved, con·volv·ing, con·volves
To roll together; coil up.

To form convolutions.
 the result of step 2. with the window function in time/spatial domain; evaluate this convolution convolution /con·vo·lu·tion/ (-loo´shun) a tortuous irregularity or elevation caused by the infolding of a structure upon itself.  at the nodes [x.sub.j].

Throughout the rest of the paper [sigma] > 1 and n = [sigma]N [member of] N will denote the oversampling Creating a more accurate digital representation of an analog signal. In order to work with real-world signals in the computer, analog signals are sampled some number of times per second (frequency) and converted into digital code.  factor and the FFT size, respectively. Furthermore, for d > 1 let [sigma] [member of] [R.sup.d], [[sigma].sub.0], ..., [[sigma].sub.d-1] > 1, n = [sigma] [dot encircle en·cir·cle  
tr.v. en·cir·cled, en·cir·cling, en·cir·cles
1. To form a circle around; surround. See Synonyms at surround.

2. To move or go around completely; make a circuit of.
], and [n.sub.[pi]] = [n.sub.0] .... [n.sub.d-1] denote the oversampling factor, the FFT size, and the total FFT size, respectively. Here, we use for notational convenience the pointwise product The pointwise product of two functions is another function, obtained by multiplying the image of the two functions at each value in the domain. If f and g are both functions with domain X and codomain Y, and elements of Y  [sigma] [dot encircle] [N := [([[sigma].sub.0][N.sub.0], [[sigma].sub.1][N.sub.1], ..., [[sigma].sub.d-1] [N.sub.d-1],).sup.t] with its inverse [N.sup.-1] := [(1/[N.sub.0], 1/[N.sub.1], ..., 1/[N.sub.d-1]).sup.T].

The window function

Starting with a window function [phi] [member of] [L.sub.2](R), which is well localised in the time/spatial domain R and in the frequency domain R, respectively, one assumes that its 1-periodic version [??], i.e.,

[??](x) := [summation over (r[member of]Z)][phi](x + r),

has an uniformly convergent Fourier series Fourier series

In mathematics, an infinite series used to solve special types of differential equations. It consists of an infinite sum of sines and cosines, and because it is periodic (i.e.
, and is well localised in the time/spatial domain T and in the frequency domain Z, respectively. Thus, the periodic window function [??} may be represented by its Fourier series

[??](x) [summation over (k[member of]Z)] [??](k) [e.sup.-2[pi]ikx]

with the Fourier coefficients


We truncate To cut off leading or trailing digits or characters from an item of data without regard to the accuracy of the remaining characters. Truncation occurs when data are converted into a new record with smaller field lengths than the original.  this series at the FFT length n which causes an aliasing In computer graphics, the stair-stepped appearance of diagonal lines when there are not enough pixels in the image or on screen to represent them realistically. Also called "stair-stepping" and "jaggies." See anti-aliasing.  error. If [phi] is furthermore well localised in time/spatial domain R, it can be truncated truncated adjective Shortened  with truncation parameter m [member of] N, m [much less than] n, and approximated by the function [phi] x X[-m/n, m/n] which has compact support within the interval [-m/n, m/n]. Moreover, the periodic window function can be approximated by the periodic version of the truncated window function. For d > 1, univaxiate window functions [[phi].sub.0], ..., [[phi].sub.d-1], and a node x = [([x.sub.0], ..., [x.sub.d-1]).sup.T] the multivariate window function is simply given by

[phi](x) := [[phi].sub.0]([x.sub.0])[[phi].sub.1]([x.sub.1]) ... [[phi].sub.d-1] ([x.sub.d-1]), (2.3)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] again denotes the 1-periodic version; an immediate observation is


For a single truncation parameter m [member of] N the window function is truncated to the cube [n.sup.-1] [dot encircle][[-m, m].sup.d].


We follow the general approach of [38, 37] and approximate the complex exponentials in the trigonometric polynomial (2.1) by


where the set

[I.sub.n,m](x) := {l [member of] [I.sub.n] : n [dot encircle] x - m1 [less than or equal to] l [less than or equal to] n [dot encircle] x + m1}

collects these indices where the window function is mostly concentrated (the inequalities have to be fulfilled modulo A mathematical operation (modulus arithmetic) in which the result is the remainder of a division. Also known as the "remainder operator," it is used to solve a variety of problems. For example, the following code in the C language determines if a number is odd or even.  n and for each component). After changing the order of summation in (2.1) we obtain for [x.sub.j] [member of] [T.sup.d], j = 0,..., M - 1, the approximation


This causes a truncation and an aliasing error; see [37, 33] for details. As can be readily seen, after an initial deconvolution In mathematics, deconvolution is an algorithm-based process used to reverse the effects of convolution on recorded data.[1] The concept of deconvolution is widely used in the techniques of signal processing and image processing.  step the expression in brackets can be computed via a d-variate FFT of total size [n.sub.[pi]]. The final step consists of the evaluation of sums having at most [(2m + 1).sup.d] summands where the window function is sampled only in the neighbourhood of the node [x.sub.j].

The algorithm and its matrix notation

The proposed scheme reads in matrix vector notation For information on vectors as a mathematical object see vector (spatial). This page is about notation of vectors. Declaration
A vector can be declared in three ways:
  • Parentheses can enclose an ordered set of coordinates:

A [??] [approximately equal to] B F D [??], (2.5)

where B denotes the real M x [n.sub.[pi]] sparse matrix In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros.

Conceptually, sparsity corresponds to systems which are loosely coupled.


where F is the d-variate Fourier matrix of size [n.sub.[pi]] x [n.sub.[pi]], and where D is the real [n.sub.[pi]] x [N.sub.[[pi] diagonal matrix Noun 1. diagonal matrix - a square matrix with all elements not on the main diagonal equal to zero
square matrix - a matrix with the same number of rows and columns

scalar matrix - a diagonal matrix in which all of the diagonal elements are equal


with zero matrices [O.sub.t] of size [N.sub.t] x [n.sub.t] - [N.sub.t]/2. Obviously, the approximate matrix splitting can by applied to the adjoint matrix as [A.sup.H] [approximately equal to] [D.sup.T][F.sup,H][B.sup.T], where the multiplication multiplication, fundamental operation in arithmetic and algebra. Multiplication by a whole number can be interpreted as successive addition. For example, a number N multiplied by 3 is N + N + N.  with the sparse matrix [B.sup.T] is implemented in a transposed way, summation as outer loop and only using the index sets [I.sub.n,m] ([x.sub.j]).

Table 2.2 shows the computational requirements for the deeonvolution step of the NFFT. We give detailed information on the number of precomputed and stored real numbers (memory), the order of magnitude A change in quantity or volume as measured by the decimal point. For example, from tens to hundreds is one order of magnitude. Tens to thousands is two orders of magnitude; tens to millions is three orders of magnitude, etc.  for the number of floating point operations (flops), and the number of evaluations for the univariate Fourier-transformed window function [??]. Precomputing the factors [[??].sub.t]([k.sub.t]) for t = 0, ..., d - 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is denoted by its associated Flag PRE_PHI_HUT within the software library.

This is followed by one FFT of total size [n.sub.[pi]]. Hence, the computational complexity computational complexity

Inherent cost of solving a problem in large-scale scientific computation, measured by the number of operations required as well as the amount of memory used and the order in which it is used.
 of the NFFT increases for a larger oversampling factor [sigma], affecting both the deconvolution step and the FFT. The time and memory requirements of the convolution and evaluation step are discussed in Section 3 in detail. In summary, we propose Algorithm 2 and Algorithm 3 for the computation of the nonequispaced FFT (2.2) and its adjoint, respectively.

Alternative NFFTs

Taylor based NFFT: A simple but nevertheless fast scheme for the computation of (2.2) in the univariate case d = 1 is presented in [1]. This approach uses for each node [x.sub.j] [member of] [-1/2, 1/2) an m-th order Taylor expansion of the trigonometric polynomial in (2.1) about the nearest neighbouring point on the oversampled equispaced lattice [{[n.sup.-1]k - 1/2}.sub.k=0], ..., n-1] where again n = [sigma]N, a [much greater than] 1. Besides its simple structure and only O(N log N + M) arithmetic operations, this algorithm utilises m FFTs of size n compared to only one in the NFFT approach, uses a medium amount of extra memory, and is not suited for highly accurate computations; see Example 4.2. Furthermore, its extension to higher dimensions Higher dimension as a term in mathematics most commonly refers to any number of spatial dimensions greater than three.

The three standard dimensions are length, width, and breadth (or height).
 has not been considered so far.
Algorithm 2: NFFT

Input: d, M [member of] N, N [member of] 2[N.sup.d],
       [x.sub.j] [member of] [[-1/2, 1/2].sup.d], j = 0, ..., M - 1,
       and [[??].sub.k] [member of] C, k [member of] [I.sub.N].

  For k [member of] [I.sub.N] compute


  For l [member of] [I.sub.n] compute by d-variate FFT


  For j = 0, ..., M - 1 compute

  [s.sub.j] := [summation over (l[member of][I.sub.n,m]([x.sub.j])]
  [g.sub.l] [??] ([x.sub.j] - [n.sup.-1] [dot encircle] l).

Output: approximate values [s.sub.j] [approximately equal to]
[f.sub.j], j = 0, ..., M - 1.

Algorithm 3: [NFFT.sup.H]

Input: d, M [member of] N, N [member of] 2[N.sup.d],
       [x.sub.j] [member of] [[-1/2, 1/2].sup.d] and [f.sub.j]
       [member of] C, j = 0, ..., M - 1.

  Compute tile sparse matrix vector product

  g := [B.sup.T] f.

  Apply the d-variate IFFT as

  [??] := [F.sup.H]g.

  Multiply by the 'diagonal' matrix, i.e.,

  [??] := [D.sup.T] [??].

Output: approximate values [[??].sub.k], k [member of] [I.sub.N].

Multipole based NFFT: A second approach for the univariate case d = 1 is considered in [9] and based on a Lagrange interpolation interpolation

In mathematics, estimation of a value between two known data points. A simple example is calculating the mean (see mean, median, and mode) of two population counts made 10 years apart to estimate the population in the fifth year.
 technique. After taking a N-point FFT of the vector [??] in (2.2), one uses an exact polynomial interpolation In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. In other words, given some data points (such as obtained by sampling), the aim is to find a polynomial which goes exactly through these points.  scheme to obtain the values of the trigonometric polynomial f at the nonequispaced nodes [x.sub.j]. Here, the time consuming part is the exact polynomial interpolation scheme which can be realised fast in an approximate way by means of the fast multipole method The Fast Multipole Method (FMM) is a mathematical technique that was developed to speed up the calculation of the N-Body Problem. It does this by expanding the system Green's Function using a Multipole Expansion, which allows one to group sources that lie close together and treat . This approach is appealing since it also allows for the inverse transform. Nevertheless, numerical experiments in [9] showed that this approach is far more time consuming than Algorithm 2 and the inversion can only be computed in a stable way for almost equispaced nodes [9].

Linear algebra linear algebra

Branch of algebra concerned with methods of solving systems of linear equations; more generally, the mathematics of linear transformations and vector spaces.
 based NFFT: Using a fully discrete approach, one might fix the entries of the diagonal matrix D in (2.5) first and precompute optimised entries for the sparse matrix B to achieve higher accuracy [30, 31]. A similar approach, based on min-max interpolation, has been taken within [15]. While these approaches gain some accuracy for the Gaussian or B-Spline windows, no reasonable improvement is obtained for the Kaiser-Bessel window function. Since it is more expensive to precompute these optimised entries of the matrix B, we do not further consider these schemes.

3 Evaluation techniques for window functions

To keep the aliasing error and the truncation error Noun 1. truncation error - (mathematics) a miscalculation that results from cutting off a numerical calculation before it is finished
miscalculation, misestimation, misreckoning - a mistake in calculating
 small, several univariate functions T with good localisation (programming) localisation - (l10n) Adapting a product to meet the language, cultural and other requirements of a specific target market "locale".

Localisation includes the translation of the user interface, on-line help and documentation, and ensuring the images and
 in time and frequency domain were proposed. For an oversampling factor [sigma] > 1, a degree N [member of] 2N, the FFT length n = [sigma]N, and a cut-off cut-off Anesthesiology The point at which elongation of the carbon chain of the 1-alkanol family of anesthetics results in a precipitous drop in the anesthetic potential of these agents–eg, at > 12 carbons in length, there is little anesthetic activity,  parameter m [member of] N, the following window functions are considered:

1. for a shape parameter In probability theory and statistics, a shape parameter is a special kind of numerical parameter of a parametric family of probability distributions. Definition

Please help [ improve this article] by expanding this section.
See talk page for details.
 b = 2[sigma]/2[sigma]-1 m/[pi] the dilated dilated

a state of dilatation.

dilated cardiomyopathy
see congestive cardiomyopathy.

dilated pupil syndrome
see feline dysautonomia (Key-Gaskell syndrome).
 Gaussian window [8, 38, 7]


2. for [M.sub.2m] denoting the centred cardinal B-Spline of order 2m the dilated B-Spline window [5, 38]

[phi](x) = [M.sub.2m](nx), (3.2)

3. the dilated Sinc window [33]

[phi](x) = [[sinc].sup.2m]((2[sigma] - 1) N/2m [pi]x) (3.3)

with sinc(x) := sin(x) / x for x [not equal to] 0 and sinc(0) := 1

4. and for a shape parameter b = [pi](2 - 1/[sigma]) the dilated Kaiser-Bessel window [35]


Note, that the latter two have compact support in frequency domain while the second one has compact support in time domain. Further references on the usage of (generalised Adj. 1. generalised - not biologically differentiated or adapted to a specific function or environment; "the hedgehog is a primitive and generalized mammal"

biological science, biology - the science that studies living organisms
) Kaiser-Bessel window functions include [22, 16, 28], where some authors prefer to interchange the role of time and frequency domain. For these univariate window functions [phi], the error introduced by Algorithm 2 obeys

[absolute value of f([x.sub.j]) - [s.sub.j]] [less than or equal to] [C.sub.[sigma],m][[parallel][??][parallel].sub.1] (3.5)



Thus, for fixed [sigma] > 1, the approximation error In the mathematical field of numerical analysis, the approximation error in some data is the discrepancy between an exact value and some approximation to it. An approximation error can occur because
  1. the measurement of the data is not precise (due to the instruments), or
 introduced by the NFFT decays exponentially with the number m of summands in (2.4). Using the tensor product (mathematics) tensor product - A function of two vector spaces, U and V, which returns the space of linear maps from V's dual to U.

Tensor product has natural symmetry in interchange of U and V and it produces an associative "multiplication" on vector spaces.
 approach, the above error estimates have been generatised for the multivariate setting in [11, 7]. Note furthermore, that it is convenient to replace the periodic window function [??] again by the original one [phi] within the actual computation. This causes an error for functions with large support in time/spatial domain. However, whenever the FFT-length n is reasonable "large, e.g., n [greater than or equal to] max{4m, 12} for the Gaussian, an easy calculation shows that for x [member of] [-m/n, m/n] the estimate


holds true, i.e., the resulting error is within machine precision. If the restriction on n is not fulfilled, the NDFT method is competitive, anyway.

In the following, we suggest different methods for the compressed storage and application of the matrix B which are all available within our NFFT library by choosing particular flags in a simple way during the initialisation Noun 1. initialisation - (computer science) the format of sectors on the surface of a hard disk drive so that the operating system can access them and setting a starting position
initialization, low-level formatting
 phase. These methods do not yield a different asymptotic performance but rather yield a lower constant in the amount of computation.

3.1 Fully precomputed window function

One possibility is to precompute all values [phi]([x.sub.j]-[n.sup.-1][dot encircle]l) for j = 0, ..., M-1 and l [member of] [I.sub.n,m]([x.sub.j]) explicitly. Thus, one has to store the large amount of [(2m + 1).sup.d]M real numbers but uses no extra floating point operations during the matrix vector multiplication, beside the necessary [(2m-b 1).sup.d]M flops. Furthermore, we store for this method explicitly the row and column for each nonzero non·ze·ro  
Not equal to zero.


Not equal to zero.
 entry of the matrix B. This method, included by the flag PRE_FULL_PSI, is the fastest procedure but can only be used if enough main memory is available.

3.2 Tensor product based precomputation

Using the fact that the window functions are built as tensor products, one can store [[phi].sub.t](([x.sub.j]).sub.t] - [l.sub.t]/[n.sub.t]) for j = 0, ..., M - 1, t = 0, ..., d - 1, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [([x.sub.j]).sub.t] denotes the t-th component of the j-th node. This method uses a medium amount of memory to store d(2m+1)M real numbers in total. However, one must carry out for each node at most 2[(2m + 1).sup.d] extra multiplications to compute from the factors the multivariate window function [phi]([x.sub.j] - [n.sup.-1] [dot encircle] l) for l [member of] [I.sub.n,m]([x.sub.j]). Note that this technique is available for every window function discussed here and can be used by means of the flag PRE_PSI, which is also the default method within our software library.

3.3 Linear interpolation Linear interpolation is a method of curve fitting using linear polynomials. It is heavily employed in mathematics (particularly numerical analysis), and numerous applications including computer graphics. It is a simple form of interpolation.  from a lookup table

For a large number of nodes, M, the amount of memory can be further reduced by the use of lookup table techniques. For a recent example within the framework of gridding, see [4]. We suggest that one precomputes from the even window function the equidistant e·qui·dis·tant  
Equally distant.

equi·distance n.
 samples [phi].sub.t]([rm/K[n.sub.t]) for t = 0, ..., d - 1 and r = 0,..., K, K [member of] N, and then compute for the actual node [x.sub.j] during the NFFT the values [[phi].sub.t][(([x.sub.j]).sub.t] - [l.sub.t]/[n.sub.t]) for t = 0, ..., d - 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by means of the linear interpolation from its two neighbouring precomputed samples.

Lemma lemma (lĕm`ə): see theorem.

(logic) lemma - A result already proved, which is needed in the proof of some further result.
 3.1 For the univariate window functions (3.1) - (3.4) and K [member of] N the linear interpolated interpolated /in·ter·po·lat·ed/ (in-ter´po-la?ted) inserted between other elements or parts.  window function, denoted by [[phi].sub.K], fulfils


Proof: From standard error estimates we know that the linear interpolated window function [[phi].sub.K] fulfils


The maximum of this second derivative is met for the window functions (3.1)-(3.4) at [xi] = 0. Thus, the assertion follows by


and the estimates [M.sub.2m-2] (0) - [M.sub.2m-2] (1) [less than or equal to] 1 and bm cosh(bm) - sinh sinh
hyperbolic sine


Abbreviation of hyperbolic sine
(bm) [less than or equal to] 2[pi]m [e.sup.2[pi]m].

This method needs only a storage of dK real numbers in total where K depends solely on the target accuracy, but neither on the number of nodes M nor on the multi degree N. Choosing K to be a multiple of m, we further reduce the computational costs during the interpolation since the distance from ([x.sub.j]).sub.t] - [l.sub.t]/[n.sub.t] to the two neighbouring interpolation nodes and, hence, the interpolation weights remain the same for all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This method requires 2[(2m+ 1).sup.d] extra multiplications per node and is used within the NFFT by the flag PRE_LIN_PSI.

3.4 Fast Gaussian gridding

Two useful properties of the Gaussian window function (3.1) within the present framework were recently reviewed in [19]. Beside its tensor product structure for d > 1, which also holds for all other window functions, it is remarkable that the number of evaluations of the form exp exp
1. exponent

2. exponential
() can be greatly decreased. More precisely, for d = 1 and a fixed node [x.sub.j] the evaluations of [phi]([x.sub.j]- l'/n), l' [member of] [I.sub.n,m]([x.sub.j]), can be reduced by the splitting


where u = min [I.sub.n,m]([x.sub.j]) and l = 0, ..., 2m. Note that the first factor and the exponential within the brackets are constant for each fixed node [x.sub.j]. Once we evaluate the second exponential, its l-th power can be computed consecutively by multiplications only. Furthermore, the last exponential is independent of [x.sub.j] and these 2m + 1 values are computed only once within the NFFT and their amount is negligible. Thus, it is sufficient to store or evaluate 2M exponentials for d = 1. The case d > 1 uses 2dM storages or evaluations by using the general tensor product structure. This method is employed by the flags FG_PSI and PRE_FG_PSI for the evaluation or storage of two exponentials per node, respectively.

3.5 No precomputation of the window function

The last considered method uses no precomputation at all, but rather evaluates the univariate window function [(2m + 1).sup.d]M times. Thus, the computational time depends on how fast we can evaluate the particular window function. However, no additional storage is necessary, which suits this approach whenever the problem size reaches the memory limits of the used computer.

3.6 Summary on the computational costs

The multiplication with the sparse matrix B clearly takes O([m.sup.d]M) operations. Beside this, Table 3.1 summarises the memory requirements for different strategies to store the elements of this matrix and the extra costs it takes to multiply with this compressed matrix.

4 Numerical experiments

We present numerical experiments in order to demonstrate the performance of our algorithms. All algorithms were implemented in C and tested on an AMD (Advanced Micro Devices, Inc., Sunnyvale, CA, A major manufacturer of semiconductor devices including x86-compatible CPUs, embedded processors, flash memories, programmable logic devices and networking chips.  Athlon[TM] XP 2700+ with 2GB main memory, SuSe-Linux (kernel 2.4.20-4GBathlon, gcc 3.3) using double precision arithmetic. Moreover, we have used the libraries FFTW FFTW Fastest Fourier Transform in the West (C subroutine library)
FFTW Fast Fourier Transform in the West
 3.0.1 [17] and an extended version of NFFT 2.0.3 [24]. In order to reproduce all of the numerical results, a pre-release of the upcoming NFFT library can be downloaded from our web page [24].

Example 4.1 We start by examining accelerated NDFTs for d = 1. Using the three proposed possibilities to compute the matrix vector product by either M N direct calls of cexp(), a Homer-like scheme, or a fully precomputed matrix A, we obtain the following timings for increasing N in Figure 4.1 (top-left). Clearly, the complete precomputation of the matrix A does not pay off. The Horner-like NDFT uses no extra memory and is considerably faster than the NDFT. Furthermore, it is faster than the default NFFT until an break even of N = 128. []

Example 4.2 Our second example concerns the Taylor expansion based NFFT, again only for d = 1. We note that this scheme actually provides a competitive NFFT with respect to the computation time relative to the problem size, at least within a factor; cf. Figure 4.1 (top-right). The main drawbacks of this approach are its instability, i.e., it is not possible to obtain high accurate results by increasing the order m of the Taylor expansion and, hence, the number of used FFTs. This fact remains even true for a very large oversampling factor [sigma] = 16; see Figure 4.1 (bottom-left). Furthermore, even when the target accuracy [E.sub.[infinity]] = [[parallel]f - s[parallel].sub.[infinity]] / [[parallel]f[parallel].sub.[infinity]], cf. [1], is somewhat larger, the NFFT needs considerably fewer arithmetic operations to reach it, cf. 4.1 (bottom-right). []

Example 4.3 We now compare the computation time for the three tasks within the NFFT, i.e., the deconvolution step, the oversampled FFT, and the convolution/evaluation step for space dimension d = 1. Figure 4.2 shows the timings for increasing degree N, M = N nodes, and a fixed cut-off m = 4. The linear dependence of the computation time with respect to the problem size can be seen for the matrix-vector multiplication with the diagonal matrix D and the sparse matrix B whereas the FFT takes O(N log N) operations.

For the deconvolution step we obtain a speed up of more than 3 by avoiding direct calls of the Fourier-transformed window function [??]; this method is default and turned on by the precomputation flag PRE_PHI_HUT; cf. Figure 4.2 (top-left).


Ways to speed up the FFT by a more exhaustive search of an optimal FFT-plan are discussed in [17]. Figure 4.2 (top-right) shows for larger degree N a speed up of around 2 when we use the planner FFTW_MEASURE, which is also default within the NFFT.

The time to compute the last step of the NFFT differs from no precomputation of the matrix entries of B to explicitly precomputed entries with PRE_FULL_PSI by a factor of 20 to 100 for small degrees IV [less than or equal to] 2048 and by a factor of 5 to 20 for larger degrees. Note, however, that the use of this flag with maximal max·i·mal
1. Of, relating to, or consisting of a maximum.

2. Being the greatest or highest possible.
 precomputation is limited by the available memory, e.g., for m = 4, and M = [2.sup.20] we already need 144 MByte just for storing the matrix entries and its indices. []

Example 4.4 Furthermore, we show the timings of the convolution/evaluation step for increasing N, the multi degree N = [(N, ..., N).sup.T], M = [N.sup.d] nodes, a fixed cut-off m = 4, and space dimension d = 2, 3 in Figure 4.3. Note, that for d = 2 and m = 4 the matrix B has already 81 nonzero entries per row. []

Example 4.5 More detailed, we focus on the convolution/evaluation step for space dimension d = 1. Figure 4.4 shows the computation time with respect to achieved target accuracy [E.sub.2] = [[parallel]f - s[parallel].sub.2] / [[parallel]f[parallel].sub.2] cf. [37], by increasing the cut-off m for fixed degree and number of nodes.

We conclude that if no additional memory is used for precomputing the entries of the matrix B, the Gaussian window function in conjunction with the flag FG_PSI performs best; cf. Figure 4.4 (top-left). If no precomputation is used, the particular bad behaviour of the B-Spline window function is due to the fact that evaluating this window function once already takes O(m) operations.

When only a small amount of memory is used for precomputations, the decision between the linear interpolated Kaiser-Bessel window function and the fast Ganssian gridding with precomputation PKE PKE - public-key encryption _FG_PSI depends on the accuracy one would like to achieve; here, the linear interpolated Kalser-Bessel window performs better up to single precision (top-right).

Whenever at least 2mM values can be precomputed, the Kaiser-Bessel window performs always best, i.e., it needs the least amount of time to achieve a given target accuracy; cf. Figure 4.4 (bottom). []




Example 4.6 Finally, Figure 4.5 shows the quadratic quadratic, mathematical expression of the second degree in one or more unknowns (see polynomial). The general quadratic in one unknown has the form ax2+bx+c, where a, b, and c are constants and x is the variable.  decay of the error introduced by the linear interpolation of the window function if the method PRE_LIN_PSI is used. The decay of the error [E.sub.2] coincides for all window functions up to the accuracy; they actually can provide for a fixed cut-off m = 10. []


5 Conclusions

Fast algorithms for the nonequispaced discrete Fourier transform have already been known a couple of years. Besides their asymptotic computational complexity of O([N.sub.[pi] log[N.sub.[pi]] + M) for [N.sub.[pi]] equispaced frequencies and M nonequispaced sampling nodes, NFFTs differ substantially in their computation time for interesting problem sizes. For its actual usage, we summarise:

1. If the problem size is really small, e.g., N = M < 32 for d = 1, just use the NDFT or its Horner-like derivative.

2. The simplest fast method is the Taylor expansion based NFFT; it achieves not even single precision, needs a somewhat larger oversampling factor, and is slower than window function based methods.

3. If the problem barely fits into your computer, you should use the fast Gaussian gridding NFFT, i.e., the Gaussian window function in conjunction with the flag FG_PSI which uses no extra memory.

4. Using only a small amount of memory for precomputation and asking for high accuracy, the fast Gaussian gridding NFFT with precomputation per forms best while storing 2d real numbers per node. However, the Kaiser-Bessel window in conjunction with the lookup table method PR]E_LIN_PSI with [2.sup.12] precomputed values suffices for single precision [10.sup.-8], regardless of the problem size, and outperforms the fast Gaussian gridding. Furthermore, the lookup table is the only precomputation method which is independent of the actual sampling set {[x.sub.j]}.

5. If a medium amount of memory can be used for precomputation, the Kaiser-Bessel window function performs best. The tensor product based precomputation scheme PRE_PSI yields a faster NFFT than the lookup table method or the fast Gaussian gridding with precomputation, but stores for each node dm real numbers. For small to medium size problems, one can gain another factor 2 to 5 by means of a fully precomputed window function PRE_FULL_PSI. However, this causes a storage cost of [m.sup.d] real numbers per sampling node.

6. Default precomputation methods, selected by the simple initialisation routine of the NFFT, are: PRE_PHI_HUT for the deconvolution step, the flag FFTW_MEASURE for planning the FFT, and the tensor product based precomputation scheme PRE_PSI for the convolution/evaluation step. Furthermore, the Kaiser-Bessel window function is selected as default at compilation.


The first author is grateful for support of this work by the German Academic Exchange Service (DAAD DAAD Deutscher Akademischer Austauschdienst (German Academic Exchange Service) ) and the warm hospitality during his stay at the Numerical Harmonic Analysis harmonic analysis
The study of functions given by a Fourier series or analogous representations, such as periodic functions and functions on topological groups.
 Group, University of Vienna History
The University was founded on March 12, 1365 by Duke Rudolph IV and his brothers Albert III and Leopold III, hence the additional name "Alma Mater Rudolphina". After the Charles University in Prague, the University of Vienna is the second oldest university in Central
. Furthermore, we would like to thank Matt Fulkerson for contributing an early version of the fast Gaussian gridding to the NFFT software.


[1] C. Anderson and M. Dahleh, Rapid computation of the discrete Fourier transform, SIAM J. Sci. Comput., 17, 913-919, 1996.

[2] A. Averbuch, R. Coifman, D. L. Donoho, M. Elad, and M. Israeli, Fast and accurate polar Fourier transform Fourier transform

In mathematical analysis, an integral transform useful in solving certain types of partial differential equations. A function's Fourier transform is derived by integrating the product of the function and a kernel function (an exponential function raised to
, Appl. Comput. Harmon. Anal., 21, 145 -167, 2006.

[3] S. Bagchi and S. K. Mitra, The nonuniform discrete Fourier transform. In F. Marvasti, editor, Nonuniform Sampling: Theory and Practice, Kluwer/Plenum, 2001.

[4] P. J. Beatty, D. G. Nishimura, and J. M. Pauly, Rapid gridding reconstruction with a minimal oversampling ratio, IEEE (Institute of Electrical and Electronics Engineers, New York, A membership organization that includes engineers, scientists and students in electronics and allied fields.  Trans. Med. Imag., 24, 799 -808, 2005.

[5] G. Beylkin, On the fast Fourier transform of functions with singularities, Appl. Comput. Harmon. Anal., 2, 363-381, 1995.

[6] E. J. Candes, L. Demanet, D. L. Donoho, and L. Ying, Fast discrete curvelet transforms, SIAM Multiscale Model. Simul simul /sim·ul/ (sim´ul) [L.] at the same time as. ., 3, 861-899, 2006.

[7] A. J. W. Duijndam and M. A. Schonewille, Nonuniform fast Fourier transform, Geophysics, 64, 539-551, 1999.

[8] A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Star. Comput., 14, 1368-1393, 1993.

[9] A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data II, Appl. Comput. Harmon. Anal., 2, 85-100, 1995.

[10] H. Eggers Eggers may refer to:
  • Dave Eggers - an American writer and editor
  • Eggers Industries - Neenah, WI Door Manufacturer
  • Eggers Island - an island of Greenland
  • Eggers - a character portrayed in Sealab 2021
  • Captain Reinhold Eggers - Colditz security chief.
, T. Knopp, and D. Potts, Field inhomogeneity in·ho·mo·ge·ne·i·ty  
n. pl. in·ho·mo·ge·ne·i·ties
1. Lack of homogeneity.

2. Something that is not homogeneous or uniform.

Noun 1.
 correction based on gridding reconstruction, IEEE Trans. Med. Imag., 26, 374-384, 2007.

[11] B. Elbel and G. Steidl, Fast Fourier transform for nonequispaced data. In C. K. Chui and L. L. Schumaker, editors, Approximation Theory In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterising the errors introduced thereby. Note that what is meant by best and simpler will depend on the application.  IX, 39-46, Vanderbilt University Press Vanderbilt University Press, founded in 1940, is a university press that is part of Vanderbilt University. External link
  • Vanderbilt University Press
, Nashville, 1998.

[12] G. E. Fasshauer and J. Zhang, Recent results for moving least squares approximation. In L. Lucian and M. Neamtu, editors, Geometric Modeling A geometric model describes the shape of a physical or mathematical object by means of geometric concepts. Geometric model(l)ing is the construction or use of geometric models.  and Computing, 163-176, Nashboro Press, Brentwood, 2003.

[13] H. G. Feichtinger, K. Gr6chenig, and T. Strohmer, Efficient numerical methods in non-uniform sampling theory, Numer. Math., 69, 423-440, 1995.

[14] M. Fenn, S. Kunis, and D. Potts, On the computation of the polar FFT, Appl. Comput. Harmon. Anal., 22, 257-263, 2007.

[15] J. A. Fessler and B. P. Sutton, Nonuniform fast Fourier transforms using min-max interpolation, IEEE Trans. Signal Process., 51, 560-574, 2003.

[16] K. Fourmont, Non equispaced fast Fourier transforms with applications to tomography, J. Fourier Anal. Appl., 9, 431-450, 2003.

[17] M. Frigo and S. G. Johnson, FFTW, C subroutine library Noun 1. subroutine library - (computing) a collection of standard programs and subroutines that are stored and available for immediate use
program library, library

[18] D. Gottlieb, B. Gustafsson, and P. Forssen, On the direct Fourier method for computer tomography, IEEE Trans. Med. Imag., 9, 223-232, 2000.

[19] L. Greengard and J.-Y. Lee, Accelerating the nonuniform fast Fourier transform, SIAM Rev., 46, 443-454, 2004.

[20] K. Grochenig, A discrete theory of irregular sampling, Lin. Alg. Appl., 193, 129-150, 1993.

[21] J. A. Hogan and J. D. Lakey, Time-Frequency and Time-Scale Methods: Wavelets See wavelet compression.

The elementary building blocks in a mathematical tool for analyzing functions. The functions can be very diverse; examples are solutions of a differential equation, and one- and two-dimensional signals.
, Sampling, Uncertainty Principles, Applied and Numerical Harmonic Analysis series, Birkhauser, Boston, 2005.

[22] J. I. Jackson, C. H. Meyer, D. G. Nishimura, and A. Macovski, Selection of a convolution function for Fourier inversion using gridding, IEEE Trans. Med. Imag., 10, 473-478, 1991.

[23] J. Keiner, S. Kunis, and D. Potts, Fast summation of radial functions on the sphere, Computing, 78, 1-15, 2006.

[24] S. Kunis and D. Potts, NFFT, Softwarepackage, C subroutine library,, 2002-2006.

[25] S. Kunis and D. Potts, Fast spherical Fourier algorithms, J. Comput. Appl. Math., 161, 75-98, 2003.

[26] S. Kunis and D. Potts, Stability results for scattered data interpolation by trigonometric polynomials, SIAM J. Sci. Comput., 29, 1403-1419, 2007.

[27] J. Ma and M. Fenn, Combined complex ridgelet shrinkage and total variation minimization, SIAM J. Sci. Comput., 28, 984-1000, 2006.

[28] S. Matej, J. A. Fessler, and I. G. Kazantsev, Iterative it·er·a·tive  
1. Characterized by or involving repetition, recurrence, reiteration, or repetitiousness.

2. Grammar Frequentative.

Noun 1.
 tomographic image reconstruction using Fourier-based forward and back-projectors, IEEE Trans. Med. Imag., 23, 401-412, 2004.

[29] F. Natterer Natterer could be:
  • August Natterer (1868 - 1933), also known as Neter, was a schizophrenic German outsider artist.
  • Johann Natterer (1787-1843), Austrian explorer and naturalist.
  • Natterer's bat, Myotis nattereri
 and F. Wubbeling, Mathematical Methods in Image Reconstruction, SIAM, Philadelphia, 2000.

[30] N. Nguyen and Q. H. Liu, The regular Fourier matrices and nonuniform fast Fourier transforms, SIAM J. Sci. Comput., 21, 283-293, 1999.

[31] A. Nieslony and G. Steidl, Approximate factorizations of Fourier matrices with nonequispaced knots, Linear Algebra Appl., 266, 337-351, 2003.

[32] J. D. O'Sullivan, A fast sinc function In mathematics, the sinc function, denoted by , has two definitions, sometimes distinguished as the normalized sinc function and unnormalized sinc function:
 gridding algorithm for Fourier inversion in computer tomography, IEEE Trans. Med. Imag., 4, 200-207, 1985.

[33] D. Potts, Schnelle Fourier-Transformationen fur Nichtaquidistante Daten und Anwendungen, Habilitation habilitation,
n See rehabilitation.
, Universitat zu Lubeck, 2003.

[34] D. Potts and G. Steidl, A new linogram algorithm for computerized tomography computerized tomography
n. Abbr. CT
Computerized axial tomography.

Noun 1. computerized tomography - a method of examining body organs by scanning them with X rays and using a computer to construct a series of
, IMA (Interactive Multimedia Association, Annapolis, MD) An earlier trade association founded in 1988 originally as the Interactive Video Industry Association. It provided an open process for adopting existing technologies and was involved in subjects such as networked services, scripting  J. Numer. Anal., 21, 769-782, 2001.

[35] D. Potts and G. Steidl, Fast summation at nonequispaced knots by NFFTs, SIAM J. Sci. Comput., 24, 2013-2037, 2003.

[36] D. Potts, G. Steidl, and A. Nieslony, Fast convolution with radial kernels at nonequispaced knots, Numer. Math., 98, 329-351, 2004.

[37] D. Potts, G. Steidl, and M. Tasche, Fast Fourier transforms for nonequispaced data: A tutorial. In J. J. Benedetto and P. J. S. G. Ferreira, editors, Modern Sampling Theory: Mathematics and Applications, 247-270, Birkhauser, Boston, 2001.

[38] G. Steidl, A note on fast Fourier transforms for nonequispaced grids, Adv. Comput. Math., 9, 337-353, 1998.

[39] B. P. Sutton, D. C. Noll, and J. A. Fessler, Fast, iterative, field-corrected image reconstruction for MRI 1. (application) MRI - Magnetic Resonance Imaging.
2. MRI - Measurement Requirements and Interface.
 in the presence of field inhomogeneities, IEEE Trans. Med. Imag., 22, 178-188, 2003.

[40] M. Tasche and H. Zeuner, Roundoff error analysis for fast trigonometric transforms. In Handbook of Analytic-Computational Methods in Applied Mathematics, 357-406, CRC (Cyclical Redundancy Checking) An error checking technique used to ensure the accuracy of transmitting digital data. The transmitted messages are divided into predetermined lengths which, used as dividends, are divided by a fixed divisor.  Press, Boca Raton Boca Raton (bō`kə rətōn`), city (1990 pop. 61,492), Palm Beach co., SE Fla., on the Atlantic; inc. 1925. Boca Raton is a popular resort and retirement community that experienced significant industrial development in the 1970s and 80s. , FL, 2000.

[41] A. F. Ware, Fast approximate Fourier transforms for irregularly spaced data. SIAM Rev., 40, 838-856, 1998.

Stefan Kunis

Department of Mathematics, Chemnitz University of Technology Chemnitz University of Technology is located in the town of Chemnitz in Germany. With over 10000 students it is the third largest university in Saxony and around 750 international students from one of the 100 universities all over the world are enrolled each year.  

Reichenhainer Str. 39, 09107 Chemnitz, Germany

Daniel Potts

Department of Mathematics, Chemnitz University of Technology

Reichenhainer Str. 39, 09107 Chemnitz, Germany
Table 2.1: Number of precomputed and stored complex exponentials
(memory), the order of magnitude for the number of floating point
operations (flops), and the number of evaluations for the function
cexp() (evaluations).

NDFT method            memory           flops        evaluations

standard                 --         [MN.sub.[pi]]   [MN.sub.[pi]]
Horner-like              --         [MN.sub.[pi]]        2dM
fully precomputed   [MN.sub.[pi]]   [MN.sub.[pi]]        --

Table 2.2: Computational requirements for
the deconvolution step in Algorithm 2.

Method            memory           flops       evaluations

--                  --          [N.sub.[pi]]   [N.sub.[pi]]
PRE_PHI_HUT   [N.sub.0] + ...   [N.sub.[pi]]        --
               + [N.sub.d-1]

Table 3.1: Theoretical order of magnitude for memory requirements,
extra floating point operations, and the evaluations of the window
function [phi]. Furthermore, at most 2[(2m + 1).sup.d] multiplications
are used within each scheme besides PRE_FULL_PSI to compute the
multivariate window function out of its univariate factors, denoted
by *.

Method              memory     extra flops   evaluations

--                    --            *        [m.sup.d]M
FG_PSI                --          dm, *          dM
PRE_LIN_PSI           dK          dm, *          --
PRE_FG_PSI            dM          dm, *          --
PRE_PSI              dmM            *            --
PRE_FULL_PSI      [m.sup.d]M       --            --
COPYRIGHT 2008 Sampling Publishing
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

 Reader Opinion




Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:fast Fourier transform
Author:Kunis, Stefan; Potts, Daniel
Publication:Sampling Theory in Signal and Image Processing
Article Type:Technical report
Geographic Code:4EUGE
Date:Jan 1, 2008
Previous Article:The tensor product of frames.
Next Article:Preface.

Related Articles
Integrated marketing.
Xilinx Spartan-3 devices enable high performance DSP functions at breakthrough low cost price points.
Microchip Technology announces two new entry-level development tools.
PU film technology provides stable parts.
Black liquor: predicting droplet size from black liquor spray characteristics.
Portable balancing.
Cristini Group Fiber Scan.
IPFlex and Sobal Co-Develop FFT Development Kit for DAPDNA-2 - Starts Shipping Today.
Discrete and continuous fourier transforms; analysis, applications and fast algorithms.

Terms of use | Copyright © 2014 Farlex, Inc. | Feedback | For webmasters