No BSD License  

5.0

5.0 | 3 ratings Rate this file 23 Downloads (last 30 days) File Size: 1.48 KB File ID: #23606

Fast and Efficient Kronecker Multiplication

by

 

09 Apr 2009 (Updated )

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

| Watch this File

File Information
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)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (7)
13 Nov 2012 carlos

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

13 Nov 2012 carlos  
25 Jan 2012 Eduardo  
25 Jan 2012 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

20 Sep 2011 SONGTING

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

14 Apr 2009 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

14 Apr 2009 Cesare

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

Updates
14 Apr 2009

Fixed the citation.

Contact us