FFTL.jl

Fastest Fourier Transform in Lübeck: a fast Fourier transform written in Julia. Complex, real and real-to-real transforms of any length and any number of dimensions, in Float32, Float64 and other floating-point types, on several threads with SIMD on the CPU, through KernelAbstractions on GPUs, and as a C library (libfftl) compiled from the same Julia code.

Experimental

FFTL.jl is under development and not registered yet. The interface can still change; the documented parts are the ones tested in CI.

How FFTL came about

FFTL was written by a coding agent under the guidance of a domain expert. Julia makes a library of this scope possible in one language: the compiler generates the codelets for the radix, element type and SIMD width in use, the same generator serves the GPU kernels, and juliac turns the package into a C library. A coding agent makes it possible to implement, test and measure the many details such a library needs. The library builds on decades of work on fast Fourier transforms, above all on FFTW; FFTW and FFTL describes that history.

FFTL is meant to be developed further by the Julia community, as one FFT that the ecosystem shares. Contribute says where help is most useful.

What FFTL covers

Transforms, number types and platforms, in Julia.

• Complex, real-input and all eleven real-to-real kinds (DCT-I to DCT-IV, DST-I to DST-IV, Hartley, halfcomplex), along any set of dimensions of any rank.

• Any length: smooth lengths through generated codelets, lengths with large prime factors through Bluestein's algorithm, no padding to powers of two.

• BigFloat and other floating-point types in their own precision, not converted to Float64.

• GPUs through KernelAbstractions.jl, with the same functions.

• Threads where the transform is large enough, and the four-step algorithm for one long line (see Threads).

A C library made from the Julia code. libfftl is the package compiled with juliac --trim, with FFTW3's C and Fortran interfaces, so programs written for FFTW3 compile and link against it without source changes. No transform is written in C, and a program that links the library needs no Julia installation. The run-time plans it is built from are public, so Julia programs that use them can be trimmed as well.

Entry points for special variants. Passes transform one dimension of a strided array and can skip zero inputs and unneeded outputs. Libraries that assemble their own transforms from such passes, such as NFFT.jl, use them.

The interface of the ecosystem. FFTL exports FFTW.jl's names with FFTW.jl's conventions and scalings, so using FFTL can take the place of using FFTW, and it is a backend of AbstractFFTs.jl's generic functions (see Coming from FFTW.jl).

Installation

using Pkg
Pkg.add(url = "https://github.com/JuliaMath/FFTL.jl")

Quick start

using FFTL, LinearAlgebra

x = randn(ComplexF64, 1000, 1000)
y = fft(x)                  # all dimensions, unnormalised
x2 = ifft(y)                # normalised inverse
x2 ≈ x

true

p = plan_fft(x)             # a plan holds the work buffers and tables
mul!(y, p, x)               # apply it, as often as you like
y ≈ fft(x)

true

r = randn(1000, 1000)
R = rfft(r)                 # half spectrum along dimension 1: 501 × 1000
irfft(R, 1000) ≈ r

true

C = dct(r)                  # orthonormal DCT-II; idct inverts it
idct(C) ≈ r

true

Where to go

If you want to	read
run your first transform	Your first transform
see the library used on real problems	Tutorials
move code from FFTW.jl	Coming from FFTW.jl
solve a specific task: plans, real data, threads, GPUs, C	How-to Guides
understand the mathematics and the algorithms	Explanation
look up a function, a kind, a limit	Reference

Design in one paragraph

A plan is a Julia object that carries the radix sequence, the twiddle tables and the work buffers for one size and one set of dimensions. Radix sequences are chosen by a fixed rule, and the codelets they run are generated for the radix, element type and SIMD width actually used. Long transforms run on several threads, and lengths with large prime factors go through Bluestein's algorithm. The details are in Algorithms.

Package status

Julia	1.10 and newer (CI: 1.10 and current)
License	MIT
Interface	AbstractFFTs.jl backend; plans are AbstractFFTs.Plans with mul!, *, \ and inv
Platforms	Linux and macOS (CI); Apple M1 Max is the development machine
GPU	experimental, via KernelAbstractions.jl
C library	experimental, juliac --trim, see libfftl

The complete matrix of transforms, number types and platforms is in Platforms and limits.