Sequences

A Sequence is a structure representing a sequence in a prescribed VectorSpace. More precisely, a Sequence is comprised of the two fields space::VectorSpace and coefficients::AbstractVector with matching dimension and length.

julia> a = Sequence(Taylor(1), [1, 2])Sequence in Taylor(1) with coefficients Vector{Int64}:
 1
 2

The two fields space and coefficients are accessible via the respective functions of the same name.

julia> space(a)Taylor(1)
julia> coefficients(a)2-element Vector{Int64}:
 1
 2

For convenience, the methods zeros, ones, fill and fill! are available:

julia> s = Taylor(1)Taylor(1)
julia> zeros(s)Sequence in Taylor(1) with coefficients Vector{Float64}:
 0.0
 0.0
julia> ones(s)Sequence in Taylor(1) with coefficients Vector{Float64}:
 1.0
 1.0
julia> fill(2, s)Sequence in Taylor(1) with coefficients Vector{Int64}:
 2
 2
julia> fill!(zeros(s), 2)Sequence in Taylor(1) with coefficients Vector{Float64}:
 2.0
 2.0

The coefficients of a Sequence are indexed according to the indices of the space (as given by indices).

julia> a[0:1] # indices(space(a))2-element Vector{Int64}:
 1
 2

When the space of a Sequence is a CartesianSpace, its coefficients are given as the concatenation of the coefficients associated with each space. The function component extracts a Sequence composing the cartesian space.

julia> b = Sequence(ParameterSpace() × Taylor(1)^2, [1, 2, 3, 4, 5])Sequence in 𝕂 × Taylor(1)² with coefficients Vector{Int64}:
 1
 2
 3
 4
 5
julia> b[1:5] # indices(space(b))5-element Vector{Int64}:
 1
 2
 3
 4
 5
julia> component(b, 1) # extract the sequence associated with the space ParameterSpace()Sequence in 𝕂 with coefficients SubArray{Int64, 1, Vector{Int64}, Tuple{UnitRange{Int64}}, true}:
 1
julia> component(b, 2) # extract the sequence associated with the space Taylor(1)^2Sequence in Taylor(1)² with coefficients SubArray{Int64, 1, Vector{Int64}, Tuple{UnitRange{Int64}}, true}:
 2
 3
 4
 5
julia> component(component(b, 2), 1)Sequence in Taylor(1) with coefficients SubArray{Int64, 1, Vector{Int64}, Tuple{UnitRange{Int64}}, true}:
 2
 3
julia> component(component(b, 2), 2)Sequence in Taylor(1) with coefficients SubArray{Int64, 1, Vector{Int64}, Tuple{UnitRange{Int64}}, true}:
 4
 5

Similarly, the function eachcomponent returns a Generator whose iterates yield each Sequence composing the cartesian space.

Arithmetic

The addition and subtraction operations are implemented as the + and - functions respectively. Their bar counterparts add_bar (unicode alias +\bar<tab>) and sub_bar (unicode alias -\bar<tab>) give the result projected in the smallest compatible space between the operands.

julia> c = Sequence(Taylor(1), [0, 1])Sequence in Taylor(1) with coefficients Vector{Int64}:
 0
 1
julia> d = Sequence(Taylor(2), [1, 2, 1])Sequence in Taylor(2) with coefficients Vector{Int64}:
 1
 2
 1
julia> c + dSequence in Taylor(2) with coefficients Vector{Int64}:
 1
 3
 1
julia> c - dSequence in Taylor(2) with coefficients Vector{Int64}:
 -1
 -1
 -1
julia> add_bar(c, d) # project(c + d, Taylor(1))Sequence in Taylor(1) with coefficients Vector{Int64}:
 1
 3
julia> sub_bar(c, d) # project(c - d, Taylor(1))Sequence in Taylor(1) with coefficients Vector{Int64}:
 -1
 -1

The discrete convolution between sequences whose spaces are a SequenceSpace is implemented as the *(::Sequence{<:SequenceSpace}, ::Sequence{<:SequenceSpace}), mul!(::Sequence{<:SequenceSpace}, ::Sequence{<:SequenceSpace}, ::Sequence{<:SequenceSpace}, ::Number, ::Number) and ^(::Sequence{<:SequenceSpace}, ::Int) functions. Their bar counterparts mul_bar (unicode alias *\bar<tab>) and pow_bar (unicode alias ^\bar<tab>) give the result projected in the smallest compatible space between the operands; in general, mul_bar is not associative.

julia> c * dSequence in Taylor(3) with coefficients Vector{Int64}:
 0
 1
 2
 1
julia> c ^ 3Sequence in Taylor(3) with coefficients Vector{Int64}:
 0
 0
 0
 1
julia> mul_bar(c, d) # project(c * d, Taylor(1))Sequence in Taylor(1) with coefficients Vector{Int64}:
 0
 1
julia> pow_bar(c, 3) # project(c ^ 3, Taylor(1))Sequence in Taylor(1) with coefficients Vector{Int64}:
 0
 0

To improve performance, the FFT algorithm may be used to compute discrete convolutions via the Convolution Theorem. However, the performance gain is tempered with the loss of accuracy which may stop the decay of the coefficients.

julia> x = Sequence(Taylor(3), interval.([inv(10_000.0 ^ i) for i ∈ 0:3]))Sequence in Taylor(3) with coefficients Vector{Interval{Float64}}:
 Interval{Float64}(1.0, 1.0, com)
 Interval{Float64}(0.0001, 0.0001, com)
 Interval{Float64}(1.0e-8, 1.0e-8, com)
 Interval{Float64}(1.0e-12, 1.0e-12, com)
julia> x³ = x ^ 3Sequence in Taylor(9) with coefficients Vector{Interval{Float64}}:
 Interval{Float64}(1.0, 1.0, com)
 Interval{Float64}(0.0003, 0.00030000000000000003, com)
 Interval{Float64}(6.0e-8, 6.000000000000001e-8, com)
 Interval{Float64}(1.0e-11, 1.0000000000000003e-11, com)
 Interval{Float64}(1.1999999999999998e-15, 1.2000000000000006e-15, com)
 Interval{Float64}(1.1999999999999996e-19, 1.2000000000000004e-19, com)
 Interval{Float64}(9.999999999999997e-24, 1.0000000000000004e-23, com)
 Interval{Float64}(5.999999999999999e-28, 6.000000000000002e-28, com)
 Interval{Float64}(2.9999999999999995e-32, 3.0000000000000006e-32, com)
 Interval{Float64}(9.999999999999998e-37, 1.0000000000000001e-36, com)
julia> x³_fft = rifft!(zero(x³), fft(x, fft_size(space(x³))) .^ 3)Sequence in Taylor(9) with coefficients Vector{Interval{Float64}}:
 Interval{Float64}(0.9999999999999988, 1.0000000000000013, com)
 Interval{Float64}(0.00029999999999913776, 0.0003000000000009015, com)
 Interval{Float64}(5.999999926209087e-8, 6.000000089712177e-8, com)
 Interval{Float64}(9.999147625819226e-12, 1.000107365363463e-11, com)
 Interval{Float64}(5.767225544805468e-16, 1.9773326896552844e-15, com)
 Interval{Float64}(-9.430727111338557e-16, 9.818959977856102e-16, com)
 Interval{Float64}(-7.735442496893302e-16, 8.539669600072433e-16, com)
 Interval{Float64}(-8.537022549179915e-16, 8.856667395928615e-16, com)
 Interval{Float64}(-5.83108068801701e-16, 5.276202109764927e-16, com)
 Interval{Float64}(-9.314916420961008e-16, 8.080597681821184e-16, com)

To circumvent machine precision limitations, the banach_rounding! method enclose rigorously each term of the convolution beyond a prescribed order.^[1]

The rounding strategy for *(::Sequence{<:SequenceSpace}, ::Sequence{<:SequenceSpace}), mul!(::Sequence{<:SequenceSpace}, ::Sequence{<:SequenceSpace}, ::Sequence{<:SequenceSpace}, ::Number, ::Number), ^(::Sequence{<:SequenceSpace}, ::Int), mul_bar and pow_bar is integrated in the functions banach_rounding_mul, banach_rounding_mul!, banach_rounding_pow, banach_rounding_mul_bar and banach_rounding_pow_bar respectively.

julia> X = ℓ¹(GeometricWeight(interval(10_000.0)))ℓ¹(GeometricWeight(Interval{Float64}(10000.0, 10000.0, com)))
julia> banach_rounding!(x³_fft, norm(x, X) ^ 3, X, 5)Sequence in Taylor(9) with coefficients Vector{Interval{Float64}}:
 Interval{Float64}(0.9999999999999988, 1.0000000000000013, com)
 Interval{Float64}(0.00029999999999913776, 0.0003000000000009015, com)
 Interval{Float64}(5.999999926209087e-8, 6.000000089712177e-8, com)
 Interval{Float64}(9.999147625819226e-12, 1.000107365363463e-11, com)
 Interval{Float64}(5.767225544805468e-16, 1.9773326896552844e-15, com)
 Interval{Float64}(-6.400000000000007e-19, 6.400000000000007e-19, com)
 Interval{Float64}(-6.400000000000008e-23, 6.400000000000008e-23, com)
 Interval{Float64}(-6.4000000000000084e-27, 6.4000000000000084e-27, com)
 Interval{Float64}(-6.400000000000009e-31, 6.400000000000009e-31, com)
 Interval{Float64}(-6.40000000000001e-35, 6.40000000000001e-35, com)

API

Sequence{T<:VectorSpace,S<:AbstractVector}

julia> Sequence(Taylor(2), [1, 2, 1]) # 1 + 2x + x^2
Sequence in Taylor(2) with coefficients Vector{Int64}:
 1
 2
 1

julia> Sequence(Taylor(1) ⊗ Fourier(1, 1.0), [0.5, 0.5, 0.0, 0.0, 0.5, 0.5]) # (1 + x) cos(y)
Sequence in Taylor(1) ⊗ Fourier(1, 1.0) with coefficients Vector{Float64}:
 0.5
 0.5
 0.0
 0.0
 0.5
 0.5

julia> Sequence([1, 2, 3])
Sequence in 𝕂³ with coefficients Vector{Int64}:
 1
 2
 3

mul!(c::Sequence{<:SequenceSpace}, a::Sequence{<:SequenceSpace}, b::Sequence{<:SequenceSpace}, α::Number, β::Number)

banach_rounding_mul!(c::Sequence{<:SequenceSpace}, a::Sequence{<:SequenceSpace}, b::Sequence{<:SequenceSpace}, X::Ell1)

banach_rounding_mul(a::Sequence{<:SequenceSpace}, b::Sequence{<:SequenceSpace}, X::Ell1)

banach_rounding_pow(a::Sequence{<:SequenceSpace}, n::Int, X::Ell1)