# FastTransforms.jl Documentation

## Introduction

FastTransforms.jl allows the user to conveniently work with orthogonal polynomials with degrees well into the millions.

This package provides a Julia wrapper for the C library of the same name. Additionally, all three types of nonuniform fast Fourier transforms available, as well as the Padua transform.

## Fast orthogonal polynomial transforms

For this documentation, please see the documentation for FastTransforms. Most transforms have separate forward and inverse plans. In some instances, however, the inverse is in the sense of least-squares, and therefore only the forward transform is planned.

## Nonuniform fast Fourier transforms

FastTransforms.nufft1Function

Computes a nonuniform fast Fourier transform of type I:

$f_j = \sum_{k=0}^{N-1} c_k e^{-2\pi{\rm i} \frac{j}{N} \omega_k},\quad{\rm for}\quad 0 \le j \le N-1.$
source

Computes a 2D nonuniform fast Fourier transform of type I-I:

$F_{i,j} = \sum_{k=0}^{M-1}\sum_{\ell=0}^{N-1} C_{k,\ell} e^{-2\pi{\rm i} (\frac{i}{M} \omega_k + \frac{j}{N} \pi_{\ell})},\quad{\rm for}\quad 0 \le i \le M-1,\quad 0 \le j \le N-1.$
source
FastTransforms.nufft2Function

Computes a nonuniform fast Fourier transform of type II:

$f_j = \sum_{k=0}^{N-1} c_k e^{-2\pi{\rm i} x_j k},\quad{\rm for}\quad 0 \le j \le N-1.$
source

Computes a 2D nonuniform fast Fourier transform of type II-II:

$F_{i,j} = \sum_{k=0}^{M-1}\sum_{\ell=0}^{N-1} C_{k,\ell} e^{-2\pi{\rm i} (x_i k + y_j \ell)},\quad{\rm for}\quad 0 \le i \le M-1,\quad 0 \le j \le N-1.$
source
FastTransforms.nufft3Function

Computes a nonuniform fast Fourier transform of type III:

$f_j = \sum_{k=0}^{N-1} c_k e^{-2\pi{\rm i} x_j \omega_k},\quad{\rm for}\quad 0 \le j \le N-1.$
source

## Other Exported Methods

FastTransforms.gauntFunction

Calculates the Gaunt coefficients, defined by:

$a(m,n,\mu,\nu,q) = \frac{2(n+\nu-2q)+1}{2} \frac{(n+\nu-2q-m-\mu)!}{(n+\nu-2q+m+\mu)!} \int_{-1}^{+1} P_n^m(x) P_\nu^\mu(x) P_{n+\nu-2q}^{m+\mu}(x) {\rm\,d}x.$

or defined by:

$P_n^m(x) P_\nu^\mu(x) = \sum_{q=0}^{q_{\rm max}} a(m,n,\mu,\nu,q) P_{n+\nu-2q}^{m+\mu}(x)$

This is a Julia implementation of the stable recurrence described in:

Y.-l. Xu, Fast evaluation of Gaunt coefficients: recursive approach, J. Comp. Appl. Math., 85:53–65, 1997.

source

Calculates the Gaunt coefficients in 64-bit floating-point arithmetic.

source
FastTransforms.sphevaluateFunction

Pointwise evaluation of real orthonormal spherical harmonic:

$Y_\ell^m(\theta,\varphi) = (-1)^{|m|}\sqrt{(\ell+\frac{1}{2})\frac{(\ell-|m|)!}{(\ell+|m|)!}} P_\ell^{|m|}(\cos\theta) \sqrt{\frac{2-\delta_{m,0}}{2\pi}} \left\{\begin{array}{ccc} \cos m\varphi & {\rm for} & m \ge 0,\\ \sin(-m\varphi) & {\rm for} & m < 0.\end{array}\right.$
source

## Internal Methods

### Miscellaneous Special Functions

FastTransforms.δFunction

The Kronecker $\delta$ function:

$\delta_{k,j} = \left\{\begin{array}{ccc} 1 & {\rm for} & k = j,\\ 0 & {\rm for} & k \ne j.\end{array}\right.$
source
FastTransforms.ΛFunction

The Lambda function $\Lambda(z) = \frac{\Gamma(z+\frac{1}{2})}{\Gamma(z+1)}$ for the ratio of gamma functions.

source

For 64-bit floating-point arithmetic, the Lambda function uses the asymptotic series for $\tau$ in Appendix B of

I. Bogaert and B. Michiels and J. Fostier, 𝒪(1) computation of Legendre polynomials and Gauss–Legendre nodes and weights for parallel computing, SIAM J. Sci. Comput., 34:C83–C101, 2012.

source

The Lambda function $\Lambda(z,λ₁,λ₂) = \frac{\Gamma(z+\lambda_1)}{Γ(z+\lambda_2)}$ for the ratio of gamma functions.

source