FastTransforms.jl

FastTransforms.jl is a Julia wrapper for the FastTransforms C library. It is designed to allow users to work with orthogonal polynomials of very high degrees (into the millions).

Key capabilities include:

• Fast orthogonal polynomial transforms.
• Nonuniform Fast Fourier Transforms (NUFFT) of three different types.
• The Padua Transform.
• Specialized quadrature and special functions.

FastTransforms provides transforms for orthogonal polynomials (e.g., Chebyshev, Legendre) with degrees reaching into the millions.

Available transforms can be found in FastTransforms.Transforms or by inspecting FastTransforms.kind2string.(instances(FastTransforms.Transforms)).

For univariate transforms, you can use standard normalization or orthonormalization. For multivariate transforms, standard normalization is omitted to avoid floating-point issues.

FastTransforms.jl supports fast orthogonal polynomial transforms. Most transforms require creating separate forward and inverse plans.

Note on Inverses: In some specific instances, the inverse is calculated in the sense of least-squares; in these cases, only the forward transform is planned.

The Julia API unifies orthogonal polynomial transforms as linear operators using parametric composite types. The core types are FTPlan{T, N, K}, AdjointFTPlan, and TransposeFTPlan.

• T: The element type of the plan (e.g., Float64).
• N: The number of leading dimensions of the array on which the plan operates. For example, N=1 allows the plan to operate on vectors or matrices (column-by-column).
• K: An enumeration used to distinguish the specific orthogonal polynomials being used.

Example: FTPlan{Float64, 1, LEG2CHEB} represents the pre-computations required to convert 64-bit Legendre series to Chebyshev series (of the first kind).

To accelerate development by coupling Julia with the underlying C library source code, you can trigger a build from source by setting the FT_BUILD_FROM_SOURCE environment variable to "true" before building the package.

This allows you to experiment with new features by ccalling into the bleeding-edge C source code.

# Set the environment variable to trigger the build script
ENV["FT_BUILD_FROM_SOURCE"] = "true"

# In the Julia package manager, build the package
(@v1.5) pkg> build FastTransforms

When releasing a new version, you must provide the 256-bit SHA for the C library tarball. You can calculate this using the command line or within Julia using the SHA.jl package.

# Using the command line
curl https://codeload.github.com/MikaelSlevinsky/FastTransforms/tar.gz/v0.6.2 --output FastTransforms.tar.gz
shasum -a 256 FastTransforms.tar.gz
rm -f FastTransforms.tar.gz

# Using SHA.jl in Julia
using SHA

open("FastTransforms.tar.gz") do f
    bytes2hex(sha256(f))
end

You can install FastTransforms.jl using the Julia package manager. The package uses BinaryBuilder.jl to provide pre-compiled binaries for all supported Julia platforms.

# In the Julia REPL
pkg> add FastTransforms

using FastTransforms, LinearAlgebra

For numerical integration and quadrature, the package provides functions to generate nodes and weights for Clenshaw-Curtis and Fejér rules:

• clenshawcurtisnodes / clenshawcurtisweights
• fejernodes1 / fejerweights1
• fejernodes2 / fejerweights2

The package implements several types of Nonuniform Fast Fourier Transforms (NUFFT):

• nufft1: Uniform samples and noninteger frequencies.
• nufft2: Nonuniform samples and integer frequencies.
• nufft3 (or nufft): Nonuniform samples and noninteger frequencies.
• inufft1: Inverse of nufft1.
• inufft2: Inverse of nufft2.

For performance, use the plan_* versions of these functions to pre-compute the transform plan.

n = 10^4;
c = complex(rand(n));
ω = collect(0:n-1) + rand(n); # noninteger frequencies
x = (collect(0:n-1) + 3rand(n))/n; # nonuniform samples

# NUFFT1: Uniform samples, noninteger frequencies
p1 = plan_nufft1(ω, eps());
result1 = p1 * c;

# NUFFT2: Nonuniform samples, integer frequencies
p2 = plan_nufft2(x, eps());
result2 = p2 * c;

# NUFFT3: Nonuniform samples, noninteger frequencies
p3 = plan_nufft3(x, ω, eps());
result3 = p3 * c;

The Padua transform is used for computing bivariate Chebyshev coefficients by interpolating a bivariate function at the Padua points on [-1,1]^2.

• paduatransform(v): Computes the transform.
• ipaduatransform(v): Computes the inverse transform.

n = 200;
N = div((n+1)*(n+2), 2);
v = rand(N); # Length is the number of Padua points

# Transform and inverse
result = ipaduatransform(paduatransform(v))

The package includes methods for computing various moments used in quadrature and polynomial analysis, specifically for Chebyshev and Jacobi polynomials.

Chebyshev Moments:

• chebyshevmoments1
• chebyshevmoments2
• chebyshevlogmoments1
• chebyshevlogmoments2

Jacobi Moments:

• chebyshevjacobimoments1
• chebyshevjacobimoments2