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,Array{Float64,2},Array{Float64,2}}:
 -2.53001     1.32594      1.31749     …  -0.182948     0.547951
  6.14912     7.16137      2.66271        -0.369747    -0.919557
  1.19679     0.886609     0.293427       -0.0407456   -0.405255
 -2.4154     -0.0394593   -7.63511         1.06022      1.92124
  1.26891    -0.66502     -0.660778       -0.0472649    0.141564
 -3.08406    -3.59175     -1.33547     …  -0.0955249   -0.237569
 -0.600245   -0.444674    -0.147167       -0.0105267   -0.104698
  1.21143     0.0197906    3.82935         0.27391      0.496356
 -0.0692255   0.0362801    0.0360487      -0.0210722    0.0631141
  0.168251    0.195947     0.0728564      -0.0425882   -0.105916
  0.0327463   0.0242591    0.00802866  …  -0.00469315  -0.046678
 -0.0660895  -0.00107968  -0.20891         0.122118     0.221292
  1.64099    -0.860019    -0.854533       -0.212799     0.637361
 -3.98838    -4.64493     -1.72706        -0.430079    -1.0696
 -0.77625    -0.575063    -0.190319       -0.0473941   -0.471381
  1.56665     0.0255937    4.9522      …   1.23322      2.23473
 -1.31762     0.690545     0.686141       -1.43423      4.29569
  3.20243     3.72961      1.38673        -2.89865     -7.20892
  0.623284    0.461742     0.152815       -0.319427    -3.17701
 -1.25793    -0.0205503   -3.97633         8.31165     15.0617

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 Array{Float64,1}:
 -6.755234772252771
 -1.5339020476853158
  0.28718084992929105
 -4.461604506324915
 -1.683274371359666
 -7.108126720386315
 -2.963076723433096
  0.5198640466570326
 -5.503484373407693
 -0.8754558089887536
  ⋮
 -1.7003184119406807
  0.4328280494699081
 -5.023359964824601
 -1.0650826889880298
 -7.945219678754793
 -2.4329946184020574
 -0.20306351171838877
 -6.644509080895488
 -1.4967462019517703

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 Array{Float64,2}:
  3.6005    -2.62589
  4.18739   -0.533891
  2.57193   -1.84092
  4.49801    0.55351
  5.46304   -3.07077
  0.147221  -2.64655
  1.84116   -1.82511
 -0.593763  -2.94895
  1.32617   -2.69926
  1.45043   -3.32702
  ⋮         
  2.07592    0.227418
  0.418109  -1.04095
  2.00125    1.076
  2.47961   -1.98871
  2.30232   -2.0384
  4.41552    0.426986
  2.32245   -1.57576
  5.42984    1.64215
  3.68175   -1.81372

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.