[ANN] LinearCombinations.jl: formal linear combinations + (multi)linear maps

Package Announcements
, ,
1

LinearCombinations.jl

This package addresses a very specific part of symbolic computation: formal linear combinations and linear maps between them. Multilinear maps and tensors are also supported. Formal linear combinations come up in many parts of (pure) mathematics, for example as elements of the group ring of a group or as simplicial chains in a simplicial complex.

The overall aim of the package is to provide functions that are easy to use and at the same time fast enough to deal with large linear combinations having millions of terms. The terms can be of any type, and coefficients can be in any commutative ring with unit. In the examples below we use Char and String for terms together with integer coefficients.

LinearCombinations.jl comes with an extensive documentation. For a use case, see the package SimplicialSets.jl.

Linear combinations

The type Linear can store any number of term-coefficient pairs. Term type and coefficient type are automatically determined if possible.

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

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

julia> c = a + 2*b - 'v'
Linear{Char, Int64} with 5 terms:
-2*'w'+'x'+2*'y'-'v'+6*'z'

julia> c .-= 2 .* b  # in-place modification
Linear{Char, Int64} with 3 terms:
'x'+2*'y'-'v'

Linear combinations with non-concrete types are also possible. For Linear, the terms and coefficients are internally stored in a dictionary. In contrast, the type DenseLinear uses a coordinate vector with respect to a chosen basis.

Linear maps

The following linear function maps terms to terms. Linearity is achieved via the macro @linear.

julia> @linear f; f(x::Char) = uppercase(x);

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

Here is another linear function, this time mapping terms to linear combinations.

julia> @linear g; g(x::Char) = Linear(f(x) => 1, x => -1);

julia> g(a)
Linear{Char, Int64} with 4 terms:
2*'Y'-'x'-2*'y'+'X'

(A more efficient implementation of g would use the keyword arguments addto and coeff, see @linear_kw.)

Multilinear maps

Multiplication is bilinear by default. Recall that multiplying Char or String values in Julia means concatenation.

julia> a * 'w'
Linear{String, Int64} with 2 terms:
"xw"+2*"yw"

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

For a user-defined function, bilinearity (or higher multilinearity) is achieved with the macro @multilinear.

julia> @multilinear h; h(x, y) = x*y*x
h (generic function with 2 methods)

julia> h(a, b)
Linear{String, Int64} with 8 terms:
-"xwx"+3*"xzx"+12*"yzy"+6*"xzy"+6*"yzx"-2*"ywx"-2*"xwy"-4*"ywy"

Multilinear function with a variable number of arguments are also possible.

Tensors

We use the intrinsic definition of a tensor. The ones appearing in physics are their coordinate representations.

We define a tensor and swap the two components of each term.

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

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

We finally take the tensor product of the functions f and g and apply it to a pure tensor and to a⊗b.

julia> f⊗g
Linear{Tensor{Tuple{typeof(f), typeof(g)}}, Int64} with 1 term:
f⊗g

julia> (f⊗g)('x'⊗'z')
Linear{Tensor{Tuple{Char, Char}}, Int64} with 2 terms:
-'X'⊗'z'+'X'⊗'Z'

julia> (f⊗g)(a⊗b)
Linear{Tensor{Tuple{Char, Char}}, Int64} with 8 terms:
-3*'X'⊗'z'+2*'Y'⊗'w'+3*'X'⊗'Z'+'X'⊗'w'-'X'⊗'W'-2*'Y'⊗'W'-6*'Y'⊗'z'+6*'Y'⊗'Z'

One can assign degrees to terms and maps. In this case tensor operations observe the usual sign rule. See deg, and swap for an example.

3 Likes