GitHub

TrigPolys

TrigPolys.jl is a package for fast manipulation of trigonometric polynomials.

A Hermitian trigonometric polynomial can be viewed as a polynomial $R(z) \in \mathbb{C}[z]$ [D17, (1.7)]:

\[R(z) = a_0 + \frac{1}{2} \sum_{k=1}^n a_k z^{-k} + a_k^* z^k\]

On the unit circle, this becomes [D17, (1.8)]:

\[R(\omega) = a_0 + \sum_{k=1}^n a_{c,k} \cos(k\omega) + a_{s,k} \sin(k\omega)\]

where $a_{c,k}$ is ac[k] and $a_{s,k}$ is as[k].

[D17] Dumitrescu, Bogdan. Positive trigonometric polynomials and signal processing applications. Vol. 103. Berlin: Springer, 2007.

The polynomial $p(x)$ can be represented either by $2n+1$ coefficients $a_k$ or by evaluations at $2n+1$ distinct points in the interval $[0,2\pi)$. Each representation is useful in different situations: the coefficient representation is useful for truncating or increasing the degree of a polynomial whereas the evaluation representation is useful for adding and multiplying polynomials.

This package provides the functions evaluate and interpolate to convert efficiently between these two representations. These operations are implemented via the Fast Fourier Transform (FFT) provided by the FFTW.jl library.

For example, multiplying two trigonometric polynomials is implemented with the following code:

function Base.:*(p1::TrigPoly, p2::TrigPoly)
    n = p1.n + p2.n
    interpolate(evaluate(pad_to(p1, n)) .* evaluate(pad_to(p2, n)))
end

Construction and Convertion

TrigPolys.TrigPoly — Type
struct TrigPoly{T<:AbstractFloat, VT<:AbstractVector{T}}
    a0::T    # Constant coefficient
    ac::VT   # cos coefficients
    as::VT   # sin coefficients
end

Represents a Hermitian trigonometric polynomial by its coefficients. The vectors ac and as should have the same length, that we call n in this docstring. This represent the following function

R(ω) = a0 + sum(ac[k] * cos(k * ω) + as[k] * sin(k * ω) for k in 1:n)

which is a polynomial in the variable x = cos(ω).

source
TrigPolys.TrigPoly — Method
TrigPoly(u::AbstractVector{T}) where {T<:AbstractFloat}

Constructs a TrigPoly given a vector of coefficients of length 2n+1. The first entry of u is a0, the next n entries are ac and the last n entries are as.

source
TrigPolys.a0 — Function
a0(p::TrigPoly)

Equivalent to p.a0, used for incorporation into automatic differentiation libraries.

source
TrigPolys.ac — Function
ac(p::TrigPoly)

Equivalent to p.ac, used for incorporation into automatic differentiation libraries.

source
TrigPolys.as — Function
as(p::TrigPoly)

Equivalent to p.as, used for incorporation into automatic differentiation libraries.

source
TrigPolys.n — Function
n(p::TrigPoly)

Equivalent to p.n. Returns the length of cosine/sine coefficients, which is length(p.ac) == length(p.as).

source
TrigPolys.degree — Function
degree(p::TrigPoly)

Returns the number of coefficients of p, which is 2*p.n + 1.

source

Methods

Base.:== — Method
Base.:(==)(p1::TrigPoly, p2::TrigPoly)

Returns true if the coefficients of p1 and p2 are all equal.

source
Base.:+ — Method
Base.:+(p1::TrigPoly, p2::TrigPoly)

Adds p1 to p2. The degree of the resulting polynomial will be the maximum degree of p1 and p2: (p1 + p2).n == max(p1.n, p2.n)

source
Base.:* — Method
Base.:*(p1::TrigPoly, p2::TrigPoly)

Multiplies p1 and p2. The degree of the resulting polynomial will be the sum of degrees of p1 and p2: (p1 * p2).n == p1.n + p2.n

source
Base.:/ — Method
Base.:/(p::TrigPoly, a::Number)

Divides p by a scalar.

source

Functions

TrigPolys.pad_to — Function
pad_to(p::TrigPoly{T,VT}, n::Integer) where {T<:AbstractFloat, VT<:AbstractVector{T}}

Increase the length of p.ac and p.as to n, padding with zeros if necessary. n cannot be smaller than p.n.

source
TrigPolys.pad_by — Function
pad_by(p::TrigPoly, n::Integer)

Increase the length of p.ac and p.as by n, padding with n zeros.

source
TrigPolys.basis — Function
basis(n, x)

Generate the basis for TrigPoly expressed as a vector, so that basis(p.n, x)'*vec(p) = p(x).

source
TrigPolys.evaluate — Function
evaluate(u::AbstractVector)

Evaluates an array representation of p::TrigPoly, returned by vec(p).

source
evaluate(p::TrigPoly)

Evaluates p on degree(p) uniformly-spaced points on the circle. See here for more details.

source
TrigPolys.evaluateT — Function
evaluateT(u::AbstractVector)

Adjoint of evaluate operator on an array representation of p::TrigPoly , returned by vec(p).

source
evaluateT(p::TrigPoly)

Adjoint of evaluate operator. Returns a vector.

source