DOCSEARCHbyAlgolia
Submit Docs

FINUFFT

repository·master·Indexed 19 days ago

https://github.com/flatironinstitute/finufft

A high-performance library for computing nonuniform Fast Fourier Transforms (NUFFT) in 1D, 2D, and 3D. It provides CPU-optimized (FINUFFT) and GPU-optimized (cuFINUFFT) implementations with interfaces for C, C++, Fortran, MATLAB/Octave, Python, and Julia. The library supports three standard types of transforms, including nonuniform to uniform (Type 1) and uniform to nonuniform (Type 2), and offers both a simple one-shot interface and a 4-step plan interface for repeated transforms.

Tokens
44.2K
Snippets
108
Records
169
Agent score
66%

What's inside FINUFFT

  1. Overview of FINUFFT and cuFINUFFT

    master

    FINUFFT is a lightweight CPU library designed to compute three standard types of nonuniform Fast Fourier Transforms (NUFFT) to a specified precision in one, two, or three dimensions. It is written in C++ and provides interfaces for C, Fortran, MATLAB/Octave, Python, and Julia.

    cuFINUFFT is the integrated GPU CUDA library for performing these same operations on GPU hardware.

    Key features include:

    • Support for 1D, 2D, and 3D nonuniform FFTs.
    • High-precision computation.
    • Multi-language interfaces.
    • GPU acceleration via cuFINUFFT.

  2. Overview of cufinufft Python wrappers

    master

    The cufinufft package provides a Python interface to the GPU CUDA implementation of the 1-, 2-, and 3-dimensional nonuniform fast Fourier transform (NUFFT) from the FINUFFT library. It supports two primary transform types:

    • Type 1: Nonuniform to uniform transforms.
    • Type 2: Uniform to nonuniform transforms.

    This package is designed for high-performance signal processing, imaging, and scientific computing using GPU acceleration.

  3. Identify packages and wrappers for (cu)FINUFFT

    master

    FINUFFT and its GPU counterpart cuFINUFFT are used as core libraries or plugins in various scientific computing packages. If you are looking for specific implementations or integrations, consider the following categories:

    Machine Learning Framework Wrappers

    • JAX: jax-finufft provides bindings that expose the library to the JAX XLA backend and implement differentiation rules.
    • PyTorch: pytorch-finufft provides a wrapper for PyTorch.
    • TensorFlow: tensorflow-nufft provides a wrapper for both CPU (via FINUFFT) and GPU (via cuFINUFFT).

    Language-Specific Wrappers

    • Julia: FINUFFT.jl is a pure Julia language wrapper. It is also wrapped by AbstractNFFTs.jl within NFFT.jl.
    • Python: Many packages depend on the Python interfaces, including mri_distortion_toolkit and Pyxu (via the pyxu_finufft plugin).

    Domain-Specific Applications

    • MRI Reconstruction: MRI-NUFFT provides a unified Python interface for MRI reconstruction.
    • Astronomy/Interferometry: SMILI (reconstruction), NWelch (power spectra), Multitaper.jl (exoplanet detection), nifty-ls (Lomb-Scargle periodogram), and fftvis (interferometric visibility simulator).
    • Cryo-EM: ASPIRE and EM-Align (volume alignment).

  4. Understand the FINUFFT repository structure

    master

    The FINUFFT repository is organized into several functional areas. When working with the source code, note the following key directories:

    Core Library

    • src/: Main C++ CPU source code.
    • src/cuda/: Main CUDA GPU source code.
    • include/: Public API header files.
    • lib/: Destination for dynamic (.so) libraries built via GNU make.
    • lib-static/: Destination for static (.a) libraries built via GNU make.

    Language Interfaces

    • fortran/: Fortran wrappers and example drivers.
    • matlab/: MATLAB/Octave CPU wrappers, tests, and examples.
    • python/: Python wrappers (supporting both CPU and GPU), examples, and tests.

    Examples and Documentation

    • examples/: Simple C/C++ example codes for calling the library.
    • tutorial/: Application demo codes in various languages.
    • docs/: Documentation source files.

    Testing and Performance

    • test/: Validation tests (C++/bash), including test/check_finufft.sh for pass/fail validation.
    • perftest/: Performance and developer tests, including GPU performance tests in perftest/cuda/.

  5. Compare FINUFFT with other NUFFT libraries

    master

    If you are evaluating whether to use FINUFFT for your project, consider the following alternatives based on your specific requirements:

    • NFFT3 (C++): A well-supported, multi-featured library using FFTW with a MATLAB MEX interface. It offers more general abilities (e.g., inverse NUFFTs) but is generally slower and more memory-intensive than FINUFFT.
    • DUCC (C++): A package containing NUFFT code developed for radio-astronomy. In certain regimes, it may be faster than FINUFFT due to its use of variable upsampling factors.
    • CMCL NUFFT (Fortran): A single-threaded library that is very easy to compile and includes a MATLAB MEX interface, but is significantly slower (up to 50x) than FINUFFT.
    • MIRT (MATLAB): A native MATLAB toolbox for image reconstruction. It is memory-intensive because it pre-stores kernel evaluations. It is fast for single-threaded implementations but slower than FINUFFT for tolerances smaller than $10^{-1}$.
    • PyNUFFT (Python): Supports both CPU and GPU operations.
    • NonuniformFFTs.jl (Julia): Native Julia code for Type 1 and Type 2 NUFFTs (CPU and GPU). It offers performance close to FINUFFT's CPU implementation and has shown competitive GPU performance.
    • NFFT.jl (Julia): A native Julia implementation for Type 1 and Type 2 NUFFTs.

  6. Understand FINUFFT performance parameters

    master

    CPU performance in FINUFFT is highly dependent on several configuration parameters. When reviewing benchmark results or tuning your own implementation, consider the following variables:

    • type: The transform type (1, 2, or 3).
    • prec: Precision level (f for float32, d for float64).
    • N1, N2, N3: The number of modes in each dimension (use 1 if a dimension is unused).
    • ntransf: The number of transforms being performed (used for testing many-vector cases).
    • M: The number of non-uniform points.
    • tol: The requested tolerance.
    • umsampfac: The upsampling factor.
    • threads: The number of threads used for multi-threaded execution.
    • FFT Implementation: The choice of FFT backend (e.g., fftw vs ducc).

    FFT Backend Note: In FFT-bound problems, ducc is generally expected to outperform fftw in 2D and 3D problems, whereas fftw is expected to be faster for 1D transforms.

  7. Precision handling in CUFINUFFT MATLAB interfaces

    master

    The simple and vectorized GPU MATLAB interfaces infer precision by checking the input arrays. All input arrays must match in precision.

    • Inference: Use underlyingType (available in R2020b+) to check the precision of a gpuArray instead of class.
    • Guru Interface: In the guru (plan) interface, precision is explicitly set using the cufinufft_plan option string opts.floatprec. Valid values are 'double' (default) or 'single'.

  8. Experimental GPU overloading of finufft commands

    master

    CUFINUFFT offers an experimental overloading of the standard finufft?d? MATLAB commands. If the first argument x is a gpuArray, the command is automatically redirected to the corresponding cufinufft?d? function.

    Important Setup Requirement: To enable this overloading, you must add the FINUFFT matlab directory to your MATLAB path before any gpuArray objects are created in the current session. This is necessary because the gpuArray class is "closed."

  9. Understand Fourier mode ordering (opts.modeord)

    master

    The ordering of frequency indices is controlled by opts.modeord. For a 1D transform with $N_1=8$:

    • opts.modeord = 0 (CMCL ordering): Indices are ordered -4, -3, -2, -1, 0, 1, 2, 3.
    • opts.modeord = 1 (FFT ordering): Indices are ordered 0, 1, 2, 3, -4, -3, -2, -1.

    These orderings are related by an fftshift. This setting applies to each dimension in multidimensional transforms.

  10. Precision handling in MATLAB/Octave

    master

    FINUFFT supports both single and double precision. The interface automatically selects the precision based on the input array class.

    • Automatic Selection: If all input arrays are double, the library uses double precision. If all input arrays are single, it uses single precision.
    • Requirement: All input arrays must match in precision.
    • Guru Interface: In the guru interface, precision is explicitly set via the finufft_plan options structure using the key o.floatprec, which can be set to 'double' (default) or 'single'.

  11. Data Layout for Multidimensional Arrays

    master

    FINUFFT does not use C/C++-style multidimensional arrays. Instead, multidimensional arrays must be passed as a pointer to a contiguous Fortran-style array.

    The dimensions are ordered by increasing speed (fastest to slowest) as follows:

    1. x (fastest)
    2. y (if present)
    3. z (if present)
    4. transform number (if ntr > 1)

  12. Use vectorized interfaces for multiple transforms

    master

    The NUFFT functions are vectorized. If you stack multiple inputs along the first dimension (row-major order), FINUFFT will process them simultaneously. This provides significant speedups for small inputs by avoiding multiple short calls.

    For a 2D Type 1 transform, if c has shape (K, M), the output f will have shape (K, N1, N2).

    import numpy as np
import finufft

K = 4
M = 100000
N1, N2 = 1000, 2000
x = 2 * np.pi * np.random.uniform(size=M)
y = 2 * np.pi * np.random.uniform(size=M)

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

# Calculate K transforms simultaneously
f = finufft.nufft2d1(x, y, c, (N1, N2))
# f.shape is (4, 1000, 2000)