Efficient (possibly preallocated) chain of Kronecker products

Specific Domains Numerics
1

I need to calculate something not unlike

reduce(kron, As...)

where As are 3–8 matrices. If it helps, I can preallocate for the output. Elements of As are dense, the length of As is known at compile time (unrolling is possible), etc.

I am wondering if there is an efficient algorithm for this, and whether this is implemented in any library.

Preliminary pencil-and-paper calculations suggest that a lot of interim results can be reused, and I can traverse efficiently with a CartesianIndices, but I thought I would ask here before reinventing the wheel (if there is a good algorithm but it is not yet implemented, I will implement it and make it publicly available in a package).

1 Like
2

Maybe Kronecker.jl would be helpful?

5 Likes
3

I have some work in progress here: https://github.com/MichelJuillard/dynare.jl/blob/master/src/linalg/KroneckerUtils.jl. It isn’t entirely optimized., Maybe it is of help. The original reference is https://www.cnb.cz/export/sites/cnb/en/economic-research/.galleries/research_publications/cnb_wp/cnbwp_2005_10.pdf Look at Appendix C p. 18.

2 Likes