Introduce a thread-safe butterfly algorithm and multi-threaded fast spherical harmonic transforms

v0.3.2

add a few more stepthreads

Bound hierarchical matrices requirement

HierarchicalMatrices.jl introduces new support for thread safety. However, this breaks a (really minor) test in this package. Therefore, this version bounds the hierarchical matrices requirement, with a forthcoming version to fix the tests.

Experimental multithreading for spherical harmonic transforms

• add native Julia experimental multithreading for spherical harmonic transforms
• start triangular harmonic transforms
• drop support for Julia v0.5

Nonuniform fast Fourier transforms

The NUFFTs are implemented thanks to Alex Townsend:

• nufft1 assumes uniform samples and noninteger frequencies;
• nufft2 assumes nonuniform samples and integer frequencies;
• nufft3 ( = nufft) assumes nonuniform samples and noninteger frequencies;
• inufft1 inverts an nufft1; and,
• inufft2 inverts an nufft2.

Here is an example:

julia> using FastTransforms

julia> n = 10^4;

julia> c = complex(rand(n));

julia> ω = collect(0:n-1) + rand(n);

julia> nufft1(c, ω, eps());

julia> p1 = plan_nufft1(ω, eps());

julia> @time p1*c;
  0.002383 seconds (6 allocations: 156.484 KiB)

v0.2.1

• Add Appveyor CI to test Windows 32- and 64-bit support.

• Support butterfly factorization for any size of matrix (other than a power of two).

• Add synthesis and analysis for bivariate Fourier series on the sphere.

• Modify sph2fourier and fourier2sph to work on arrays with different band limits.

Support Spherical Harmonics

This major release now supports the fast and backward stable transform between spherical harmonic expansions and bivariate Fourier series. Convert between representations as simply as:

julia> Pkg.add("FastTransforms")

julia> using FastTransforms

julia> F = sphrandn(Float64, 1024, 1024);

julia> G = sph2fourier(F; sketch = :none);
Pre-computing...100%|███████████████████████████████████████████| Time: 0:00:04

julia> H = fourier2sph(G; sketch = :none);
Pre-computing...100%|███████████████████████████████████████████| Time: 0:00:04

julia> norm(F-H)
1.1612440912382192e-12