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}}:
  -6.2587     -2.63974     5.19565    …   0.133244   -0.262257     -0.56529
  -4.84213     0.466945   -5.70394       -0.0235696   0.287913      0.037621
   0.94451    -7.9439      2.99421        0.400978   -0.151137     -0.287519
 -11.4629      0.629269    0.0700806     -0.0317631  -0.00353741   -0.656001
   0.416761    0.175778   -0.345973      -1.18353     2.32948       5.02115
   0.322433   -0.0310934   0.37982    …   0.209355   -2.55737      -0.334166
  -0.062894    0.528977   -0.199382      -3.56166     1.34246       2.55387
   0.763304   -0.0419024  -0.0046666      0.282134    0.0314208     5.82688
  -9.72595    -4.10213     8.07398        3.08134    -6.06482     -13.0726
  -7.52462     0.725627   -8.86387       -0.545059    6.65814       0.870004
   1.46776   -12.3447      4.65298    …   9.27282    -3.49511      -6.64901
 -17.8132      0.977878    0.108905      -0.734538   -0.0818043   -15.1703
  -1.34218    -0.566092    1.11421       -2.40446     4.73257      10.201
  -1.03839     0.100136   -1.22321        0.425327   -5.19556      -0.678891
   0.20255    -1.70357     0.642109      -7.23587     2.72734       5.18844
  -2.45822     0.134947    0.0150288  …   0.573183    0.0638345    11.8379
  -1.59656    -0.673385    1.32539        1.07621    -2.11825      -4.56584
  -1.2352      0.119115   -1.45505       -0.190372    2.32548       0.303864
   0.24094    -2.02645     0.76381        3.2387     -1.22073      -2.32229
  -2.92413     0.160524    0.0178773     -0.256551   -0.0285716    -5.29852

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}:
  0.1502095661063918
 -1.5954593201840215
 -1.378290641136343
  0.36700980485121687
 -0.5058937084626813
  1.590734618863015
  1.0299874513726168
  0.79475277256565
  0.048038837403401785
  0.9473536076140875
  ⋮
  2.343944777099711
  1.1553750656603272
  0.1060254730636805
  1.7824153502374238
  0.09750012348127234
 -0.8437620813562253
 -1.1225843338662187
  0.11382115751442065
 -0.5747767705610549

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}:
  5.15531    -0.176896
  5.36415    -1.05323
  7.11646    -1.38553
  5.98653     0.878107
  2.06343     0.0651956
  3.46391    -0.169993
  3.47602    -0.566238
  4.23223    -1.94909
  3.94527     0.996622
  1.63857     1.70967
  ⋮          
  0.781027    0.765067
  2.23388     0.815828
  1.23642     2.43505
 -0.676014    1.92254
 -0.317974    2.30683
 -0.0285209   0.268468
  0.76483     2.25789
 -0.409987    3.02141
 -2.56932     1.35425

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.