Fast and Efficient Kronecker Multiplication

Computes a matrix-vector product with a repeated Kronecker product matrix.

Description

Computing the matrix-vector product

y = (Q1 kron Q2 kron ... kron Qm) * x

can be done without ever forming the big matrix of Kronecker products. This m-file implements an algorithm for this task from page 394 of Fernandes, et al. 1998, JACM 45(3): 381--414 (doi:10.1145/278298.278303). The implementation works where X is a matrix too.

Don't be scared off by the for-loops, this code works well with the Matlab JIT compiler and works for vectors with over 50 million entries.

• MATLAB release: MATLAB 7.7 (R2008b)

[Cesare]

Hi! Many thanks for the interesting submission!
Could you provide some additional info regarding the reference you cite?
Many thanks,
Cesare

[David Gleich]

My apologies, I had a few typos in the citation that made it difficult to find. I've fixed this issue. The doi is http://dx.doi.org/10.1145/278298.278303

[SONGTING]

Hi! very nice function.
I was wondering whether there is a similar
fast algorithm for general matrix (not just the square matrix).

[Eduardo]

Nice code. I would like to know if this is the most efficient code if the Q matrices are sparse. It may be the case I only have 2 matrices Q{1} and Q{2}, however they are very large sparse matrices such that their kronecker product surely cannot be stored. I've already checked that this code is indeed efficient memory-wise in this case. Now I wonder if it could be further speeded up for sparse matrices or if this is the best we can do.

Thanks a lot

[Eduardo]