StarAlgebras

AbstractBasis{T,I}

Implements

• in(x, basis) for basis elements
• Base.getindex(b::AbstractBasis{T,I}, idx::I)::T
• iteration protocol

AbstractBasis from the outside may look like a vector with arbitrary indices, however it may be possibly infinite (and therefore does not define its length).

When I<:Integer one may store coefficients w.r.t. the basis in an ordinary vector, however it's length has no relation to the size of the basis (which may still be infinite).

• ImplicitBasis is best suited for bases which can be enumerated but are in princle infinite in size (e.g. monomial basis for the polynomial ring). An example implementation of DiracBasis wrapping an iterator can be used for this purpose.
• ExplicitBasis can be used for fixed, finite size bases, in particular FixedBasis implements AbstractVector-type storage for elements. This can be used e.g. for representing polynomials as (sparse) vectors of coefficients w.r.t. a given FixedBasis.

abstract type AbstractCoefficients{K,V} end

Everything that implements a fixed set of methods can be used as SparseCoefficients without subtyping it.

"Read-only" coefficients

E.g. returned by calls to a MultiplicativeStructure need to implement

• Base.keys
• Base.values
• StarAlgebras.canonical
• StarAlgebras.star(b::AbstractBasis, ac)

For general types either all necessary arithmetic operations need to be implemented, or fallbacks using the framework of MutableArithmetics are provided based on random indexing. Additionally one needs to provide:

• Base.similar(ac, T::Type) with the same semantics as the one for vectors
• Base.getindex(ac, idx)
• Base.setindex!(ac, val, idx)
• MutableArithmetics.operate!(ms::UnsafeAddMul, ac, v::C, w::C) where C<:SA.AbstractCoefficients

struct AlgebraElement{T,A<:AbstractStarAlgebra,V} <: MA.AbstractMutable
    coeffs::V
    parent::A
end

Represent an element of the algebra parent with coefficients coeffs. The coefficients is a mapping from keys(coeffs) to values(coeffs). The basis element correponding to a key key can be obtained via parent[key].

The coefficients are always in canonicalized state, meaning the coefficients are sorted in increasing key order without duplicate keys. Don't call this constructor with a value of coeffs that is in canonical form. If unsure whether coeffs is in canonical form, call algebra_element instead of the AlgebraElement constructor.

The [UnsafeAddMul] and [UnsafeAdd] operations may break the canonicalized state of AlgebraElement, hence the Unsafe prefix in their name, the algebra element, say a, should be canonicalized with MA.operate!(canonical, a) after using these unsafe operations and before using other operations which assumes the canonicalized state.

AlgebraElement(qf::QuadraticForm, A::AbstractStarAlgebra)

Construct an algebra element in A representing quadratic form qf.

struct DiracBasis{T,S} <: ImplicitBasis{T,T}
    object::S
end

Given any iterable object over elements of type T, the basis corresponds to the list of elements of object. The object (its type S, respectively) should implement the methods:

Base.IteratorSize(::Type{S})
Base.eltype(::S) # Should return `T`
Base.iterate(::S)
Base.iterate(::S, state)
Base.in(::T, ::S)

Optionally, it may implement the following,

Base.isempty(::S)
Base.length(::S)

abstract type ExplicitBasis{T,I<:Integer} <: AbstractBasis{T,I} end

Explicit bases are bases of finite length for which the keys are integers.

FixedBasis(elts::AbstractVector)

Represents a linear basis which is fixed of length (given by elts). The elements of elts are assumed to be linearly independent and (as a set) invariant under star. Due to its finiteness, b::FixedBasis can be indexed like a vector (by positive integers) and therefore elements expressed in b can be represented by simple (sparse) Vectors.

Examples

julia> import StarAlgebras as SA;

julia> SA.star(s::String) = reverse(s) # identity is also fine

julia> b = SA.FixedBasis(["", "a", "b", "aa", "ab", "ba", "bb"]);

julia> b["a"]
1

julia> b["ab"]
4

julia> b[4]
"ab"

julia> b["abc"]
ERROR: KeyError: key "abc" not found
[...]

julia> A = SA.StarAlgebra(String, SA.DiracMStructure(b, *))
*-algebra of String

julia> c = A("a") + A("b")
1·"a" + 1·"b"

julia> c*A("a")
1·"aa" + 1·"ba"

julia> A("a")*c
1·"aa" + 1·"ab"

julia> c*c
1·"aa" + 1·"ab" + 1·"ba" + 1·"bb"

julia> SA.coeffs(c*c)
7-element SparseArrays.SparseVector{Int64, Int64} with 4 stored entries:
  [4]  =  1
  [5]  =  1
  [6]  =  1
  [7]  =  1

abstract type ImplicitBasis{T,I} <: AbstractBasis{T,I} end

Implicit bases are bases that contains the product of all its elements. This makes these bases particularly useful to work with AlgebraElements with supports that can not be reasonably bounded. Note that these bases may not explictly store its elements in memory as they may be potentially infinite. The elements of the basis are iterated in increasing order according to comparable(object(b)).

MTable{T, I} <: MultiplicativeStructure{T,I}

Multiplicative table, stored explicitly as an AbstractMatrix{I}.

mt(-i, j) == b[star(b[i])*b[j]]

mutable struct MappedBasis{T,I,S,F,U} <: ImplicitBasis{T,I}
    object::S
    map::F
    inverse_map::U
end

Given any iterable object over elements of type I, the basis corresponds to the list of elements map(i::I) where i belongs to object. The function inverse_map should be the inverse of map. That is, inverse_map(map(i)) should be i for all i in object. The object (its type S, respectively) should implement the methods:

Base.IteratorSize(::Type{S})
Base.eltype(::S) # Should return `I`
Base.iterate(::S)
Base.iterate(::S, state)
Base.in(::I, ::S)

Optionally, it may implement the following,

Base.isempty(::S)
Base.length(::S)

MultiplicativeStructure{T,I}

Structure representing multiplication w.r.t its basis.

Implements

• basis(ms::MultiplicativeStructure{T,I}) → AbstractBasis{T}
• (ms::MultiplicativeStructure{T,I})(i::V, j::V, ::Type{U}) where {V<:Union{T,I},U<:Union{T,I}} → Union{AbstractCoefficients, AbstractVector} the product of i and j represented by coefficients in basis(ms) for which the keys are of type U<:Union{T,I}.

The following shortcuts are provided:

• (ms::MultiplicativeStructure{T})(i::T, j::T) → ms(i, j, T)
• (ms::MultiplicativeStructure{T,I})(i::I, j::I) → ms(i, j, I)
• (ms::MultiplicativeStructure)[x] → basis(ms)[x]

When the product is not representable faithfully, ProductNotWellDefined exception should be thrown.

QuadraticForm(Q)
QuadraticForm{star}(Q)

A simple wrapper for representing a quadratic form.

QuadraticForm(Q) represents an honest quadratic form, however in the context of *-algebras a more canonical object is a sesquilinear form which can be constructed as QuadraticForm{star}(Q).

Both objects are defined by matrix coefficients with respect to their bases b, i.e. their values at i-th and j-th basis elements: star.(b)·Q·b = ∑ᵢⱼ Q[i,j]·star(b[i])·b[j].

Necessary methods:

• basis(Q) - a finite basis b of the quadratic form;
• Base.getindex(Q, i::T, j::T) - the value at i-th and j-th basis elements where T is the type of indicies of basis(Q);
• Base.eltype(Q) - the type of Q[i,j]·star(b[i])·b[j].

struct StarAlgebra{O,T,M<:MultiplicativeStructure{T}} <: AbstractStarAlgebra{O,T}
    object::O
    mstructure::M
end

Star algebra implementation with an object that should implement one(::O) and a MultiplicativeStructure mstructure.

struct SubBasis{T,I,K,B<:ImplicitBasis{T,K},V<:AbstractVector{K}} <:
    ExplicitBasis{T,I}
    parent_basis::B
    keys::V
    is_sorted::Bool
end

Represents a sub-basis of a given basis, where keys is a vector of keys representing the sub-basis elements, parent_basis is the parent basis from which the sub-basis is derived, and is_sorted indicates whether the keys are sorted.

operate_to!(res, ms::MultiplicativeStructure, A, B, α)

Compute α·A·B storing the result in res. Return res.

res is assumed to behave like AbstractCoefficients and not aliased with any other arguments. A and B are assumed to behave like AbstractCoefficients, while α will be treated as a scalar.

Canonicalization of the result happens only once at the end of the operation.

adjoint_coeffs(cfs, source, target)

Return A' * cfs where A is the linear map applied by coeffs.

algebra_element(coeffs, parent::AbstractStarAlgebra)

Same as AlgebraElement(coeffs, parent) but also canonicalizes coeffs.

canonical(ac::AbstractCoefficients)

Compute the canonical form of ac (e.g. grouping coefficients together, etc).

If ac can be brought to canonical form in-place one has to implement

• MA.mutability(::Type{typeof(ac)}, canonical, ::Vararg{Type}) = MA.IsMutable()
• MA.operate!(canonical, ac) that performs this canonicalization.

otherwise canonical(ac) needs to be implemented.

coeffs(cfs, source, target)

Translate coefficients cfs in source::AbstractBasis to basis target::AbstractBasis.

first_of(a, b)

Return the first argument. Useful as a combine function for merge_sorted to deduplicate without combining values.

key_index(b::SubBasis, key, default = nothing)

Given a key key of the basis parent(b), if the key is in SubBasis b then it returns the index of the key, otherwise, it returns default. This is a shortcut for get(b, parent(b)[key], default).

maybe_promote(a, parent, map)

Promote a given the promoted parent parent and the key map map. Call this function as follows:

maybe_promote(a, ::Nothing)

Just return a in case there is no promotion to do.

To be used as follows

function promote_bases_with_maps(a::..., b::...)
    _a, _b = promote_bases_with_maps(parent(a), parent(b))
    return maybe_promote(a, _a...), maybe_promote(b, _b...)
end

merge_bases(basis1::SubBasis, basis2::SubBasis)

Merge two sorted SubBasis with the same parent basis into a single SubBasis. See also merge_bases_with_maps.

merge_bases_with_maps(basis1::SubBasis, basis2::SubBasis)

Merge two sorted SubBasis with the same parent basis into a single SubBasis. Returns (merged_basis, I1, I2) where I1 and I2 are index vectors such that I1[i] is the index of the ith element of merged_basis in basis1 (or 0 if absent), and similarly for I2.

merge_sorted!(result, v1::AbstractVector, v2::AbstractVector; lt, combine, filter, rev=false)

In-place version of merge_sorted that writes the result into result. result must be large enough to hold the merged output (at most length(v1) + length(v2)). It is resized to the actual output length before returning. If rev=true, the comparison lt is reversed.

merge_sorted(v1::AbstractVector, v2::AbstractVector; lt, combine, filter, rev=false)

Merge two sorted vectors v1 and v2 into a single sorted vector. Elements are compared using lt (a less-than function). When two elements are equal (neither is less than the other), they are combined using combine(x1, x2). Elements for which filter returns false are dropped. If rev=true, the comparison lt is reversed.

merge_sorted(a::Tuple, b::Tuple; lt, combine, filter, rev=false)

Merge two sorted tuples, removing duplicates. Returns a tuple. If rev=true, the comparison lt is reversed.

multi_findsorted(x, y; lt = isless)

Given two sorted collections x and y, return a vector I of length length(x) where I[i] is the index of x[i] in y, or 0 if x[i] does not occur in y. Both x and y must be sorted according to lt.

nonzero_pairs(ac::AbstractCoefficients)

Return an iterator over pairs (k=>v) of keys and values stored in ac.

The iterator contains all pairs with v potentially non-zero.

promote_bases(a, b)

Same as promote_bases_with_maps but without the key maps.

promote_bases_with_map(a, b)

Return (new_a, map_a), (new_b, map_b) where new_a and new_b are the promoted version of a and b so that they now have the same basis. The function map_a (resp. map_b) maps the key of a (resp. b) to the corresponding key of new_a (resp. new_b).

The convention for implementing this interface for a type A with parent type B and function parent that obtains the parent type is as follows:

import StarAlgebras as SA

function SA.promote_with_map(a::A, b::B, map)
    # Promote other fields of `a` using `b` and `map`...
    return A(b, ...)
end

function SA.promote_bases_with_maps(a::A, b::A)
    _a, _b = SA.promote_bases_with_maps(parent(a), parent(b))
    return SA.maybe_promote(a, _a...), SA.maybe_promote(b, _b...)
end

function SA.promote_bases_with_maps(a::A, b::B)
    _a, _b = SA.promote_bases_with_maps(parent(a), b)
    return SA.maybe_promote(a, _a...), _b
end

promote_object(object, mstructure, map)

Promote the object field of a StarAlgebra to the new multiplicative structure mstructure and the key map map.

promote_with_map(a, parent, map)

Promote a given the promoted parent parent and the key map map. Implement this function but callmaybe_promote`.

sub_basis(basis::ImplicitBasis, keys::AbstractVector)

Return a SubBasis of basis but the subset of keys keys.

Note

Even though the constructor SubBasis(basis, keys) allows basis to be a ExplicitBasis, this function restricts it to be an ImplicitBasis in order to provide an interface that would help catch common mistakes.

sub_basis(basis::SubBasis, indices::Vector)

Return a SubBasis of the same parent but the subset of keys basis.keys[indices].