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}}:
  -4.21776    -1.2954    -2.9602    …  -1.45828    -3.3324     5.74999
  -5.42405     4.29973    2.78552       4.84036     3.13576   -4.2481
  -3.54116     4.54055   -2.91149       5.11146    -3.27757    3.93864
   4.43406    -4.4787    -5.41346      -5.04183    -6.09413    5.06481
   0.517362    0.158898   0.363106      0.0534219   0.122077  -0.210642
   0.665328   -0.527416  -0.34168   …  -0.177319   -0.114874   0.155623
   0.434368   -0.556957   0.357131     -0.187251    0.120069  -0.144286
  -0.543894    0.549369   0.66403       0.1847      0.223249  -0.185542
   1.73763     0.533678   1.21954       1.10467     2.52436   -4.35573
   2.23459    -1.7714    -1.14758      -3.66666    -2.3754     3.21802
   1.45888    -1.87061    1.19947   …  -3.87203     2.48282   -2.98359
  -1.82674     1.84513    2.23023       3.81928     4.61641   -3.83669
  -4.27724    -1.31367   -3.00194      -0.718107   -1.64099    2.8315
  -5.50054     4.36037    2.82481       2.38356     1.54416   -2.09191
  -3.5911      4.60459   -2.95255       2.51706    -1.61399    1.93952
   4.49659    -4.54186   -5.48981   …  -2.48277    -3.00096    2.49409
  11.1789      3.43337    7.84579       1.7219      3.9348    -6.78943
  14.376     -11.3961    -7.38282      -5.71536    -3.70262    5.01604
   9.38557   -12.0344     7.71669      -6.03547     3.87006   -4.65063
 -11.7521     11.8705    14.348         5.95325     7.19577   -5.98039

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}:
 3.3323849553293274
 2.3244678115924517
 2.1012430791072063
 1.5339571236134986
 2.6842091757144404
 4.934594591805311
 4.084142611082458
 3.410133218130084
 1.9410384595338557
 3.5880403619161716
 ⋮
 4.339171439931756
 3.8367537192866625
 4.070510436810194
 4.515178130726152
 4.929973086000409
 3.5476112152775054
 2.836828655335608
 1.0149422416069795
 3.5678157336433793

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.04367   -0.0822368
 -3.19008   -1.17649
 -2.48251    0.932163
 -3.04768    0.910472
 -1.60227    0.966046
 -0.813873  -3.6623
  0.437571  -7.26946
 -0.575111  -3.32492
 -1.81486   -2.52947
  0.461817  -4.10244
  ⋮         
 -2.90707   -4.10723
 -1.93242   -0.915759
 -2.61245   -0.827569
 -1.62869   -1.26214
 -1.45081   -2.4135
 -1.25738   -5.03257
 -0.519944  -3.22049
 -1.6295    -1.31189
 -0.53592   -2.67936

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.