# Python interface¶

## Quick-start examples¶

The easiest way to install is to run pip install finufft, which downloads and installs the latest precompiled binaries from PyPI. Please note that the finufftpy package is obsolete. If you would like to compile from source, see the Python installation instructions.

To calculate a 1D type 1 transform, from nonuniform to uniform points, we import finufft, specify the nonuniform points x, their strengths c, and call nufft1d1:

import numpy as np
import finufft

# number of nonuniform points
M = 100000

# the nonuniform points
x = 2 * np.pi * np.random.uniform(size=M)

# their complex strengths
c = (np.random.standard_normal(size=M)
+ 1J * np.random.standard_normal(size=M))

# desired number of Fourier modes (uniform outputs)
N = 200000

# calculate the transform
f = finufft.nufft1d1(x, c, N)


The input here is a set of complex strengths c, which are used to approximate (1) in Mathematical definitions of transforms. That approximation is stored in f, which is indexed from -N // 2 up to N // 2 - 1 (since N is even; if odd it would be -(N - 1) // 2 up to (N - 1) // 2). The approximation is accurate to a tolerance of 1e-6, which is the default tolerance of nufft1d1. It can be modified using the eps argument:

# calculate the transform to higher accuracy
f = finufft.nufft1d1(x, c, N, eps=1e-12)


Note, however, that a lower tolerance (that is, a higher accuracy) results in a slower transform. See python/examples/simple1d1.py for the demo code that includes a basic math test (useful to check both the math and the indexing).

For higher dimensions, we would specify point locations in more than one dimension:

# 2D nonuniform points (x,y coords)
x = 2 * np.pi * np.random.uniform(size=M)
y = 2 * np.pi * np.random.uniform(size=M)

# desired number of Fourier modes (in x, y directions respectively)
N1 = 1000
N2 = 2000

# the 2D transform outputs f array of shape (N1, N2)
f = finufft.nufft2d1(x, y, c, (N1, N2))


See python/examples/simple2d1.py for the demo code that includes a basic math test (useful to check both the math and the indexing).

We can also go the other way, from uniform to non-uniform points, using a type 2 transform:

# input Fourier coefficients
f = (np.random.standard_normal(size=(N1, N2))
+ 1J * np.random.standard_normal(size=(N1, N2)))

# calculate the 2D type 2 transform
c = finufft.nufft2d2(x, y, f)


Now the output is a complex vector of length M approximating (2) in Mathematical definitions of transforms, that is the adjoint (but not inverse) of (1). (Note that the default sign in the exponential is negative for type 2 in the Python interface.)

In addition to tolerance eps, we can adjust other options for the transform. These are listed in Options parameters and are specified as keyword arguments in the Python interface. For example, to change the mode ordering to FFT style (that is, in each dimension Ni = N1 or N2, the indices go from 0 to Ni // 2 - 1, then from -Ni // 2 to -1, since each Ni is even), we call

f = finufft.nufft2d1(x, y, c, (N1, N2), modeord=1)


We can also specify a preallocated output array using the out keyword argument. This would be done by

# allocate the output array
f = np.empty((N1, N2), dtype='complex128')

# calculate the transform
finufft.nufft2d1(x, y, c, out=f)


In this case, we do not need to specify the output shape since it can be inferred from f.

Note that the above functions are all vectorized, which means that they can take multiple inputs stacked along the first dimension (that is, in row-major order) and process them simultaneously. This can bring significant speedups for small inputs by avoiding multiple short calls to FINUFFT. For the 2D type 1 vectorized interface, we would call

# number of transforms
K = 4

# generate K stacked coefficient arrays
c = (np.random.standard_normal(size=(K, M))
+ 1J * np.random.standard_normal(size=(K, M)))

# calculate the K transforms simultaneously (K is inferred from c.shape)
f = finufft.nufft2d1(x, y, c, (N1, N2))


The output array f would then have the shape (K, N1, N2). See the complete demo in python/examples/many2d1.py.

More fine-grained control can be obtained using the plan (or guru) interface. Instead of preparing the transform, setting the nonuniform points, and executing the transform all at once, these steps are seperated into different function calls. This can speed up calculations if multiple transforms are executed for the same grid size, since the same FFTW plan can be reused between calls. Additionally, if the same nonuniform points are reused between calls, we gain an extra speedup since the points only have to be sorted once. To perform the call above using the plan interface, we would write

# specify type 1 transform
nufft_type = 1

# instantiate the plan (note ntrans must be set here)
plan = finufft.Plan(nufft_type, (N1, N2), n_trans=K)

# set the nonuniform points
plan.setpts(x, y)

# execute the plan
f = plan.execute(c)


See the complete demo in python/examples/guru2d1.py. All interfaces support both single and double precision, but for the plan, this must be specified at initialization time using the dtype argument

# convert input data to single precision
x = x.astype('float32')
y = y.astype('float32')
c = c.astype('complex64')

# instantiate the plan and set the points
plan = finufft.Plan(nufft_type, (N1, N2), n_trans=K, dtype='float32')
plan.setpts(x, y)

# execute the plan, giving single-precision output
f = plan.execute(c)


See the complete demo, with math test, in python/examples/guru2d1f.py.

## Full documentation¶

The Python interface to FINUFFT is divided into two parts: the simple interface (through the nufft* functions) and the more advanced plan interface (through the Plan class). The former allows the user to perform an NUFFT in a single call while the latter allows for more efficient reuse of resources when the same NUFFT is applied several times to different data by saving FFTW plans, sorting the nonuniform points, and so on.

finufft.nufft1d1(x, c, n_modes=None, out=None, eps=1e-06, isign=1, **kwargs)

1D type-1 (nonuniform to uniform) complex NUFFT

        M-1
f[k1] = SUM c[j] exp(+/-i k1 x(j))
j=0

for -N1/2 <= k1 <= (N1-1)/2

Parameters: x (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. c (complex[M] or complex[ntransf, M]) – source strengths. n_modes (integer or integer tuple of length 1, optional) – number of uniform Fourier modes requested (N1, ). May be even or odd; in either case, modes k1 are integers satisfying -N1/2 <= k1 <= (N1-1)/2. Must be specified if out is not given. out (complex[N1] or complex[ntransf, N1], optional) – output array for Fourier mode values. If n_modes is specifed, the shape must match, otherwise n_modes is inferred from out. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign in exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.

Note

The output is written into the out array if supplied.

Returns: The resulting array. complex[N1] or complex[ntransf, N1]

Example:

# number of nonuniform points
M = 100

# the nonuniform points
x = 2 * np.pi * np.random.uniform(size=M)

# their complex strengths
c = (np.random.standard_normal(size=M)
+ 1J * np.random.standard_normal(size=M))

# desired number of Fourier modes
N1 = 50

# calculate the type-1 NUFFT
f = finufft.nufft1d1(x, c, (N1, ))


See also python/examples/simple1d1.py, python/examples/simpleopts1d1.py.

finufft.nufft1d2(x, f, out=None, eps=1e-06, isign=-1, **kwargs)

1D type-2 (uniform to nonuniform) complex NUFFT

c[j] = SUM f[k1] exp(+/-i k1 x(j))
k1

for j = 0, ..., M-1, where the sum is over -N1/2 <= k1 <= (N1-1)/2

Parameters: x (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. f (complex[N1] or complex[ntransf, N1]) – Fourier mode coefficients, where N1 may be even or odd. In either case the mode indices k1 satisfy -N1/2 <= k1 <= (N1-1)/2. out (complex[M] or complex[ntransf, M], optional) – output array at targets. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign in exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.

Note

The output is written into the out array if supplied.

Returns: The resulting array. complex[M] or complex[ntransf, M]

Example:

# number of nonuniform points
M = 100

# the nonuniform points
x = 2 * np.pi * np.random.uniform(size=M)

# number of Fourier modes
N1 = 50

# the Fourier mode coefficients
f = (np.random.standard_normal(size=(N1, ))
+ 1J * np.random.standard_normal(size=(N1, )))

# calculate the type-2 NUFFT
c = finufft.nufft1d2(x, f)


See also python/test/accuracy_speed_tests.py.

finufft.nufft1d3(x, c, s, out=None, eps=1e-06, isign=1, **kwargs)

1D type-3 (nonuniform to nonuniform) complex NUFFT

       M-1
f[k] = SUM c[j] exp(+/-i s[k] x[j]),
j=0

for k = 0, ..., N-1

Parameters: x (float[M]) – nonuniform source points. c (complex[M] or complex[ntransf, M]) – source strengths. s (float[N]) – nonuniform target points. out (complex[N] or complex[ntransf, N]) – output values at target frequencies. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign in exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.

Note

The output is written into the out array if supplied.

Returns: The resulting array. complex[M] or complex[ntransf, M]

Example:

# number of source points
M = 100

# number of target points
N = 200

# the source points
x = 2 * np.pi * np.random.uniform(size=M)

# the target points
s = 2 * np.pi * np.random.uniform(size=N)

# their complex strengths
c = (np.random.standard_normal(size=M)
+ 1J * np.random.standard_normal(size=M))

# calcuate the type-3 NUFFT
f = finufft.nufft1d3(x, c, s)


See also python/test/accuracy_speed_tests.py.

finufft.nufft2d1(x, y, c, n_modes=None, out=None, eps=1e-06, isign=1, **kwargs)

2D type-1 (nonuniform to uniform) complex NUFFT

            M-1
f[k1, k2] = SUM c[j] exp(+/-i (k1 x(j) + k2 y(j)))
j=0

for -N1/2 <= k1 <= (N1-1)/2, -N2/2 <= k2 <= (N2-1)/2

Parameters: x (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. y (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. c (complex[M] or complex[ntransf, M]) – source strengths. n_modes (integer or integer tuple of length 2, optional) – number of uniform Fourier modes requested (N1, N2). May be even or odd; in either case, modes k1, k2 are integers satisfying -N1/2 <= k1 <= (N1-1)/2, -N2/2 <= k2 <= (N2-1)/2. Must be specified if out is not given. out (complex[N1, N2] or complex[ntransf, N1, N2], optional) – output array for Fourier mode values. If n_modes is specifed, the shape must match, otherwise n_modes is inferred from out. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign in exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.

Note

The output is written into the out array if supplied.

Returns: The resulting array. complex[N1, N2] or complex[ntransf, N1, N2]

Example:

# number of nonuniform points
M = 100

# the nonuniform points
x = 2 * np.pi * np.random.uniform(size=M)
y = 2 * np.pi * np.random.uniform(size=M)

# their complex strengths
c = (np.random.standard_normal(size=M)
+ 1J * np.random.standard_normal(size=M))

# desired number of Fourier modes
N1, N2 = 50, 75

# calculate the type-1 NUFFT
f = finufft.nufft2d1(x, y, c, (N1, N2))


See also python/examples/simple2d1.py, python/examples/many2d1.py.

finufft.nufft2d2(x, y, f, out=None, eps=1e-06, isign=-1, **kwargs)

2D type-2 (uniform to nonuniform) complex NUFFT

c[j] = SUM f[k1, k2] exp(+/-i (k1 x(j) + k2 y(j)))
k1, k2

for j = 0, ..., M-1, where the sum is over -N1/2 <= k1 <= (N1-1)/2,
-N2/2 <= k2 <= (N2-1)/2

Parameters: x (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. y (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. f (complex[N1, N2] or complex[ntransf, N1, N2]) – Fourier mode coefficients, where N1, N2 may be even or odd. In either case the mode indices k1, k2 satisfy -N1/2 <= k1 <= (N1-1)/2, -N2/2 <= k2 <= (N2-1)/2. out (complex[M] or complex[ntransf, M], optional) – output array at targets. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign in exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.

Note

The output is written into the out array if supplied.

Returns: The resulting array. complex[M] or complex[ntransf, M]

Example:

# number of nonuniform points
M = 100

# the nonuniform points
x = 2 * np.pi * np.random.uniform(size=M)
y = 2 * np.pi * np.random.uniform(size=M)

# number of Fourier modes
N1, N2 = 50, 75

# the Fourier mode coefficients
f = (np.random.standard_normal(size=(N1, N2))
+ 1J * np.random.standard_normal(size=(N1, N2)))

# calculate the type-2 NUFFT
c = finufft.nufft2d2(x, y, f)


See also python/test/accuracy_speed_tests.py.

finufft.nufft2d3(x, y, c, s, t, out=None, eps=1e-06, isign=1, **kwargs)

2D type-3 (nonuniform to nonuniform) complex NUFFT

       M-1
f[k] = SUM c[j] exp(+/-i (s[k] x[j] + t[k] y[j])),
j=0

for k = 0, ..., N-1

Parameters: x (float[M]) – nonuniform source points. y (float[M]) – nonuniform source points. c (complex[M] or complex[ntransf, M]) – source strengths. s (float[N]) – nonuniform target points. t (float[N]) – nonuniform target points. out (complex[N] or complex[ntransf, N]) – output values at target frequencies. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign in exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.

Note

The output is written into the out array if supplied.

Returns: The resulting array. complex[M] or complex[ntransf, M]

Example:

# number of source points
M = 100

# number of target points
N = 200

# the source points
x = 2 * np.pi * np.random.uniform(size=M)
y = 2 * np.pi * np.random.uniform(size=M)

# the target points
s = 2 * np.pi * np.random.uniform(size=N)
t = 2 * np.pi * np.random.uniform(size=N)

# their complex strengths
c = (np.random.standard_normal(size=M)
+ 1J * np.random.standard_normal(size=M))

# calcuate the type-3 NUFFT
f = finufft.nufft2d3(x, y, c, s, t)


See also python/test/accuracy_speed_tests.py.

finufft.nufft3d1(x, y, z, c, n_modes=None, out=None, eps=1e-06, isign=1, **kwargs)

3D type-1 (nonuniform to uniform) complex NUFFT

                M-1
f[k1, k2, k3] = SUM c[j] exp(+/-i (k1 x(j) + k2 y(j) + k3 z(j)))
j=0

for -N1/2 <= k1 <= (N1-1)/2, -N2/2 <= k2 <= (N2-1)/2, -N3/2 <= k3 <=
(N3-1)/2

Parameters: x (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. y (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. z (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. c (complex[M] or complex[ntransf, M]) – source strengths. n_modes (integer or integer tuple of length 3, optional) – number of uniform Fourier modes requested (N1, N2, N3). May be even or odd; in either case, modes k1, k2, k3 are integers satisfying -N1/2 <= k1 <= (N1-1)/2, -N2/2 <= k2 <= (N2-1)/2, -N3/2 <= k3 <= (N3-1)/2. Must be specified if out is not given. (complex[N1, N2, N3] or complex[ntransf, N1, N2, N3], (out) – optional): output array for Fourier mode values. If n_modes is specifed, the shape must match, otherwise n_modes is inferred from out. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign in exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.

Note

The output is written into the out array if supplied.

Returns: The resulting array. complex[N1, N2, N3] or complex[ntransf, N1, N2, N3]

Example:

# number of nonuniform points
M = 100

# the nonuniform points
x = 2 * np.pi * np.random.uniform(size=M)
y = 2 * np.pi * np.random.uniform(size=M)
z = 2 * np.pi * np.random.uniform(size=M)

# their complex strengths
c = (np.random.standard_normal(size=M)
+ 1J * np.random.standard_normal(size=M))

# desired number of Fourier modes
N1, N2, N3 = 50, 75, 100

# calculate the type-1 NUFFT
f = finufft.nufft3d1(x, y, z, c, (N1, N2, N3))


See also python/test/accuracy_speed_tests.py.

finufft.nufft3d2(x, y, z, f, out=None, eps=1e-06, isign=-1, **kwargs)

3D type-2 (uniform to nonuniform) complex NUFFT

c[j] = SUM f[k1, k2, k3] exp(+/-i (k1 x(j) + k2 y(j) + k3 z(j)))
k1, k2, k3

for j = 0, ..., M-1, where the sum is over -N1/2 <= k1 <= (N1-1)/2,
-N2/2 <= k2 <= (N2-1)/2, -N3/2 <= k3 <= (N3-1)/2

Parameters: x (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. y (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. z (float[M]) – nonuniform points, valid only in [-3pi, 3pi]. f (complex[N1, N2, N3] or complex[ntransf, N1, N2, N3]) – Fourier mode coefficients, where N1, N2, N3 may be even or odd. In either case the mode indices k1, k2, k3 satisfy -N1/2 <= k1 <= (N1-1)/2, -N2/2 <= k2 <= (N2-1)/2, -N3/2 <= k3 <= (N3-1)/2. out (complex[M] or complex[ntransf, M], optional) – output array at targets. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign in exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.

Note

The output is written into the out array if supplied.

Returns: The resulting array. complex[M] or complex[ntransf, M]

Example:

# number of nonuniform points
M = 100

# the nonuniform points
x = 2 * np.pi * np.random.uniform(size=M)
y = 2 * np.pi * np.random.uniform(size=M)
z = 2 * np.pi * np.random.uniform(size=M)

# number of Fourier modes
N1, N2, N3 = 50, 75, 100

# the Fourier mode coefficients
f = (np.random.standard_normal(size=(N1, N2, N3))
+ 1J * np.random.standard_normal(size=(N1, N2, N3)))

# calculate the type-2 NUFFT
c = finufft.nufft3d2(x, y, z, f)


See also python/test/accuracy_speed_tests.py.

finufft.nufft3d3(x, y, z, c, s, t, u, out=None, eps=1e-06, isign=1, **kwargs)

3D type-3 (nonuniform to nonuniform) complex NUFFT

       M-1
f[k] = SUM c[j] exp(+/-i (s[k] x[j] + t[k] y[j] + u[k] z[j])),
j=0

for k = 0, ..., N-1

Parameters: x (float[M]) – nonuniform source points. y (float[M]) – nonuniform source points. z (float[M]) – nonuniform source points. c (complex[M] or complex[ntransf, M]) – source strengths. s (float[N]) – nonuniform target points. t (float[N]) – nonuniform target points. u (float[N]) – nonuniform target points. out (complex[N] or complex[ntransf, N]) – output values at target frequencies. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign in exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.

Note

The output is written into the out array if supplied.

Returns: The resulting array. complex[M] or complex[ntransf, M]

Example:

# number of source points
M = 100

# number of target points
N = 200

# the source points
x = 2 * np.pi * np.random.uniform(size=M)
y = 2 * np.pi * np.random.uniform(size=M)
z = 2 * np.pi * np.random.uniform(size=M)

# the target points
s = 2 * np.pi * np.random.uniform(size=N)
t = 2 * np.pi * np.random.uniform(size=N)
u = 2 * np.pi * np.random.uniform(size=N)

# their complex strengths
c = (np.random.standard_normal(size=M)
+ 1J * np.random.standard_normal(size=M))

# calcuate the type-3 NUFFT
f = finufft.nufft3d3(x, y, z, c, s, t, u)


See also python/test/accuracy_speed_tests.py.

class finufft.Plan(nufft_type, n_modes_or_dim, n_trans=1, eps=1e-06, isign=None, **kwargs)

A non-uniform fast Fourier transform (NUFFT) plan

The Plan class lets the user exercise more fine-grained control over the execution of an NUFFT. First, the plan is created with a certain set of parameters (type, mode configuration, tolerance, sign, number of simultaneous transforms, and so on). Then the nonuniform points are set (source or target depending on the type). Finally, the plan is executed on some data, yielding the desired output.

In the simple interface, all these steps are executed in a single call to the nufft* functions. The benefit of separating plan creation from execution is that it allows for plan reuse when certain parameters (like mode configuration) or nonuniform points remain the same between different NUFFT calls. This becomes especially important for small inputs, where execution time may be dominated by initialization steps such as allocating and FFTW plan and sorting the nonuniform points.

Example:

import numpy as np
import finufft

# set up parameters
n_modes = (1000, 2000)
n_pts = 100000
nufft_type = 1
n_trans = 4

# generate nonuniform points
x = 2 * np.pi * np.random.uniform(size=n_pts)
y = 2 * np.pi * np.random.uniform(size=n_pts)

# generate source strengths
c = (np.random.standard_normal(size=(n_trans, n_pts)),
+ 1J * np.random.standard_normal(size=(n_trans, n_pts)))

# initialize the plan
plan = finufft.Plan(nufft_type, n_modes, n_trans)

# set the nonuniform points
plan.setpts(x, y)

# execute the plan
f = plan.execute(c)


Also see python/examples/guru1d1.py and python/examples/guru2d1.py.

Parameters: nufft_type (int) – type of NUFFT (1, 2, or 3). n_modes_or_dim (int or tuple of ints) – if nufft_type is 1 or 2, this should be a tuple specifying the number of modes in each dimension (for example, (50, 100)), otherwise, if nufft_type is 3, this should be the number of dimensions (between 1 and 3). n_trans (int, optional) – number of transforms to compute simultaneously. eps (float, optional) – precision requested (>1e-16). isign (int, optional) – if non-negative, uses positive sign exponential, otherwise negative sign. **kwargs (optional) – for more options, see Options parameters.
setpts(x=None, y=None, z=None, s=None, t=None, u=None)

Set the nonuniform points

For type 1, this sets the coordinates of the M nonuniform source points, for type 2, it sets the coordinates of the M target points, and for type 3 it sets both the M source points and the N target points.

The dimension of the plan determines the number of arguments supplied. For example, if dim == 2, we provide x and y (as well as s and t for a type-3 transform).

Parameters: x (float[M]) – first coordinate of the nonuniform points (source for type 1 and 3, target for type 2). y (float[M], optional) – second coordinate of the nonuniform points (source for type 1 and 3, target for type 2). z (float[M], optional) – third coordinate of the nonuniform points (source for type 1 and 3, target for type 2). s (float[N], optional) – first coordinate of the nonuniform points (target for type 3). t (float[N], optional) – second coordinate of the nonuniform points (target for type 3). u (float[N], optional) – third coordinate of the nonuniform points (target for type 3).
execute(data, out=None)

Execute the plan

Performs the NUFFT specified at plan instantiation with the points set by setpts. For type-1 and type-3 transforms, the input is a set of source strengths, while for a type-2 transform, it consists of an array of size n_modes. If n_transf is greater than one, n_transf` inputs are expected, stacked along the first axis.

Parameters: data (complex[M], complex[n_transf, M], complex[n_modes], or complex[n_transf, n_modes]) – The input source strengths (type 1 and 3) or source modes (type 2). out (complex[n_modes], complex[n_transf, n_modes], complex[M], or complex[n_transf, M], optional) – The array where the output is stored. Must be of the right size. The output array of the transform(s). complex[n_modes], complex[n_transf, n_modes], complex[M], or complex[n_transf, M]