flt — Fast Legendre Transform

This is a minimal Python package for fast discrete Legendre transforms (DLTs). The implementation uses a recursive version of the matrix relations by Alpert & Rokhlin (1991) to compute the DLT via a discrete cosine transform (DCT). [1] [2]

The package can be installed using pip:

pip install flt

Current functionality covers the absolutely minimal use case. Please open an issue on GitHub if you would like to see anything added.

Array backends

The flt functions support generic array backends via single dispatch. Currently available implementations are:

• NumPy

• JAX

Other implementations are easily added, even from third-party code, and will be picked up by the flt functions automatically.

Example

The main functionality of the flt module is the pair flt.dlt() and flt.idlt() of discrete Legendre transforms:

>>> import jax
>>> import flt
>>> key = jax.random.key(42)
>>> x = jax.random.uniform(key, shape=(100,))
>>> a = flt.dlt(x)
>>> y = flt.idlt(a)
>>> jax.numpy.allclose(x, y)
Array(True, dtype=bool)

References

[1]

Alpert, B. K., & Rokhlin, V., 1991, SIAM Journal on Scientific and Statistical Computing, 12, 158. doi:10.1137/0912009

[2]

Tessore N., Loureiro A., Joachimi B., von Wietersheim-Kramsta M., Jeffrey N., 2023, OJAp, 6, 11. doi:10.21105/astro.2302.01942

API

flt.dlt(x, closed=False)

Discrete Legendre transform.

Takes a function in \(\mathtt{n}\) points and returns its discrete Legendre transform coefficients from \(0\) to \(\mathtt{lmax} = \mathtt{n}-1\).

The function must be given at the points \(\cos(\theta)\) returned by flt.theta(). These can be distributed either over the open interval \(\theta \in (0, \pi)\), or over the closed interval \(\theta \in [0, \pi]\), in which case \(\theta_0 = 0\) and \(\theta_{n-1} = \pi\).

Parameters:

x(n,) array_like

Function values.

closedbool, optional

Compute DLT over open (closed=False) or closed (closed=True) interval.

Returns:

a(n,) array_like

Legendre coefficients \(0\) to \(\mathtt{lmax}\).

Warning

Not all array implementations support the closed transform.

See also

flt.idlt

the inverse operation

flt.theta

compute the angles at which the function is evaluated

Notes

The discrete Legendre transform takes a function \(f(\cos\theta)\) over the domain \(\theta \in [0, \pi]\) and returns the coefficients of the series

\[f(\cos\theta) = \sum_{l=0}^{l_{\max}} a_l \, P_l(\cos\theta) \;,\]

where \(P_l(\cos\theta)\) is a Legendre polynomial.

The computation is done in two steps:

First, the function is transformed to the coefficients of a discrete cosine transform (DCT) using a DCT-II for the open interval, or a DCT-I for the closed interval.

Second, the DCT coefficients are transformed to the DLT coefficients using a recursive version of the matrix relation given by [1].

References

[1]

Alpert, B. K., & Rokhlin, V. (1991). A fast algorithm for the evaluation of Legendre expansions. SIAM Journal on Scientific and Statistical Computing, 12(1), 158-179.

flt.idlt(a, closed=False)

Inverse discrete Legendre transform.

Takes the \(\mathtt{n} = \mathtt{lmax}+1\) coefficients of a DLT and returns the corresponding function in \(\mathtt{n}\) points.

The function will be given at the points \(\cos(\theta)\) returned by flt.theta(). These can be distributed either over the open interval \(\theta \in (0, \pi)\), or over the closed interval \(\theta \in [0, \pi]\), in which case \(\theta_0 = 0\) and \(\theta_{n-1} = \pi\).

Parameters:

a(n,) array_like

DLT coefficients from \(0\) to \(\mathtt{lmax}\).

Returns:

x(n,) array_like

Function values.

closedbool, optional

Compute DLT over open (closed=False) or closed (closed=True) interval.

Warning

Not all array implementations support the closed transform.

See also

flt.dlt

the forward operation

flt.theta

compute the angles at which the function is evaluated

Notes

The inverse discrete Legendre transform returns a function \(f(\cos\theta)\) over the domain \(\theta \in [0, \pi]\) given the coefficients of the series

\[f(\cos\theta) = \sum_{l=0}^{l_{\max}} a_l \, P_l(\cos\theta) \;,\]

where \(P_l(\cos\theta)\) is a Legendre polynomial.

The computation is done in two steps:

First, the DLT coefficients are transformed to the coefficients of a discrete cosine transform (DCT) using a recursive version of the matrix relation given by [1].

Second, the function values are computed using the inverse DCT-II for the open interval, or the inverse DCT-I for the closed interval.

References

[1]

Alpert, B. K., & Rokhlin, V. (1991). A fast algorithm for the evaluation of Legendre expansions. SIAM Journal on Scientific and Statistical Computing, 12(1), 158-179.

flt.theta(n, closed=False, *, xp=None)

Compute angles for DLT function values.

Returns \(n\) angles \(\theta_0, \ldots, \theta_{n-1}\) at which the function \(f(\cos\theta)\) is evaluated in flt.dlt() or flt.idlt().

The returned angles can be distributed either over the open interval \((0, \theta)\), or over the closed interval \([0, \pi]\), in which case \(\theta_0 = 0, \theta_{n-1} = \pi\).

Parameters:

nint

Number of nodes.

closedbool, optional

Compute angles over open (closed=False) or closed (closed=True) interval.

xparray namespace, optional

Return array from this array namespace. By default, numpy is used.

Returns:

thetaarray_like (n,)

Angles in radians.

flt.quadrature(n, closed=False, *, xp=None)

Compute a quadrature rule for n points.

Returns a set of weights to numerically integrate the function given at the n nodes \(\cos(\theta)\) returned by flt.theta().

The quadrature is exact for band-limited functions, and corresponds to the monopole of the FLT, so that flt.quadrature(n) @ x is equal to 2 * flt.dlt(x)[0] to numerical precision.

>>> n = 20
>>> x = np.random.rand(n)
>>> flt.quadrature(n) @ x
1.0377474091871635
>>> 2 * flt.dlt(x)[0]
1.0377474091871632

Parameters:

nint

Number of nodes.

closedbool, optional

Compute weights for the open (closed=False) or closed (closed=True) interval.

xparray namespace, optional

Return an array from this array namespace. By default, numpy is used.

Returns:

weightsarray_like (n,)

Weights of the quadrature rule.

Notes

Computes the weights \(w_1, \ldots, w_n\) of the quadrature rule

\[\int_{0}^{\pi} \! f(\cos\theta) \, d\theta \approx \sum_{i=1}^{n} w_i \, f(\cos\theta_i) \;,\]

where the points \(\theta_1, \ldots, \theta_n\) are those of the function flt.theta(). The integral is twice the monopole of the FLT,

\[\int_{0}^{\pi} \! f(\cos\theta) \, d\theta = \int_{0}^{\pi} \! f(\cos\theta) \, P_0(\cos\theta) \, d\theta = 2 a_0 \;.\]

For band-limited functions, the FLT computes the monopole exactly (to numerical precision), and the function returns the corresponding set of quadrature weights: for the open interval, this is Fejér’s first quadrature rule; for the closed interval, it is Clenshaw–Curtis quadrature.

flt.dct2dlt(b)

Convert DCT coefficients to DLT coefficients.

Parameters:

b(n,) array

DCT coefficients.

Returns:

a(n,) array

DLT coefficients.

flt.dlt2dct(a)

Convert DLT coefficients to DCT coefficients.

Parameters:

a(n,) array

DLT coefficients.

Returns:

b(n,) array

DCT coefficients.