Multiplication

Kronecker.jl allows for efficient multiplication of large Kronecker systems by overloading the multiplication function *. We distinguish three cases:

Kronecker-Kronecker multiplications yield again a type of AbstractKroneckerProduct;
Kronecker-vector multiplications use the 'vec trick' and yield a vector;
sampled Kronecker-vector multiplications use the sampled-vec trick to yield a vector.

Kronecker-kronecker multiplications

Multiplying two conformable Kronecker products of the same order yield a new Kronecker product, based on the mixed-product property:

\[(A \otimes B)(C \otimes D) = (AC) \otimes (BD),\]

A, B, C, D = randn(5, 5), randn(4, 4), randn(5, 4), randn(4, 4);
(A ⊗ B) * (C ⊗ D)

20×16 Kronecker.KroneckerProduct{Float64, Matrix{Float64}, Matrix{Float64}}:
  -1.11175     1.487      0.493717  …  -2.08163   -0.69115     2.14722
  -3.65045     3.21493   -1.11694      -4.50055    1.5636      0.415925
  -3.44066     4.13651    1.6345       -5.79066   -2.28812     3.67649
   1.7347     -2.05592   -1.3918        2.87807    1.94837    -4.30458
   4.13965    -5.53692   -1.83838       3.17972    1.05574    -3.2799
  13.5926    -11.971      4.15899   …   6.87464   -2.38841    -0.635331
  12.8115    -15.4025    -6.08614       8.8453     3.49513    -5.61587
  -6.45925     7.65534    5.18244      -4.39628   -2.97616     6.5753
   1.98283    -2.65211   -0.880559      4.44626    1.47626    -4.58635
   6.51068    -5.73392    1.9921        9.61293   -3.33976    -0.888395
   6.13651    -7.37759   -2.91518   …  12.3685     4.88731    -7.85278
  -3.09389     3.6668     2.48232      -6.1474    -4.16161     9.19437
  -0.630147    0.842842   0.279843      1.32924    0.441339   -1.37113
  -2.0691      1.82225   -0.633092      2.87386   -0.998447   -0.265592
  -1.95019     2.34461    0.926447      3.69767    1.4611     -2.34765
   0.983243   -1.16531   -0.788884  …  -1.83781   -1.24415     2.74873
  -4.23941     5.67035    1.88268      -0.263572  -0.0875118   0.271876
 -13.9202     12.2594    -4.25922      -0.569849   0.197979    0.0526635
 -13.1202     15.7737     6.23281      -0.7332    -0.289717    0.465508
   6.61491    -7.83983   -5.30733       0.364415   0.246698   -0.545037

The Vec trick

Reshaping allows computing a product between a Kronecker product and vector as two matrix multiplications. This is the so-called vec trick which holds for any set of conformable matrices:

\[(A \otimes B) \text{vec}(X) = \text{vec}(B^\intercal X A).\]

Here, $\text{vec}(\cdot)$ is the vectorization operator, which stacks all columns of a matrix into a vector.

A, B = rand(10, 10), rand(5, 6);
x = randn(60);
(A ⊗ B) * x

50-element Vector{Float64}:
  1.5980924797416427
  1.5282565358835418
 -2.102401710038416
 -1.0940436063420702
  2.8970434615654836
  3.373855821778105
  5.409216124873286
  1.9571476136158834
  2.2973902776702477
  5.095787958492494
  ⋮
  1.0035523760663332
 -1.638817108915303
 -1.3375732150365578
  1.7964553029320645
  2.19504514352293
  3.2377082489211344
 -1.0913871371669321
 -0.45504936699351395
  4.176465430910038

Note that this trick is extended to also work with matrices:

A, B = rand(10, 10), rand(5, 6);
x = randn(60, 2);
(A ⊗ B) * x

50×2 Matrix{Float64}:
  0.86889    6.36823
 -0.0824133  3.56234
  0.672417   3.53476
  1.92115    6.68805
  0.449999   4.65645
  1.15106    7.17939
  0.526125   5.09992
  0.969942   4.78106
  0.928264   6.38944
  0.508215   5.00116
  ⋮          
  1.22652    3.63325
  2.35629    4.31528
  5.39486    6.81673
  2.72833    4.55902
  1.13418    3.32175
 -0.908235   2.05945
  0.979855   2.79707
  2.92832    3.58106
  1.35963    3.70023

The vec trick works with higher-order Kronecker products. However, at the moment this has a substantial overhead and likely be relatively slow.

Docstrings

Missing docstring.

Missing docstring for mul!. Check Documenter's build log for details.

LinearAlgebra.lmul! — Function

lmul!(a::Number, K::AbstractKroneckerProduct)

Scale an AbstractKroneckerProduct K inplace by a factor a by rescaling the left matrix.

source

lmul!(a::Number, K::KroneckerPower)

Scale an KroneckerPower K inplace by a factor a by rescaling the matrix the base matrix with a factor a^(1/N).

It is recommended to rewrite your Kronecker product rather as copy(A) ⊗ (A ⊗ n - 1) (note the copy) for numerical stability. This will only modify the first matrix, leaving the chain of Kronecker products alone.

source

LinearAlgebra.rmul! — Function

rmul!(K::AbstractKroneckerProduct, a::Number)

Scale an AbstractKroneckerProduct K inplace by a factor a by rescaling the right matrix.

source

Sampled Kronecker-vector multiplications

See Indexed Kronecker products for the specifics.