Kronecker.jl

A general-purpose toolbox for efficient Kronecker-based algebra.

Kronecker.jl is a Julia package for working with large-scale Kronecker systems. The main feature of Kronecker.jl is providing a function kronecker(A, B) used to obtain an instance of the lazy GeneralizedKroneckerProduct type. In contrast to the native Julia function kron(A, B), this does not compute the Kronecker product but instead stores the matrices in a specialized structure.

Commonly-used mathematical functions are overloaded to provide the most efficient methods to work with Kronecker products. We also provide an equivalent binary operator ⊗ which can be used directly as a Kronecker product in statements, i.e., A ⊗ B.

• Kronecker.jl
• • Package features
  • Example use
• Basic use
• • Constructing Kronecker products
  • Basic properties of Kronecker products
  • Linear algebra
• Factorization methods
• • Eigenvalue decomposition
  • Cholesky factorization
• Indexed Kronecker products
• Kronecker powers and graphs
• • Kronecker powers
  • Kronecker graphs
• Kronecker sums
• Multiplication
• • Kronecker-kronecker multiplications
  • The Vec trick
  • Docstrings
  • Sampled Kronecker-vector multiplications
• Types

Package features

• tr, det, size, eltype, inv, ... are efficient functions to work with Kronecker products. Either the result is a numeric value, or returns a new KroneckerProduct type.
• Kronecker product - vector multiplications are performed using the vec trick. Two Kronecker products of conformable size can be multiplied efficiently, yielding another Kronecker product.
• Working with incomplete systems using the sampled vec trick.
• Overloading of the function eigen to compute eigenvalue decompositions of Kronecker products. It can be used to efficiently solve systems of the form (A ⊗ B +λI) \ v.
• Higher-order Kronecker systems are supported: most functions work on A ⊗ B ⊗ C or systems of arbitrary order.
  • Efficient sampling of Kronecker graphs is supported.
• Kronecker powers are supported: kronecker(A, 3) or A ⊗ 3.
• A KroneckerSum can be constructed with A ⊕ B (typed using \oplus TAB) or kroneckersum(A,B).
  • Multiplication with vectors uses a specialized version of the vec trick
  • Higher-order sums are supported, e.g. A ⊕ B ⊕ C or kroneckersum(A,4).

Example use

julia> using Kronecker, LinearAlgebra
julia> A = [1.0 2.0;
            3.0 5.0];
julia> B = Array{Float64, 2}([1 2 3;
                   4 5 6;
                   7 -2 9]);
julia> K = A ⊗ B6×6 Kronecker.KroneckerProduct{Float64,Array{Float64,2},Array{Float64,2}}:
  1.0   2.0   3.0   2.0    4.0   6.0
  4.0   5.0   6.0   8.0   10.0  12.0
  7.0  -2.0   9.0  14.0   -4.0  18.0
  3.0   6.0   9.0   5.0   10.0  15.0
 12.0  15.0  18.0  20.0   25.0  30.0
 21.0  -6.0  27.0  35.0  -10.0  45.0
julia> collect(K)  # yield the dense matrix6×6 Array{Float64,2}:
  1.0   2.0   3.0   2.0    4.0   6.0
  4.0   5.0   6.0   8.0   10.0  12.0
  7.0  -2.0   9.0  14.0   -4.0  18.0
  3.0   6.0   9.0   5.0   10.0  15.0
 12.0  15.0  18.0  20.0   25.0  30.0
 21.0  -6.0  27.0  35.0  -10.0  45.0
julia> tr(K)90.0
julia> det(K)-3600.000000000004
julia> K'  # (conjugate transpose)6×6 Kronecker.KroneckerProduct{Float64,Adjoint{Float64,Array{Float64,2}},Adjoint{Float64,Array{Float64,2}}}:
 1.0   4.0   7.0   3.0  12.0   21.0
 2.0   5.0  -2.0   6.0  15.0   -6.0
 3.0   6.0   9.0   9.0  18.0   27.0
 2.0   8.0  14.0   5.0  20.0   35.0
 4.0  10.0  -4.0  10.0  25.0  -10.0
 6.0  12.0  18.0  15.0  30.0   45.0
julia> inv(K')6×6 Kronecker.KroneckerProduct{Float64,Adjoint{Float64,Array{Float64,2}},Adjoint{Float64,Array{Float64,2}}}:
  4.75   0.5  -3.58333   -2.85  -0.3   2.15
 -2.0   -1.0   1.33333    1.2    0.6  -0.8
 -0.25   0.5  -0.25       0.15  -0.3   0.15
 -1.9   -0.2   1.43333    0.95   0.1  -0.716667
  0.8    0.4  -0.533333  -0.4   -0.2   0.266667
  0.1   -0.2   0.1       -0.05   0.1  -0.05
julia> K * K  # (A * A) ⊗ (B * B)6×6 Kronecker.KroneckerProduct{Float64,Array{Float64,2},Array{Float64,2}}:
  210.0    42.0   294.0   360.0    72.0   504.0
  462.0   147.0   672.0   792.0   252.0  1152.0
  434.0   -98.0   630.0   744.0  -168.0  1080.0
  540.0   108.0   756.0   930.0   186.0  1302.0
 1188.0   378.0  1728.0  2046.0   651.0  2976.0
 1116.0  -252.0  1620.0  1922.0  -434.0  2790.0
julia> v = collect(1:6)6-element Array{Int64,1}:
 1
 2
 3
 4
 5
 6
julia> K * v6-element Array{Float64,1}:
  78.0
 186.0
 174.0
 202.0
 481.0
 450.0