API

Options

Keyword arguments of plan_nfft, plan_rnfft, plan_nfct and plan_nfst; plan_nnfft takes them without tilesize, gridsize and measure, its dims is the dimension of the sources in an array of the size given as third argument, and its window, W and σ apply to its inner NFFT:

keywordmeaning
reltolrequested relative error, default 1e-8
dimsdimensions to transform, see Transforms along Dimensions
eltypeFloat32 or Float64, default from the nodes
storagearray type of data and workspace, default from the nodes; see GPU
nthreadsnumber of threads, default Threads.nthreads()
window:auto, KaiserBessel(), ExpSemicircle(), CustomWindow(φ)
W, σwindow width and oversampling factor
fftFFT backend: FFTLBackend() (default), FFTWBackend() (needs using FFTW) or FFTABackend() (needs using FFTA; NFFT and NNFFT)
tilesizeedge length of the tiles the nodes are sorted into (expert option)
gridsizesize Ñ of the oversampled grid, an integer or one per transformed dimension, at least σN and W; any size, not only the 2,3,5-smooth ones the planner takes (expert option, plan_nfft only)
measuretrue: time the four parameter sets of lowest predicted cost at plan time and keep the fastest

The first five are part of the Abstract Interface and mean the same for every implementation; the others are specific to NFFT.jl. An unknown option is an error, and so are fft, tilesize and gridsize for plans on a GPU. How to use window, W, σ and fft is shown in Choosing Parameters.

Plans and transforms

AbstractNFFTs.plan_nfft — Function
plan_nfft([backend,] k, N; reltol=1e-8, dims=:, eltype, storage, nthreads, kwargs...)

Plan an NFFT for the nodes k (a d × J matrix, or a vector for d = 1, entries in [-1/2, 1/2)) and an equidistant array of size N (an integer or a tuple; with dims, the size of the whole array including batch dimensions). Without backend the active backend is used.

Generic options, accepted by every implementation:

  • reltol: requested relative error (ℓ² norm); a value the implementation cannot reach throws an ArgumentError
  • dims: dimensions to transform (:, an integer or a contiguous range); the other dimensions are batch dimensions and pass through unchanged
  • eltype: real element type of the data, default float(eltype(k))
  • storage: array type of data and workspace, default the array type of k
  • nthreads: number of CPU threads, default Threads.nthreads()

Further keyword arguments are specific to the implementation; an implementation throws an ArgumentError for options it does not know.

source
AbstractNFFTs.plan_nnfft — Function
plan_nnfft([backend,] k, y[, N]; kwargs...)

Plan an NNFFT with non-equidistant nodes k (D × J) in the frequency domain and y (D × M) in the spatial domain. The input is a vector of length M, or an array of size N whose dimension dims (an integer) holds the M sources; the output has the J targets in that dimension, and the other dimensions are batch dimensions. Keyword arguments as for plan_nfft.

source
AbstractNFFTs.plan_nfct — Function
plan_nfct([backend,] k, N; kwargs...)

Plan a non-equidistant fast cosine transform (NFCT) for nodes k in [0, 1/2] and a real array of size N. Keyword arguments as for plan_nfft.

source
AbstractNFFTs.plan_nfst — Function
plan_nfst([backend,] k, N; kwargs...)

Plan a non-equidistant fast sine transform (NFST) for nodes k in [0, 1/2] and a real array of size N. Keyword arguments as for plan_nfft.

source
AbstractNFFTs.plan_rnfft — Function
plan_rnfft([backend,] k, N; kwargs...)

Plan an NFFT with real values at the nodes k (in [-1/2, 1/2)) for an array of logical size N (the NFFT counterpart of FFTW's brfft/rfft). The input of the direct transform is the half h of the coefficients with n₁ = 0 … N₁÷2, an array of size (N₁÷2+1, N₂, …) whose other dimensions are indexed as in plan_nfft; the direct transform is

f̂_j = Re Σ_n h_n exp(-2πi n·k_j),

the adjoint maps real values y at the nodes to h_n = Σ_j y_j exp(2πi n·k_j). The two are adjoint with respect to the real inner product. With dims, the first of the transformed dimensions is the halved one. Keyword arguments as for plan_nfft.

source
NFFT.NFFTPlan — Type
NFFTPlan{T,D,R}

NFFT plan of NFFT.jl, created by plan_nfft(k, N; kwargs...) or NFFTPlan(k, N; kwargs...).

Generic options (every AbstractNFFTs implementation): reltol (default 1e-8), dims, eltype, storage, nthreads. Options of NFFT.jl:

  • window: :auto (default; all windows with a parameter table compete), KaiserBessel(), ExpSemicircle() or a CustomWindow (needs W and σ)
  • W: window width (integer, odd allowed; W = 2m in the notation of Knopp et al. 2023)
  • σ: oversampling factor
  • fft: FFT backend, FFTLBackend() (default) or FFTWBackend() (using FFTW), see AbstractFFTBackend
  • tilesize: expert option, tile edge of the node binning
  • gridsize: expert option, size Ñ of the oversampled grid (integer, or one per transformed dimension), at least σN and W; any size, not only the FFT-friendly ones (2, 3, 5) the planner takes. The window stays the one designed for σ.
  • measure: true times the four parameter sets of lowest predicted cost at plan time (transform and adjoint) and keeps the fastest; the cost model cannot see how fast the FFT is for a particular grid size

T is the real element type, D the number of dimensions of the array and R that of the output (1 without batch dimensions). The compiler infers the type of the plan when dims is left out or a single dimension; with a range it depends on its length.

source
NFFT.NFCTPlan — Type
NFCTPlan{T,D,R}
NFSTPlan{T,D,R}

NFCT and NFST plans of NFFT.jl, created by plan_nfct(k, N; kwargs...) and plan_nfst(k, N; kwargs...), with the definitions of NFFT3: for nodes k in [0, 1/2]^d and a real array f of size N,

NFCT: f̂_j = Σ_{n=0}^{N-1} f_n Π_d cos(2π n_d k_dj),   NFST: f̂_j = Σ_{n=1}^{N} f_n Π_d sin(2π n_d k_dj)

(the array index of mode n is n + 1 for the NFCT and n for the NFST). transpose(p) is the transposed transform. Options as for NFFTPlan; batch dimensions run as slices, in parallel or one after the other.

source
NFFT.NFSTPlan — Type
NFCTPlan{T,D,R}
NFSTPlan{T,D,R}

NFCT and NFST plans of NFFT.jl, created by plan_nfct(k, N; kwargs...) and plan_nfst(k, N; kwargs...), with the definitions of NFFT3: for nodes k in [0, 1/2]^d and a real array f of size N,

NFCT: f̂_j = Σ_{n=0}^{N-1} f_n Π_d cos(2π n_d k_dj),   NFST: f̂_j = Σ_{n=1}^{N} f_n Π_d sin(2π n_d k_dj)

(the array index of mode n is n + 1 for the NFCT and n for the NFST). transpose(p) is the transposed transform. Options as for NFFTPlan; batch dimensions run as slices, in parallel or one after the other.

source
NFFT.RNFFTPlan — Type
RNFFTPlan{T,D,R}

RNFFT plan of NFFT.jl (real values at the nodes), created by plan_rnfft(k, N; kwargs...), see plan_rnfft. Options as for NFFTPlan; batch dimensions loop over the slices.

source
NFFT.NNFFTPlan — Type
NNFFTPlan{T,D,M}

NNFFT plan of NFFT.jl (non-equidistant nodes in both domains), created by plan_nnfft(k, y[, N]; kwargs...) for targets k (D × J) and sources y (D × N), arbitrary real coordinates:

f̂_j = Σ_l f_l exp(−2πi k_j·y_l)

The cost grows with the product of the extents of k and y (the size of the inner NFFT is about 4σ²·Y·K per dimension), not with their numbers. With an array size N (M dimensions), dims selects the dimension of the sources; the transform maps it to the targets and passes the other dimensions through, one slice after the other. Generic options reltol, eltype, storage, nthreads; restrictions of the inner NFFT window (:auto, KaiserBessel() or ExpSemicircle()), W and σ, and its FFT backend fft, as for NFFTPlan.

source
NFFT.NFFTBackend — Type
NFFTBackend()

The AbstractNFFTs backend of NFFT.jl. Activated when the package is loaded; reactivate with NFFT.activate!().

source
NFFT.parameters — Function
NFFT.parameters(p) -> (; window, W, σ)

Window family, window width and oversampling factor the plan uses.

source
AbstractNFFTs.accuracy — Function
accuracy(p) -> Float64

Bound on the relative error (ℓ² norm) of the plan p; at most the requested reltol, unless the implementation's parameters were fixed by the caller.

source
NFFT.calibrate_cost — Function
NFFT.calibrate_cost(storage=Array; eltype=Float64, densities=(0.01, 0.1, 1, 10, 100), W=4:2:14,
                    σ=(1.25, 1.5, 2.0, 2.5), dims=1:3, sizes=CALIBRATION_SIZES, nrep=3, set=true)

Fit the cost model by which plans choose window width and oversampling to NFFTs timed on this machine: transform and adjoint for random nodes and every combination of the node density J/|N|, W, σ and the sizes in sizes[D] (default 2^12 and 2^16, 64² and 256², 16³ and 32³) in the dimensions dims. The coefficients are nonnegative, so that the model also extrapolates to densities outside the sweep. With set, plans with this storage and eltype use the result for the rest of the session. Returns a Dict from the dimension to the coefficients, for NFFT.set_cost_model! in a later session.

The built-in models are fitted on an Apple M1 Max (CPU with 8 threads, GPU with Metal and Float32) and, for GPUs with Float64, on an Nvidia RTX A6000 (CUDA). Other machines, thread counts and GPUs have other ratios of resampling, FFT and fixed costs. The default sweep takes a few minutes; fewer densities, widths and sizes keep it short.

source
NFFT.set_cost_model! — Function
NFFT.set_cost_model!(storage, eltype, coef)
NFFT.set_cost_model!(storage, eltype, nothing)

Use the coefficients coef (a Dict from the dimension 1, 2, 3 to a tuple, as returned by NFFT.calibrate_cost) when plans with this storage and eltype choose their parameters; nothing restores the built-in model. The setting holds for the Julia session.

source
AbstractNFFTs.size_in — Function
size_in(p)

Size of the input array for the plan p (NFFT/NFCT/NFST/NNFFT). The returned tuple has D entries. Note that this will be the output size for the transposed / adjoint operator.

source
AbstractNFFTs.size_out — Function
size_out(p)

Size of the output array for the plan p (NFFT/NFCT/NFST/NNFFT). The returned tuple has R entries. Note that this will be the input size for the transposed / adjoint operator.

source
LinearAlgebra.mul! — Function
mul!(fHat, p, f) -> fHat

In-place transform of f (size size_in(p)) into fHat (size size_out(p)).

source
mul!(f, p, fHat) -> f

In-place adjoint transform of fHat (size size_out(p)) into f (size size_in(p)).

source
mul!(f, p, fHat) -> f

In-place transposed NFCT/NFST of fHat (size size_out(p)) into f (size size_in(p)).

source
Base.:* — Function
*(p, f) -> fHat
*(adjoint(p), fHat) -> f
*(transpose(p), fHat) -> f

Apply a plan, its adjoint (NFFT, NNFFT, RNFFT) or its transpose (NFCT, NFST) and return a new array. f has size size_in(p) and fHat size size_out(p); batch dimensions (dims) are part of both. mul! writes into a given array instead.

source
AbstractNFFTs.nfft — Function
nfft(k, f; kwargs...)
nfft(backend, k, f; kwargs...)

NFFT of the array f at the nodes k (D × J, a vector for D = 1), with a plan made for this call: plan_nfft(backend, k, size(f); kwargs...) * f. For repeated transforms at the same nodes, make the plan once.

Without backend the active backend is used. A package activates itself with BackendModule.activate!(), and a scoped value overrides the active backend within a scope:

julia> NFFT.activate!()

julia> nfft(k, f)                                   # uses NFFT

julia> with(nfft_backend => NonuniformFFTs.backend()) do
          nfft(k, f)                                # uses NonuniformFFTs
       end
source
AbstractNFFTs.nfft_adjoint — Function
nfft_adjoint(k, N, fHat; kwargs...)
nfft_adjoint(backend, k, N, fHat; kwargs...)

Adjoint NFFT of the values fHat at the nodes k, an array of size N: adjoint(plan_nfft(backend, k, N; kwargs...)) * fHat. Backend as for nfft.

source
AbstractNFFTs.nfct — Function
nfct(k, f; kwargs...)
nfct(backend, k, f; kwargs...)

NFCT of the real array f at the nodes k in $[0, 1/2]^D$: plan_nfct(backend, k, size(f); kwargs...) * f. Backend as for nfft.

source
AbstractNFFTs.nfct_transpose — Function
nfct_transpose(k, N, fHat; kwargs...)
nfct_transpose(backend, k, N, fHat; kwargs...)

Transposed NFCT of the values fHat at the nodes k, an array of size N: transpose(plan_nfct(backend, k, N; kwargs...)) * fHat. Backend as for nfft.

source
AbstractNFFTs.nfst — Function
nfst(k, f; kwargs...)
nfst(backend, k, f; kwargs...)

NFST of the real array f at the nodes k in $[0, 1/2]^D$: plan_nfst(backend, k, size(f); kwargs...) * f. Backend as for nfft.

source
AbstractNFFTs.nfst_transpose — Function
nfst_transpose(k, N, fHat; kwargs...)
nfst_transpose(backend, k, N, fHat; kwargs...)

Transposed NFST of the values fHat at the nodes k, an array of size N: transpose(plan_nfst(backend, k, N; kwargs...)) * fHat. Backend as for nfft.

source

Windows and FFT

NFFT.AbstractWindow — Type
AbstractWindow

Window function of the NFFT. A window is evaluated in grid units, φ(z) for z ∈ [-W/2, W/2] (W the window width, W = 2m in the notation of Knopp et al. 2023); it is symmetric and zero outside. The resampling evaluates a piecewise polynomial fitted to φ, so the cost of φ itself does not matter.

Families with a parameter table (used by the automatic parameter choice): KaiserBessel, ExpSemicircle. Any other window can be used with explicit W and σ through CustomWindow.

source
NFFT.KaiserBessel — Type
KaiserBessel()

Continuous Kaiser–Bessel window (Potts & Tasche 2021): the sinh form sinh(β√(1−(2z/W)²))/√(1−(2z/W)²) minus its edge value β, so that it vanishes at |z| = W/2. The shape parameter β is taken from the kernel table (optimised per W and σ).

source
NFFT.ExpSemicircle — Type
ExpSemicircle()

Exponential of semicircle family, φ(z) = exp(β((1−(2z/W)²)^e₀ − 1)). e₀ = 1/2 is the ES kernel of FINUFFT (Barnett et al. 2019); a free exponent e₀ is the family used by ducc (Arras et al. 2021). β and e₀ are taken from the kernel table.

source
NFFT.CustomWindow — Type
CustomWindow(φ)

User-defined window: φ(z, W) must be symmetric in z and zero for |z| ≥ W/2. Requires explicit W and σ in the plan.

source
NFFT.AbstractFFTBackend — Type
AbstractFFTBackend

FFT used for the oversampled grid by NFFT plans (and the NNFFT): batched 1D transforms along one dimension of an array view, in place as seen from NFFT.jl. A backend B implements

  • NFFT.pass_plan(::B, ::Val{K}, v, d): a plan for the transform of the view v along dimension d, forward for K = -1, unnormalised backward for K = 1
  • NFFT.apply_pass!(plan, v): apply it to v in place (default: plan * v, an in-place plan)
  • optionally NFFT.planning(f, ::B, nthreads): run the planning f() with nthreads threads per plan (default: f())

The real transforms (RNFFT, NFCT, NFST) run with every backend: FFTW has native real and real-to-real plans, the others through complex FFTs of the same length (ComplexRealFFT) and FFTL's real-to-real passes.

source
NFFT.FFTWBackend — Type
FFTWBackend(; flags = 1 << 6)

FFTW on the CPU. In D ≥ 2 NFFT.jl threads the per-dimension passes itself over single-threaded FFTW plans: FFTW's own threading with ESTIMATE produces plans up to 17× slower than MEASURE, while single-threaded batched ESTIMATE plans are within 10–20 % of MEASURE. A transform with one dimension uses FFTW's own threading. flags is FFTW's planning flag, 1 << 6 is FFTW.ESTIMATE; needs using FFTW (the backend is a weak dependency).

source
NFFT.FFTABackend — Type
FFTABackend()

FFTA.jl, an FFT in pure Julia; needs using FFTA. For NFFT and NNFFT plans. Slower than FFTL and FFTW; its plans work out of place, so every pass keeps a buffer.

source
NFFT.FFTLBackend — Type
FFTLBackend()

FFTL.jl, the default backend: an FFT in pure Julia with batched in-place transforms along one dimension of strided views, on the CPU through plan_pass and on GPU arrays through the KernelAbstractions extension. The first plan of a length compiles its kernels.

source

Stages

AbstractNFFTs.oversampled_size — Function
oversampled_size(p) -> NTuple

Size of the oversampled equidistant array the FFT of plan p acts on. The stage interface is defined for plans without batch dimensions; an implementation throws an ArgumentError for others.

source
AbstractNFFTs.spectrum_size — Function
spectrum_size(p) -> NTuple

Size of the oversampled spectrum ĝ that the resampling correction writes and the FFT stage reads: oversampled_size(p), except for RNFFT plans (the half spectrum (Ñ₁÷2+1, Ñ₂, …)).

source
AbstractNFFTs.resampling_correction! — Function
resampling_correction!(p, f, ĝ) -> ĝ

First step of the direct NFFT: divide f by the Fourier transform of the window function and place it into the zero-padded oversampled spectrum ĝ.

source
AbstractNFFTs.oversampled_fft! — Function
oversampled_fft!(p, g) -> g
oversampled_fft!(p, ĝ, g) -> g

Second step of the direct NFFT: the FFT of the oversampled spectrum, in place on g or from ĝ into g. The out-of-place form leaves ĝ unchanged.

source
AbstractNFFTs.resampling! — Function
resampling!(p, g, fHat) -> fHat

Third step of the direct NFFT: resample the oversampled equidistant array g at the nodes.

source
AbstractNFFTs.resampling_adjoint! — Function
resampling_adjoint!(p, fHat, g) -> g

First step of the adjoint NFFT: the adjoint resampling of the values fHat at the nodes onto the oversampled equidistant array g (overwritten).

source
AbstractNFFTs.oversampled_bfft! — Function
oversampled_bfft!(p, g) -> g
oversampled_bfft!(p, g, ĝ) -> ĝ

Second step of the adjoint NFFT: the adjoint (unnormalised backward) FFT, in place on g or from g into ĝ. The out-of-place form leaves g unchanged.

source
SparseArrays.sparse — Method
sparse(p::NFFTPlan) -> B

The resampling stage of the plan p (without batch dimensions, on the CPU) as a sparse J × prod(oversampled_size(p)) matrix of window weights, W^D entries per node: for an oversampled array g, resampling!(p, g, fHat) computes fHat = B * vec(g) and resampling_adjoint!(p, fHat, g) computes vec(g) = B' * fHat. Requires using SparseArrays.

source

NFFTTools

NFFTTools.sdc — Function
weights = sdc(p::AbstractNFFTPlan; method = :pipemenon, iters)

Sampling density compensation weights for the nodes of the NFFT plan p, scaled such that $A^{\mathsf{H}} \operatorname{diag}(w) A \bm{1} ≈ \bm{1}$. For nodes on the equidistant grid of an array of size N they are ≈ 1/prod(N).

method = :pipemenon (default): iters (default 20) iterations of the method of Pipe and Menon (Magn Reson Med 41(1):179–186, 1999, doi:10.1002/(SICI)1522-2594(199901)41:1<179::AID-MRM25>3.0.CO;2-V). The iteration uses the resampling stage of the plan, i.e. the window function on the oversampled grid, as its kernel. The weights therefore depend on the window of the plan rather than on its accuracy: narrow windows give better weights than wide ones. With NFFT.jl, plan_nfft(k, N; W = 4, σ = 2.0) works well (MRI test data: 0.11 relative deviation of a gridding reconstruction from the scanner's, 0.21 with the window chosen for reltol = 1e-3). The weights are positive. p must implement the stage interface of AbstractNFFTs (oversampled_size, resampling!, resampling_adjoint!).

method = :frobenius: the weights that minimise $\|A^{\mathsf{H}} \operatorname{diag}(w) A - I\|_F$ (Sedarat and Nishimura, IEEE Trans Med Imaging 19(4):306–317, 2000), the best a diagonal weighting can do. With at least as many nodes as the doubled array has modes (prod(2 .* N)), spread without clusters, they reconstruct every array exactly. They solve $S w = |I_N| \bm{1}$ with $S_{jh} = |(A A^{\mathsf{H}})_{jh}|^2$: the entries of $A A^{\mathsf{H}}$ are the Dirichlet kernel at $x_j - x_h$, their squares the Fejér kernel, a trigonometric polynomial on the doubled array with coefficients $c_l = \prod_d (N_d - |l_d|)$. Hence $S = A_{2N} \operatorname{diag}(c) A_{2N}^{\mathsf{H}}$ costs one NFFT and one adjoint NFFT of size 2 .* N, and iters (default 50) steps of conjugate gradients minimise the Frobenius error. The weights can be negative. The plan of size 2 .* N is made with the active backend.

p must be a plan without batch dimensions.

source
NFFTTools.sdc! — Function
sdc!(weights, p::AbstractNFFTPlan; iters = 20, workg, workf, workv)

In-place version of sdc. The work arrays (complex, of sizes oversampled_size(p), size_out(p) and size_in(p)) can be passed to avoid allocations.

source
NFFTTools.calculateToeplitzKernel — Function
calculateToeplitzKernel(shape, tr::AbstractMatrix{T}; fftplan = plan_fft(zeros(Complex{T}, 2 .* shape); flags=FFTW.ESTIMATE), kwargs...)

Calculate the kernel for an implementation of the Gram matrix $A^{\mathsf{H}} A$ that utilizes its Toeplitz structure. The output is an array of twice the size of shape, as the Toeplitz trick requires an oversampling factor of 2 (cf. Wajer, F. T. A. W., and K. P. Pruessmann. "Major speedup of reconstruction for sensitivity encoding with arbitrary trajectories." Proc. Intl. Soc. Mag. Res. Med. 2001.). The type of the kernel is Complex{T}, i.e. the complex of the k-space trajectory's type; for speed and memory efficiency, call this function with Float32.(tr), and the kernel will also be Float32.

The kernel is computed with an adjoint NFFT of the active AbstractNFFTs backend (e.g. NFFT.jl after using NFFT).

Required Arguments

  • shape::NTuple(Int): size of the image; e.g. (256, 256) for 2D imaging, or (256,256,128) for 3D imaging
  • tr::Matrix{T}: non-Cartesian k-space trajectory in units revolutions/voxel, i.e. tr[i] ∈ [-0.5, 0.5] ∀ i. The matrix has the size 2 x Nsamples for 2D imaging with a trajectory length Nsamples, and 3 x Nsamples for 3D imaging.

Keyword Arguments:

  • fftplan: plan for the final FFT of the kernel from image to k-space. Therefore, it has to have twice the size of the original image. default = plan_fft(zeros(Complex{T}, 2 .* shape); flags=FFTW.ESTIMATE). If this constructor is used many times, it is worth to precompute the plan with plan_fft(zeros(Complex{T}, 2 .* shape); flags=FFTW.MEASURE) and reuse it.
  • kwargs: passed on to plan_nfft, e.g. reltol for the accuracy of the kernel.

Examples

julia> using NFFT, NFFTTools

julia> Nx = 32;

julia> trj = Float32.(rand(2, 1000) .- 0.5);

julia> λ = calculateToeplitzKernel((Nx, Nx), trj);

julia> y = randn(ComplexF32, Nx, Nx);

julia> convolveToeplitzKernel!(y, λ);
source
NFFTTools.calculateToeplitzKernel! — Function
calculateToeplitzKernel!(f::AbstractArray{Complex{T}}, p::AbstractNFFTPlan, tr::AbstractMatrix{T}, fftplan)

Calculate the kernel for an implementation of the Gram matrix that utilizes its Toeplitz structure and writes it in-place in f, which has to be twice the size of the desired image matrix, as the Toeplitz trick requires an oversampling factor of 2 (cf. Wajer, F. T. A. W., and K. P. Pruessmann. "Major speedup of reconstruction for sensitivity encoding with arbitrary trajectories." Proc. Intl. Soc. Mag. Res. Med. 2001.). The type of the kernel f has to be Complex{T}, i.e. the complex of the k-space trajectory's type; for speed and memory efficiecy, call this function with Float32.(tr), and set the type of f accordingly.

Required Arguments

  • f::AbstractArray{Complex{T}}: array in which the kernel will be written.
  • p::AbstractNFFTPlan: NFFT plan for an array of twice the image size; its nodes are set to tr.
  • tr::Matrix{T}: non-Cartesian k-space trajectory in units revolutions/voxel, i.e. tr[i] ∈ [-0.5, 0.5] ∀ i. The matrix has the size 2 x Nsamples for 2D imaging with a trajectory length Nsamples, and 3 x Nsamples for 3D imaging.
  • fftplan: plan for the final FFT of the kernel from image to k-space. Therefore, it has to have twice the size of the original image. Calculate, e.g., with fftplan = plan_fft(zeros(Complex{T}, 2 .* shape); flags=FFTW.MEASURE), where shape is the size of the reconstructed image.

Examples

julia> using NFFT, NFFTTools, NFFTTools.FFTW

julia> Nx = 32;

julia> trj = Float32.(rand(2, 1000) .- 0.5);

julia> p = plan_nfft(trj, (2Nx, 2Nx));

julia> fftplan = plan_fft(zeros(ComplexF32, (2Nx,2Nx)); flags=FFTW.MEASURE);

julia> λ = Array{ComplexF32}(undef, 2Nx, 2Nx);

julia> calculateToeplitzKernel!(λ, p, trj, fftplan);
source
NFFTTools.convolveToeplitzKernel! — Function
convolveToeplitzKernel!(y::AbstractArray{T,N}, λ::AbstractArray{T,N}[, fftplan = plan_fft(λ; flags=FFTW.ESTIMATE), ifftplan = plan_ifft(λ; flags=FFTW.ESTIMATE), xOS1 = similar(λ), xOS2 = similar(λ)])

Convolves the image y with the Toeplitz kernel λ and overwrites y with the result. y is also returned for convenience. As this function is commonly applied many times, it is highly recommended to pre-allocate / pre-compute all optional arguments. By doing so, this entire function is non-allocating.

Required Arguments

  • y::Array{T,N}: Input image that will be overwritten with the result. y is a matrix (N=2) for 2D imaging and a 3D tensor (N=3) for 3D imaging. The type of the elements T must match the ones of λ.
  • λ::Array{T,N}: Toeplitz kernel, which has the same element type as y and twice its size due to the required oversampling (cf. calculateToeplitzKernel).

Optional, but highly recommended Arguments

  • fftplan: plan for the oversampled FFT, i.e. it has to have twice the size of the original image. Calculate, e.g., with fftplan = plan_fft(λ; flags=FFTW.MEASURE).
  • ifftplan: plan for the oversampled inverse FFT. Calculate, e.g., with ifftplan = plan_ifft(λ; flags=FFTW.MEASURE).
  • xOS1: pre-allocated array of the size of λ. Pre-allocate with xOS1 = similar(λ).
  • xOS2: pre-allocated array of the size of λ. Pre-allocate with xOS2 = similar(λ).

Examples

julia> using NFFT, NFFTTools, NFFTTools.FFTW

julia> Nx = 32;

julia> trj = Float32.(rand(2, 1000) .- 0.5);

julia> λ = calculateToeplitzKernel((Nx, Nx), trj);

julia> xOS1 = similar(λ);

julia> xOS2 = similar(λ);

julia> fftplan = plan_fft(xOS1; flags=FFTW.MEASURE);

julia> ifftplan = plan_ifft(xOS1; flags=FFTW.MEASURE);

julia> y = randn(ComplexF32, Nx, Nx);

julia> convolveToeplitzKernel!(y, λ, fftplan, ifftplan, xOS1, xOS2);
source

Direct transforms

NFFT.NDFTPlan — Type
NDFTPlan(k, N)
NDCTPlan(k, N)
NDSTPlan(k, N)
NNDFTPlan(k, y)

Direct evaluation of the NDFT, NDCT, NDST and NNDFT with the definitions of the fast plans (O(J·prod(N)) operations), as a reference for tests and small problems. Nodes are a D × J matrix or, for D = 1, a vector; the sums are computed in double precision.

source
NFFT.NDCTPlan — Type
NDFTPlan(k, N)
NDCTPlan(k, N)
NDSTPlan(k, N)
NNDFTPlan(k, y)

Direct evaluation of the NDFT, NDCT, NDST and NNDFT with the definitions of the fast plans (O(J·prod(N)) operations), as a reference for tests and small problems. Nodes are a D × J matrix or, for D = 1, a vector; the sums are computed in double precision.

source
NFFT.NDSTPlan — Type
NDFTPlan(k, N)
NDCTPlan(k, N)
NDSTPlan(k, N)
NNDFTPlan(k, y)

Direct evaluation of the NDFT, NDCT, NDST and NNDFT with the definitions of the fast plans (O(J·prod(N)) operations), as a reference for tests and small problems. Nodes are a D × J matrix or, for D = 1, a vector; the sums are computed in double precision.

source
NFFT.NNDFTPlan — Type
NDFTPlan(k, N)
NDCTPlan(k, N)
NDSTPlan(k, N)
NNDFTPlan(k, y)

Direct evaluation of the NDFT, NDCT, NDST and NNDFT with the definitions of the fast plans (O(J·prod(N)) operations), as a reference for tests and small problems. Nodes are a D × J matrix or, for D = 1, a vector; the sums are computed in double precision.

source

Abstract interface

AbstractNFFTs.AbstractFTPlan — Type
AbstractFTPlan{T,D,R}

Abstract type for any NFFT-like plan (NFFT, NNFFT, RNFFT, NFCT, NFST).

  • T is the element type (Float32/Float64)
  • D is the number of dimensions of the input array.
  • R is the number of dimensions of the output array.
source
AbstractNFFTs.AbstractComplexFTPlan — Type
AbstractComplexFTPlan{T,D,R}

Abstract type for either an NFFT plan or an NNFFT plan.

  • T is the element type (Float32/Float64)
  • D is the number of dimensions of the input array.
  • R is the number of dimensions of the output array.
source
AbstractNFFTs.AbstractRealFTPlan — Type
AbstractRealFTPlan{T,D,R}

Abstract type for either an NFCT plan or an NFST plan.

  • T is the element type (Float32/Float64)
  • D is the number of dimensions of the input array.
  • R is the number of dimensions of the output array.
source
AbstractNFFTs.AbstractNFFTPlan — Type
AbstractNFFTPlan{T,D,R}

Abstract type for an NFFT plan.

  • T is the element type (Float32/Float64)
  • D is the number of dimensions of the input array.
  • R is the number of dimensions of the output array.
source
AbstractNFFTs.AbstractNNFFTPlan — Type
AbstractNNFFTPlan{T,D,R}

Abstract type for an NNFFT plan.

  • T is the element type (Float32/Float64)
  • D is the number of dimensions of the input array.
  • R is the number of dimensions of the output array.
source
AbstractNFFTs.AbstractNFCTPlan — Type
AbstractNFCTPlan{T,D,R}

Abstract type for an NFCT plan.

  • T is the element type (Float32/Float64)
  • D is the number of dimensions of the input array.
  • R is the number of dimensions of the output array.
source
AbstractNFFTs.AbstractNFSTPlan — Type
AbstractNFSTPlan{T,D,R}

Abstract type for an NFST plan.

  • T is the element type (Float32/Float64)
  • D is the number of dimensions of the input array.
  • R is the number of dimensions of the output array.
source
AbstractNFFTs.AbstractRNFFTPlan — Type
AbstractRNFFTPlan{T,D,R}

Abstract type for an NFFT plan with real values at the nodes (the NFFT counterpart of FFTW's brfft/rfft): the direct transform maps the half n₁ ≥ 0 of the complex coefficients to real values at the nodes, the adjoint maps real values at the nodes to that half.

  • T is the real element type (Float32/Float64)
  • D is the number of dimensions of the input array.
  • R is the number of dimensions of the output array.
source
AbstractNFFTs.set_active_backend! — Function
set_active_backend!(back::Union{Missing, Module, AbstractNFFTBackend})

Set the default NFFT plan backend. A module back must implement back.backend().

source
AbstractNFFTs.default_reltol — Function
default_reltol(T)

Relative error requested from a plan with real element type T when reltol is not given: DEFAULT_RELTOL, or 100 * eps(T) where that is larger (Float32: 1.2e-5, Float16: 0.098).

source
AbstractNFFTs.GenericOptions — Type
GenericOptions

The options every implementation of the interface accepts, resolved from the keyword arguments of plan_nfft and friends by generic_options:

  • reltol: requested relative error (ℓ² norm)
  • dims: dimensions of the transform (a contiguous range); all other dimensions are batch dimensions that pass through unchanged
  • eltype: real element type of the data (Float32, Float64, …)
  • storage: array type of the data and the workspace (Array, a GPU array type, …)
  • nthreads: number of CPU threads
source
AbstractNFFTs.generic_options — Function
generic_options(k, N; reltol, dims, eltype, storage, nthreads) -> (GenericOptions, rest)

Resolve the generic keyword arguments of a plan constructor for nodes k and array size N, and return the remaining (implementation-specific) keyword arguments untouched.

source
AbstractNFFTs.check_options — Function
check_options(backend, kwargs, supported)

Throw an ArgumentError if kwargs contains a keyword that is not in supported. Every implementation must reject options it does not understand instead of ignoring them.

source

Index