File Exchange

image thumbnail

Fast and Efficient Kronecker Multiplication

version 1.1 (1.48 KB) by

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

9 Downloads

Updated

No License

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.

Comments and Ratings (7)

carlos

carlos (view profile)

 

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

carlos

carlos (view profile)

Eduardo

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

SONGTING

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

David Gleich

David Gleich (view profile)

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

Cesare

Cesare (view profile)

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

Updates

1.1

Fixed the citation.

MATLAB Release
MATLAB 7.7 (R2008b)
Tags Add Tags
Acknowledgements

Inspired: Fast Kronecker matrix multiplication

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video