Linear combinations
Types
LinearCombinations.AbstractLinear — TypeL(xc::Pair...; is_filtered = false; kw...) where L <: AbstractLinear
L(itr; is_filtered = false; kw...) where L <: AbstractLinearAbstractLinear{T,R} is the supertype of all linear combinations with term type T and coefficient type R.
A constructor for a subtype L <: AbstractLinear constructs a linear combination of type L out of the given term-coefficient pairs of the form x => c where x is the term and c the coefficient, or out of the pairs provided by the iterator itr. It must be possible to convert all terms and coefficients to the chosen term type and coefficient type, respectively.
Neither the term type nor the coefficient type need to be concrete. (Of course, concrete types lead to better performance.) If the coefficient type and possibly also the term type are not specified, the constructor tries to determine them using promote_type (for coefficients) and promote_typejoin (for terms).
If two or more term-coefficient pairs are given with the same term, then the corresponding coefficients are added up. This is different from dictionaries, where any key-value pair overrides previous pairs with the same key. However, the implemented behavior is more useful for linear combinations.
For specialized applications, terms and coefficients can be processed with linear_filter and termcoeff before being stored in a linear combination. The keyword argument is_filtered controls whether linear_filter is called for each term.
By default, linear combinations are displayed in a human-readable form with a limited number of terms. Dedicated show methods display all terms of a linear combination or return an expression that Julia can parse as input. See the examples below.
See also Linear, DenseLinear, Linear1, linear_filter, LinearCombinations.termcoeff, Base.show
Examples
julia> Linear('x' => 1, 'y' => 2)
Linear{Char, Int64} with 2 terms:
'x'+2*'y'
julia> Linear(x => c for (c, x) in enumerate('u':'z'))
Linear{Char, Int64} with 6 terms:
3*'w'+2*'v'+4*'x'+'u'+5*'y'+6*'z'
julia> Linear{Char,Int}('x' => 1, 'y' => Int8(0), 'x' => 3.0)
Linear{Char, Int64} with 1 term:
4*'x'
julia> a = Linear('x' => BigInt(1), "yz" => 2.0)
Linear{Any, BigFloat} with 2 terms:
'x'+2.0*"yz"Iterating over a linear combination yields all non-zero term-coefficient pairs. Hence a linear combination can itself be used an argument to an AbstractLinear constructor.
julia> Linear{Union{Char,String}}(a) # same a as before
Linear{Union{Char, String}, BigFloat} with 2 terms:
'x'+2.0*"yz"Various forms to display a linear combination.
julia> a = Linear(x => 1 for x in 'a':'z')
Linear{Char, Int64} with 26 terms:
'n'+'f'+'w'+'d'+'e'+'o'+'h'+'j'+'i'+'k'+'r'+'s'+'t'+'q'+'y'+'a'+'c'+'p'+'m'+'z'±⋯
julia> show(stdout, MIME"text/plain"(), a) # all terms
Linear{Char, Int64} with 26 terms:
'n'+'f'+'w'+'d'+'e'+'o'+'h'+'j'+'i'+'k'+'r'+'s'+'t'+'q'+'y'+'a'+'c'+'p'+'m'+'z'+'g'+'v'+'l'+'u'+'x'+'b'
julia> b = Linear('a' => 1, 'y' => 2)
Linear{Char, Int64} with 2 terms:
'a'+2*'y'
julia> show(b) # can be parsed as input
Linear{Char, Int64}('a' => 1, 'y' => 2)LinearCombinations.Linear — TypeLinear{T,R} <: AbstractLinear{T,R}
Linear{T,R}(itr)Construct a linear combination of type Linear with term type T and coefficient type R out of the term-coefficient pairs provided by the iterator itr.
Linear combinations of this type are sparse in the sense that terms and (non-zero) coefficients are internally stored in a dictionary.
Other ways to use this constructor are discussed under AbstractLinear.
See also AbstractLinear, DenseLinear, Linear1.
LinearCombinations.DenseLinear — TypeDenseLinear{T,R} <: AbstractLinear{T,R}
DenseLinear{T,R}(itr; basis::Basis)Construct a linear combination of type DenseLinear with term type T and coefficient type R out of the term-coefficient pairs provided by the iterator itr.
Linear combinations of this type are internally stored as a Vector (or, more generally, an AbstractArray). The mandatory keyword argument basis is used to translate between terms and entries of the Vector (or Array). Operations involving two DenseLinear elements are much faster when the two bases are identical (in the sense of ===).
Other ways to use this constructor are discussed under AbstractLinear.
See also Basis, AbstractLinear, Linear, Linear1, basis, coordinates.
Examples
julia> azbasis = Basis('a':'z')
Basis('a':1:'z')
julia> a = DenseLinear('x' => 1, 'y' => 2; basis = azbasis)
DenseLinear{Char, Int64} with 2 terms:
'x'+2*'y'
julia> a + 'z'
DenseLinear{Char, Int64} with 3 terms:
'x'+2*'y'+'z'
julia> a + 'X'
ERROR: KeyError: key 'X' not found
[...]
julia> b = DenseLinear('x' => -1, 'z' => 3; basis = azbasis)
DenseLinear{Char, Int64} with 2 terms:
-'x'+3*'z'
julia> a + b
Linear{Char, Int64} with 2 terms:
2*'y'+3*'z'
julia> c = DenseLinear('a' => 5; basis = Basis('a':'c'))
DenseLinear{Char, Int64} with 1 term:
5*'a'
julia> add!(a, c)
DenseLinear{Char, Int64} with 3 terms:
5*'a'+'x'+2*'y'
julia> add!(c, a)
ERROR: KeyError: key 'x' not foundLinearCombinations.Linear1 — TypeLinear1{T,R} <: AbstractLinear{T,R}
Linear1{T,R}(itr)Construct a linear combination of type Linear1 with term type T and coefficient type R out of the term-coefficient pairs provided by the iterator itr.
Linear combinations of this type can hold at most one non-zero term-coefficient pair at any time. There are often situations where this is sufficient, and in these cases Linear1 is much more efficient than Linear or DenseLinear.
Other ways to use this constructor are discussed under AbstractLinear.
See also AbstractLinear, Linear, DenseLinear.
Examples
julia> a = Linear1('x' => 1)
Linear1{Char, Int64} with 1 term:
'x'
julia> add!(a, 'x')
Linear1{Char, Int64} with 1 term:
2*'x'
julia> addmul!(a, 'x', -2)
Linear1{Char, Int64} with 0 terms:
0
julia> a + 'y' # works because a is zero
Linear1{Char, Int64} with 1 term:
'y'
julia> a + 'y' + 'z'
ERROR: Linear1 cannot store linear combinations of two or more elements
[...]
julia> a = Linear1('x' => 1); b = Linear1('y' => 2); a+b
Linear{Char, Int64} with 2 terms:
'x'+2*'y'
julia> typeof(ans)
Linear{Char, Int64}Basic methods
LinearCombinations.termtype — Functiontermtype(::Type{L}) where L <: AbstractLinear{T,R} = T
termtype(a::L) where L <: AbstractLinear{T,R} = TReturn the type of the terms (basis elements) in a linear combination.
See also coefftype.
LinearCombinations.coefftype — Functioncoefftype(::Type{L}) where L <: AbstractLinear{T,R} = R
coefftype(a::L) where L <: AbstractLinear{T,R} = RReturn the type of the coefficients in a linear combination.
See also termtype.
Base.in — Methodx in a::AbstractLinear -> BoolReturn true if the term x appears in the linear combination a with a non-zero coefficient, and false otherwise.
Base.length — Methodlength(a::AbstractLinear) -> IntReturn the number of non-zero terms in a.
Base.iterate — Methoditerate(a::AbstractLinear [, state])Iterating over a linear combination yields all non-zero term-coefficient pairs.
Examples
julia> a = Linear('x' => 1, 'y' => 2, 'z' => 0)
Linear{Char, Int64} with 2 terms:
'x'+2*'y'
julia> collect(a)
2-element Vector{Pair{Char, Int64}}:
'x' => 1
'y' => 2
julia> Linear(x => c^2 for (x, c) in a)
Linear{Char, Int64} with 2 terms:
'x'+4*'y'LinearCombinations.coeffs — Functioncoeffs(a::AbstractLinear)Return an iterator over the non-zero coefficients appearing in a.
LinearCombinations.terms — Functionterms(a::AbstractLinear)Return an iterator over the terms appearing in a (with a non-zero coefficient).
Base.zero — Functionzero(::Type{L}; kw...) where L <: AbstractLinear -> L
zero(a::L) where L <: AbstractLinear -> LReturn a zero linear combination of type L. If zero is called with a type L <: AbstractLinear as argument, then keyword arguments may be accepted or required.
See also zero!.
LinearCombinations.zero! — FunctionBase.copy — Functioncopy(a::L) where L <: AbstractLinear -> LReturn a copy of a.
Base.copyto! — Functioncopyto!(a::AbstractLinear, b::AbstractLinear, c = 1) -> a
copyto!(a::AbstractLinear, x, c = 1) -> aSet a equal to the c-fold multiple of the linear combination b or of the term x. If the scalar c is omitted, it is taken to be 1.
Base.sizehint! — Functionsizehint!(a::AbstractLinear, n::Integer) -> aTry to make room for in total n non-zero term-coefficient pairs in the linear combination a.
This can speed up computations. At present, sizehint! has an effect for elements of type Linear (which internally use a dictionary) and is ignored for all other subtypes of AbstractLinear.
See also Linear, LinearCombinations.has_sizehint, Base.sizehint!(d::AbstractDict).
Base.convert — Functionconvert(::Type{L}, a::AbstractLinear; kw...) where L <: AbstractLinear -> L
convert(::Type{L}, x; kw...) where L <: AbstractLinear -> LConvert the linear combination a or the term x to a linear combination of type L. Keyword arguments are passed to the constructor for L.
Examples
julia> a = Linear{AbstractChar,Int}('x' => 2)
Linear{AbstractChar, Int64} with 1 term:
2*'x'
julia> b = convert(Linear{Char,Float64}, a)
Linear{Char, Float64} with 1 term:
2.0*'x'
julia> convert(Linear{Char,Int}, 'x') == Linear('x' => 1)
true
julia> convert(DenseLinear, a; basis = Basis('a':'z'))
DenseLinear{AbstractChar, Int64} with 1 term:
2*'x'Additional functions for DenseLinear
LinearCombinations.basis — FunctionLinearCombinations.coordinates — Functioncoordinates(a::DenseLinear{T,R}) -> AbstractArray{R}Return the coordinates of a with respect to the basis used for it. The coordinate array (usually a vector) has the same axes as the basis. Modifying this array will also modify a.
See also basis.
Example
julia> b = Basis('x':'z')
Basis('x':1:'z')
julia> a = DenseLinear('x' => 1, 'z' => 2; basis = b)
DenseLinear{Char, Int64} with 2 terms:
'x'+2*'z'
julia> v = coordinates(a)
3-element Vector{Int64}:
1
0
2
julia> a == Linear(x => c for (x, c) in zip(basis(a), v))
true
julia> v[2] = -1; a
DenseLinear{Char, Int64} with 3 terms:
'x'-'y'+2*'z'Arithmetic
LinearCombinations.add! — Functionadd!(a::AbstractLinear, b::AbstractLinear) -> a
add!(a::AbstractLinear, x) -> aAdd the linear combination b or the term x to a. This function modifies a.
LinearCombinations.sub! — Functionsub!(a::AbstractLinear, b::AbstractLinear) -> a
sub!(a::AbstractLinear, x) -> aSubtract the linear combination b or the term x from a. This function modifies a.
LinearCombinations.mul! — Functionmul!(a::AbstractLinear, c) -> aMultiply a by the scalar c. This functions modifies a.
See also addmul!.
LinearCombinations.addmul! — Functionaddmul!(a::AbstractLinear, b::AbstractLinear, c) -> a
addmul!(a::AbstractLinear, x, c) -> aAdd the c-fold multiple of the linear combination b or of the term x to a, where c is a scalar. This function modifies a.
LinearCombinations.addmul — Functionaddmul(a::AbstractLinear, b::AbstractLinear, c)
addmul(a::AbstractLinear, x, c)Add the c-fold multiple of the linear combination b or of the term x to a, where c is a scalar.
See also addmul!.
LinearCombinations.deg — Methoddeg(a::AbstractLinear)Return deg(x) where x is the first term appearing in a (as determined by first(a)).
The linear combination a must not be zero. If a is homogeneous, then deg(a) is the common degree of all terms in it.
Calling linear combinations
Calling objects is extended linearly. Here is an example:
julia> struct P{T} y::T end
julia> Base.hash(p::P, h::UInt) = hash(p.y, hash(P, h)); # `Linear` uses hashing
julia> @linear p::P; (p::P)(x) = x * p.y
julia> p, q = P('p'), P('q')
(P{Char}('p'), P{Char}('q'))
julia> p('x')
"xp"
julia> a = Linear('x' => 1, 'y' => 2)
Linear{Char, Int64} with 2 terms:
'x'+2*'y'
julia> p(a)
Linear{String, Int64} with 2 terms:
2*"yp"+"xp"
julia> u = Linear(p => -1, q => 3)
Linear{P{Char}, Int64} with 2 terms:
-P{Char}('p')+3*P{Char}('q')
julia> u('x')
Linear{String, Int64} with 2 terms:
3*"xq"-"xp"
julia> u(a)
Linear{String, Int64} with 4 terms:
3*"xq"-2*"yp"+6*"yq"-"xp"Broadcasting
Broadcasting is supported for AbstractLinear types. Broadcasted versions of +, -, *, = are converted to addmul!, mul! and copyto! as much as possible to avoid (or at least minimize) allocations. For example, for linear combinations a, b, c and d, the statement
a .= b .+ 2 .* (c .- 3 .* d)is translated to
copyto!(a, b)
addmul!(a, c, 2)
addmul!(a, d, 2*(-3))and the statement
a .+= b .+ 2 .* (c .- 3 .* d)to
addmul!(a, b)
addmul!(a, c, 2)
addmul!(a, d, 2*(-3))Broadcasted .* is always interpreted as scalar multiplication, with the scalar as the first argument. The only exception is a statement of the form a .*= c (that is, a .= a .* c) where the scalar is the second argument.
By default, only elements of types AbstractLinear and Number participate in broadcasting. To allow other scalar or term types, one has to use the macro @linear_broadcastable.
julia> @linear_broadcastable Char
julia> a, b = Linear('x' => 1), Linear('y' => 2)
(Linear{Char, Int64}('x' => 1), Linear{Char, Int64}('y' => 2))
julia> a .+= b .+ 2 .* 'z'
Linear{Char, Int64} with 3 terms:
'x'+2*'y'+2*'z'
julia> a
Linear{Char, Int64} with 3 terms:
'x'+2*'y'+2*'z'LinearCombinations.@linear_broadcastable — Macro@linear_broadcastable TAdd the type T to the types that participate in broadcasting for linear combinations. By default, only the types AbstractLinear and Number are available. (A few others happen to work as well, for example AbstractChar.)
See also LinearCombinations.LinearStyle.
AbstractLinear interface
LinearCombinations.getcoeff — FunctionLinearCombinations.getcoeff(a::AbstractLinear{T,R}, x) where {T,R} -> RReturn the coefficient of x in the linear combination a. This is zero(R) if x does not appear in a.
This function is part of the AbstractLinear interface. When it is called, the term x has already been transformed via termcoeff, and linear_filter(x) is true.
See also LinearCombinations.setcoeff!, linear_filter, LinearCombinations.termcoeff.
LinearCombinations.setcoeff! — FunctionLinearCombinations.setcoeff!(a::AbstractLinear{T,R}, c, x) where {T,R} -> cSet the coefficient of x in the linear combination a equal to c and return c.
This function is part of the AbstractLinear interface. When it is called, both x and c have already been transformed via termcoeff, and linear_filter(x) is true.
See also LinearCombinations.getcoeff, linear_filter, LinearCombinations.termcoeff.
LinearCombinations.modifycoeff! — FunctionLinearCombinations.modifycoeff!(op, a::AbstractLinear, x, c) -> aReplace the coefficient of x in a by op(getcoeff(a, x), c) and return a. Here op is either + or -.
This function is called after termcoeff and linear_filter.
See also linear_filter, LinearCombinations.termcoeff, LinearCombinations.modifylinear!.
LinearCombinations.modifylinear! — FunctionLinearCombinations.modifylinear!(op, a::AbstractLinear, b::AbstractLinear, c = missing) -> aIf op is +, add c*b to a, or just b if c is missing. If op is -, subtract b or c*b from a. Store the new value in a and return it.
See also LinearCombinations.modifycoeff!.