Linear and multilinear functions

@linear f

This macro defines a linear extension of the function (or callable object) f. More specifically, it defines a new method f(a::AbstractLinear{T,R}; kw...) where {T,R} that returns the linear combination obtained by summing up c*f(x) for all term-coefficient pairs x => c appearing in a.

The new method recognizes the following keyword arguments:

• coefftype: This optional keyword argument specifies the coefficient type of the linear combination returned by f(a) if the keyword argument addto is not present. If coefftype is also not specified and f(x::T) is a term (as opposed to a linear combination), then coefftype is set to R. If f(x::T) <: AbstractLinear, say with coefficient type S, then promote_type(R, S) is chosen as the new coefficient type. If the addto keyword is present, then coefftype is ignored.

  Because of the way Julia handles keyword arguments, the form f(a; coefftype = Int) is not type-stable. Type stability can be achieved by saying f(a; coefftype = Val(Int)).

• addto::AbstractLinear: If given, the sum of all terms c*f(x) is added to addto, and the result is returned. This avoids allocating a new linear combination each time f is called with an AbstractLinear argument. The default value for addto is Linear{U,coefftype}. Here U is the return type of f(x::T) if this return type is not a subtype of AbstractLinear and the term type of the return values otherwise.

• coeff: This optional keyword argument allows to efficiently compute scalar multiples of f(a). More precisely, f(a; coeff = c) returns c*f(a), and f(a; addto = b, coeff = c) adds c*f(a) to b and returns this new value.

• sizehint::Bool = true: The new method for f may call sizehint! for addto to pre-allocate room for the new terms. This keyword argument permits to turn pre-allocation off.

All other keyword arguments are passed on to f(x). With the macro @linear_kw one can make f(a) pass the special keyword arguments listed above on to f(x), too.

See also @multilinear, sizehint!, @linear_kw, keeps_filtered.

Examples

Linear extension of a function returning a term

julia> f(x) = uppercase(x); @linear f
f (generic function with 2 methods)

julia> a = Linear('x' => 1, 'y' => 2)
Linear{Char, Int64} with 2 terms:
'x'+2*'y'

julia> f(a)
Linear{Char, Int64} with 2 terms:
2*'Y'+'X'

julia> f(a; coefftype = Float64)
Linear{Char, Float64} with 2 terms:
2.0*'Y'+'X'

julia> b = Linear('z' => 3); f(a; addto = b, coeff = -1); b
Linear{Char, Int64} with 3 terms:
-2*'Y'-'X'+3*'z'

Linear extension of a function returning a linear combination

julia> g(x) = Linear(x*x => 1.0, string(x) => -1.0); @linear g
g (generic function with 2 methods)

julia> g("x"), g("")
(Linear{String, Float64}("xx" => 1.0, "x" => -1.0), Linear{String, Float64}())

julia> g(a)   # same a as before
Linear{String, Float64} with 4 terms:
"xx"-"x"+2.0*"yy"-2.0*"y"

julia> g(a; coefftype = Val(Int), coeff = 3.0)
Linear{String, Int64} with 4 terms:
3*"xx"-3*"x"+6*"yy"-6*"y"

Linear extension of a callable object

julia> struct P y::String end

julia> (p::P)(x) = p.y*x*p.y; @linear p::P

julia> p = P("w"); p(a)   # same a as before
Linear{String, Int64} with 2 terms:
"wxw"+2*"wyw"

LinearExtension{F}

This type is the linear extension of the given type F.

Examples

julia> const g = LinearExtension(uppercase)
LinearExtension(uppercase)

julia> g('x')
'X': ASCII/Unicode U+0058 (category Lu: Letter, uppercase)

julia> a = Linear('x' => 1, 'y' => 2); g(a; coeff = 3)
Linear{Char, Int64} with 2 terms:
6*'Y'+3*'X'

matrixrepr(f, b1::AbstractBasis, b0::AbstractBasis, ::Type{R})) where R

Return a matrix representing the linear map f with respect to the bases b0 (source) and b1 (target). Coefficients have the type R.

See also matrixrepr!.

Example

julia> @linear f; f(x) = Linear(uppercase(x) => 1, 'A' => 1)
f (generic function with 2 methods)

julia> matrixrepr(f, Basis('A':'C'), Basis('a':'c'), Int)
3×3 Matrix{Int64}:
 2  1  1
 0  1  0
 0  0  1

matrixrepr!(f, a::AbstractMatrix, b1::AbstractBasis, b0::AbstractBasis; iszero::Bool = false) -> a

Compute a matrix representing the linear map f with with respect to the bases b0 (source) and b1 (target). Store the result in a and return a. If the keyword argument iszero is true, then the matrix a is not first initialized with zeros.

See also matrixrepr.

diff(x)

The differential of x.

The module LinearCombinations only defines the linear extension of diff, but no methods for terms. The only exception is diff for tensors.

See also diff(t::AbstractTensor).

coprod(x)

The coproduct (or comultiplication) of x, which is assumed to be an element of a coalgebra.

The module LinearCombinations only defines the linear extension of coprod, but no methods for terms, except for tensors.

See also coprod(t::AbstractTensor).

@multilinear f
@multilinear f f0

This macro defines a multilinear extension of the function f (or f0). This is analogous to @linear f. The new methods accepts both terms and linear combinations as arguments. It linearly expands all arguments that are linear combinations and then calls f for each combination of terms. If f0 is specified, then f0 is called instead to evaluate terms.

The new method always returns a linear combination (of type Linear unless this is overriden by the addto keyword). The term type is inferred from the return type of f (or f0) with terms as arguments. The coefficient type is computed by promoting the coefficient types of all AbstractLinear arguments. In case f (or f0) returns a linear combination for term arguments, that coefficient type is also taken into account.

In order to catch all possible combinations of terms and linear combinations, @multilinear f and @multilinear f f0 define a single new method f(x...; kw...) that matches all argument types. (This is different from @linear.) Hence, if f0 is not given, then the methods for f that evaluate terms must have a non-generic signature. If instead the signature also is f(x::Any...), then this method is overwritten, resulting in an error when f is called.

The new method defined by @multilinear accepts all keyword arguments discussed for @linear. Unknown keyword arguments are passed on to the call for term evaluation. The macro @linear_kw works as for linear functions.

If the two-argument version of @multilinear is used, then typically there is no other method for f. Hence f returns a linear combination for all arguments in this case. If all arguments are terms and also f0 returns a term, then the coefficient type is LinearCombinations.DefaultCoefftype. For the one-argument version there must be at least one other method as discussed above. So f may not return a linear combination for all arguments.

See also @linear, @linear_kw, LinearCombinations.DefaultCoefftype.

Examples

Bilinear extension of a function returning a term

julia> f(x::Char, y::String) = x*y; @multilinear f

julia> a, b = Linear('x' => 1, 'y' => 2), Linear("z" => 1.0, "w" => -1.0)
(Linear{Char, Int64}('x' => 1, 'y' => 2), Linear{String, Float64}("w" => -1.0, "z" => 1.0))

julia> f(a, "z")
Linear{String, Int64} with 2 terms:
2*"yz"+"xz"

julia> f('x', b)
Linear{String, Float64} with 2 terms:
-"xw"+"xz"

julia> f(a, b)
Linear{String, Float64} with 4 terms:
-"xw"+2.0*"yz"-2.0*"yw"+"xz"

Bilinear extension of a function returning a linear combination

julia> f(x::Char, y::String) = Linear(x*y => BigInt(1), y*x => BigInt(-1)); @multilinear f

julia> f(a, b)   # same a and b as before
Linear{String, BigFloat} with 8 terms:
-2.0*"zy"-"xw"-"zx"+2.0*"yz"+"wx"-2.0*"yw"+"xz"+2.0*"wy"

julia> typeof(ans)
Linear{String, BigFloat}

Multilinear extension of a function

julia> g(xs::Union{Char,String}...) = *(xs...); @multilinear g

julia> g(a)   # same a and b as before
Linear{String, Int64} with 2 terms:
"x"+2*"y"

julia> g(a, b)
Linear{String, Float64} with 4 terms:
-"xw"+2.0*"yz"-2.0*"yw"+"xz"

julia> g(a, b, a)
Linear{String, Float64} with 8 terms:
-"xwx"+"xzx"+4.0*"yzy"+2.0*"xzy"+2.0*"yzx"-2.0*"ywx"-2.0*"xwy"-4.0*"ywy"

Multilinear extension using the two-argument version of @multilinear

julia> @multilinear(h, *)

julia> h(a, b; coeff = 2)   # same a and b as before
Linear{String, Float64} with 4 terms:
-2.0*"xw"+4.0*"yz"-4.0*"yw"+2.0*"xz"

MultilinearExtension(f)
MultilinearExtension(f, name)

An element of this type is a multilinear extension of f. One can additionally specify the name displayed for it.

Example

julia> a, b = Linear('x' => 1, 'y' => 2), Linear("z" => 1.0, "w" => -1.0)
(Linear{Char, Int64}('x' => 1, 'y' => 2), Linear{String, Float64}("w" => -1.0, "z" => 1.0))

julia> const concat = MultilinearExtension(*, "concat")
concat

julia> concat(a, b)
Linear{String, Float64} with 4 terms:
-"xw"+2.0*"yz"-2.0*"yw"+"xz"

LinearCombinations.mul(x1::Any, x2::Any, ...)

Return the product of the arguments. This is the multilinear extension of *.

The new name avoids type piracy since mul accepts all argument types.

@linear_kw function def

@linear_kw scans a function definition for the keywords coefftype, addto, coeff and sizehint and makes them known to the LinearCombinations package. This allows to write performant code. Not all keywords have to present. However, addto and coeff only have an effect if used together.

See also LinearCombinations.has_coefftype, LinearCombinations.has_addto_coeff, LinearCombinations.has_isfiltered, LinearCombinations.has_sizehint, LinearCombinations.unval.

Example

Consider the following two functions:

f(x::Char) = Linear(uppercase(x) => 1, x => -1)

@linear f

using LinearCombinations: unval   # unwraps a Val argument

@linear_kw function g(x::Char;
        coefftype = Int,
        addto = zero(Linear{Char,unval(coefftype)}),
        coeff = 1)
    addmul!(addto, uppercase(x), coeff)
    addmul!(addto, x, -coeff)
    addto
end

@linear g

The linear extensions are functionally equivalent, but g will be much faster than f.

julia> a = Linear('x' => 1, 'y' => 2)
Linear{Char, Int64} with 2 terms:
'x'+2*'y'

julia> f(a; coefftype = Float64, coeff = 2)
Linear{Char, Float64} with 4 terms:
4.0*'Y'-2.0*'x'-4.0*'y'+2.0*'X'

julia> g(a; coefftype = Float64, coeff = 2)
Linear{Char, Float64} with 4 terms:
4.0*'Y'-2.0*'x'-4.0*'y'+2.0*'X'

Test whether keywords have been registered:

julia> using LinearCombinations: has_coefftype, has_addto_coeff, has_sizehint

julia> has_coefftype(g, Char), has_addto_coeff(g, Char), has_sizehint(g, Char)
(true, true, false)

const LinearCombinations.DefaultCoefftype = Int

The coefficient type use by LinearCombinations if no other coefficient type information is available.

LinearCombinations.linear_filter(x) -> Bool

Return true if the term x is to be stored in linear combinations and false if it is to be dropped.

The effect of this is that linear combinations don't live in the vector space (or free module) spanned by all possible terms, but rather in the quotient by the subspace (or submodule) spanned by the terms for which linear_filter returns false. Setting coefficients for terms that are divided out is allowed, but has no effect.

The default return value of linear_fiilter is true for all arguments, so that nothing is divided out.

See also keeps_filtered, LinearCombinations.termcoeff.

Example

julia> LinearCombinations.linear_filter(x::Char) = islowercase(x)

julia> a = Linear('x' => 1, 'Y' => 2)
x

julia> a['Z'] = 3
3

julia> a
x

keeps_filtered(f, types...) -> Bool

Return true if the following is satisfied, and false otherwise: Whenever the function f is called with arguments of types types and returns a single term y, then linear_filter(y) == true holds.

By default, keeps_filtered returns false for all arguments. This can be changed to avoid unneccesary (and possibly expensive) calls to linear_filter. Note that if f returns a linear combination when called with term arguments, then all terms appearing in this linear combination satisfy the condition above anyway. The setting for keeps_filtered doesn't matter in this case.

See also LinearCombinations.linear_filter.

LinearCombinations.termcoeff(xc::Pair) -> Pair

Transform a term-coefficient pair into the format that is stored in a linear combination.

This function is called for every term-coefficient pair that enters a linear combination. The default is to return a pair x => c unchanged. This can be changed in special situations where one wants to normalize terms and coefficients. Note that termcoeff is called only if linear_filter(x) is true.

See also linear_filter.

Example

We show how to convert term-coefficient pairs with an uppercase letter to lowercase letters together with the negative coefficient.

julia> function LinearCombinations.termcoeff((x, c)::Pair{Char})
           isuppercase(x) ? lowercase(x) => -c : x => c
       end

julia> a = Linear('x' => 1, 'Y' => 2)
Linear{Char, Int64} with 2 terms:
'x'-2*'y'

julia> a['y'], a['Y']
(-2, 2)

julia> a['Y'] = 3; a
Linear{Char, Int64} with 2 terms:
'x'-3*'y'

julia> a + 'X'
Linear{Char, Int64} with 1 term:
-3*'y'

LinearCombinations.has_coefftype(f, types...) -> Bool

Return true if the method for f with signature given by types is known to support the keyword argument coefftype. The macro @linear_kw is used to make this keyword known to the LinearCombinations package.

See also @linear_kw, LinearCombinations.has_addto_coeff, LinearCombinations.has_isfiltered, LinearCombinations.has_sizehint.

LinearCombinations.has_addto_coeff(f, types...) -> Bool

Return true if the method for f with signature given by types is known to support the keyword arguments addto and coeff. The macro @linear_kw is used to make these keywords known to the LinearCombinations package.

See also @linear_kw, LinearCombinations.has_coefftype, LinearCombinations.has_isfiltered, LinearCombinations.has_sizehint.

LinearCombinations.has_isfiltered(f, types...) -> Bool

Return true if the method for f with signature given by types is known to support the keyword argument is_filtered::Bool. The macro @linear_kw is used to make this keyword known to the LinearCombinations package.

The keyword argument is_filtered = true for a linear or multilinear function f indicates this potentially expensive test can be skipped when evaluating f.

See also @linear_kw, LinearCombinations.has_coefftype, LinearCombinations.has_addto_coeff, LinearCombinations.has_sizehint, keeps_filtered.

LinearCombinations.has_sizehint(f, types...) -> Bool

Return true if the method for f with signature given by types is known to support the keyword argument sizehint. The macro @linear_kw is used to make this keyword known to the LinearCombinations package.

See also @linear_kw, LinearCombinations.has_coefftype, LinearCombinations.has_addto_coeff, LinearCombinations.has_isfiltered,

TensorSlurp(f)

TensorSlurp turns a linear function acting on Tensor terms into a multilinear function. This is similar to slurping in Julia.

The new function always returns a linear combination, even if none of the arguments is a linear combination. It recognizes all keyword arguments discussed for @linear. Unknown keyword arguments are passed on to f.

See also Tensor, tensor, TensorSplat, @linear.

Examples

We use swap as an example of a function acting on tensors.

julia> const f = TensorSlurp(swap)
TensorSlurp(Regroup{(1, 2),(2, 1)})

julia> a = Linear('x' => 1, 'y' => 2)
Linear{Char, Int64} with 2 terms:
'x'+2*'y'

julia> b = Linear("w" => 3, "z" => -1)
Linear{String, Int64} with 2 terms:
3*"w"-"z"

julia> c = tensor(a, b)
Linear{Tensor{Tuple{Char, String}}, Int64} with 4 terms:
3*'x'⊗"w"-'x'⊗"z"-2*'y'⊗"z"+6*'y'⊗"w"

julia> swap(c)
Linear{Tensor{Tuple{String, Char}}, Int64} with 4 terms:
-"z"⊗'x'-2*"z"⊗'y'+6*"w"⊗'y'+3*"w"⊗'x'

julia> f(a, b)
Linear{Tensor{Tuple{String, Char}}, Int64} with 4 terms:
-"z"⊗'x'-2*"z"⊗'y'+6*"w"⊗'y'+3*"w"⊗'x'

julia> f(a, b; addto = swap(c), coeff = -1)
Linear{Tensor{Tuple{String, Char}}, Int64} with 0 terms:
0

TensorSplat(f)

TensorSplat turns a multilinear function f into a linear function acting on terms of type Tensor. This is similar to splatting in Julia.

When called with an argument of type Tensor, the new function returns the the value of f on the components of the tensor (which may or may not be a linear combination). All keyword arguments are passed on to f in this case.

When called with a linear combination as argument, the new function returns a linear combination. It recognizes all keyword arguments discussed for @linear. Unknown keyword arguments are passed on to f.

See also Tensor, tensor, TensorSlurp, @linear.

Examples

julia> const f = MultilinearExtension(*)
MultilinearExtension(*)

julia> const g = TensorSplat(f)
TensorSplat(MultilinearExtension(*))

julia> a = Linear('x' => 1, 'y' => 2)
Linear{Char, Int64} with 2 terms:
'x'+2*'y'

julia> b = Linear("w" => 3, "z" => -1)
Linear{String, Int64} with 2 terms:
3*"w"-"z"

julia> f(a, b)
Linear{String, Int64} with 4 terms:
3*"xw"-2*"yz"+6*"yw"-"xz"

julia> c = tensor(a, b)
Linear{Tensor{Tuple{Char, String}}, Int64} with 4 terms:
3*'x'⊗"w"-'x'⊗"z"-2*'y'⊗"z"+6*'y'⊗"w"

julia> g(c)
Linear{String, Int64} with 4 terms:
3*"xw"-2*"yz"+6*"yw"-"xz"

julia> g(c; addto = f(a, b), coeff = -1)
Linear{String, Int64} with 0 terms:
0