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}}:
  4.14885   -1.44107    4.38331   …   1.49164   -4.53712   -1.26053
  2.69083   -0.681624   2.21182       0.705543  -2.28944   -1.9202
 -4.84623    1.42667    0.914254     -1.47673   -0.946336   0.588926
 -2.43663   -1.51151   -1.9276        1.56455    1.99525    2.23244
 -5.52633    1.91953   -5.83864       0.991959  -3.01724   -0.838267
 -3.58423    0.907934  -2.94618   …   0.469195  -1.5225    -1.27696
  6.45525   -1.90034   -1.2178       -0.982043  -0.629325   0.391643
  3.24562    2.01335    2.5676        1.04044    1.32686    1.4846
 -4.5372     1.57596   -4.79361       1.39041   -4.22921   -1.17498
 -2.94271    0.745428  -2.41886       0.65766   -2.13406   -1.78988
  5.29986   -1.56021   -0.999833  …  -1.37651   -0.882112   0.548957
  2.66471    1.65299    2.10804       1.45837    1.85984    2.08093
 -3.33709    1.15911   -3.52567       1.33659   -4.06551   -1.1295
 -2.16434    0.548258  -1.77906       0.632205  -2.05146   -1.7206
  3.89801   -1.14752   -0.735371     -1.32323   -0.847969   0.52771
  1.95988    1.21576    1.55045   …   1.40192    1.78785    2.00039
  1.07858   -0.374637   1.13953      -2.69055    8.18386    2.27369
  0.699538  -0.177203   0.57501      -1.27263    4.12958    3.46357
 -1.25988    0.370892   0.23768       2.66366    1.70696   -1.06228
 -0.633453  -0.392948  -0.501122     -2.82206   -3.59894   -4.02678

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}:
 -2.288615876653745
 -4.6950726015817015
 -3.360244020111282
 -2.1400592519884727
 -3.5795470770557807
 -0.7053359020893049
 -1.7432240700910726
 -1.0309061508926907
 -1.049179477566011
 -0.809201382742677
  ⋮
 -0.3744925336220022
 -0.24973216851618263
  0.06947807180545612
 -0.31599864153680585
 -0.5246896461176256
 -2.129875957949822
 -1.8585915722520754
 -1.0086811065869492
 -1.1241586235720518

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}:
  3.45506   -3.1162
  4.90488   -1.57651
  5.08942   -5.09294
  3.08144   -5.81177
  6.20885   -3.53238
  4.4003    -4.28453
  6.48055   -2.77907
  5.56242   -3.78515
  2.48352   -4.80394
  6.24574   -3.89798
  ⋮         
  1.50495   -1.77981
 -0.504583  -4.92037
 -1.30422   -4.63929
 -0.802639  -4.4299
  3.02957   -4.41088
  6.85321   -2.33172
  4.29294   -4.09646
  0.523117  -5.13116
  3.1481    -5.09591

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

Docstrings

Kronecker.mul_vec_trick! — Function

mul_vec_trick!(x::AbstractVector, K::AbstractKroneckerProduct, v::AbstractVector)

Calculates the vector-matrix multiplication K * v and stores the result in x, overwriting its existing value.

source

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.