KroneckerTools

WORK IN PROGRESS

KroneckerTools computes chains of Kronecker products as described in Kamenik (2005).

The following computations are performed

• c = (I_p ⊗ A ⊗ I_q)*b
• c = (I_p ⊗ A^T ⊗ I_q)*b
• c = (A ⊗ A ⊗ ... ⊗ A)*b
• d = (A^T ⊗ A^T ⊗ ... ⊗ A^T ⊗ B)*c
• C = A * (B ⊗ B ⊗ .... ⊗ B)
• D = A B (C ⊗ C ⊗ .... ⊗ C)
• D = A^T B (C ⊗ C ⊗ .... ⊗ C)
• E = AB(C ⊗ D ⊗ ... ⊗ D)

Installation

 julia> using Pkg
 julia> Pkg.add("KroneckerTools")

Documentation

Algorithms

We exploit the following property of the Kronecker product: vec(A B C) = (C^T ⊗ A) * vec(B), so as never to form the matrix corresponding to the Kronecker product and whenever possible use matrix product instead.

Let A, a m * n matrix, B, a matrix whose size depends on the context, and b = vec(B). It follows that

• c = (I_p ⊗ A) b = vec(A B), where B is a n * p matrix.
• c = (A ⊗ I_q) b = vec(B A^T), where B is a q * m matrix
• c = (I_p ⊗ A ⊗ I_q) b is computed in p blocks c_i = vec(B_i A^T), i = 1, ..., p where B_i is the i^th block of q * n elements of vector b

A chain of Kronecker products, (A₁ ⊗ A₂ ⊗ ... ⊗ A_n) b can be written as (A₁ ⊗ I_p1) (I_p2 ⊗ A₂ ⊗ I_p2) ... (I_pn ⊗ A_n)b where b is a vector and p_1>, p₂, ..., p_n, q₁, q₂, ...,q_n are such as making each group in brackets conformable.

References

O. Kamenik (2005), "Solving SDGE models: A new algorithm for the Sylvester equation", Computational Economics 25, 167--187.