Fastest way to compute a multiplication of matrices times a sequence of kronecker products

3 views (last 30 days)
I would like to compute the following operation
o=f*(kron(a0,a1,a1,a1,a1)+kron(a1,a0,a1,a1,a1)+kron(a1,a1,a0,a1,a1)+kron(a1,a1,a1,a0,a1)+kron(a1,a1,a1,a1,a0))*B
All matrices involved in the operation are very sparse. In particular,
a0 is of size 38 x 6 with 141 nonzero elements
a1 of size 38 x 6 with 32 nonzero elements
f is of size 25 x 79,235,168 with 4698 nonzero elements
B is of size 7776 x 7776 with 18 nonzero elements
In the notation above kron(a0,a1,a1,a1,a1) is a shorthand for kron(kron(kron(kron(a0,a1),a1),a1),a1)
How fast can this problem be solved and what is the fastest way to solve it?

Accepted Answer

Matt J
Matt J on 8 Aug 2022
Edited: Matt J on 8 Aug 2022
With this FEX package
it takes about 5 sec. on my machine: (EDIT: now it's much faster if we aggregate some of the operands into explicit Kronecker products, about 0.02 sec.)
a0=sprand(38,6,141/38/6);
a1=sprand(38,6,38/38/6);
ft=sprand(79235168,25,4698/25/79235168); %f tranposed - less memory
B=sprand(7776,7776,18/7776^2);
tic
K{1}=KronProd({kron(a0,kron(a1,a1)),kron(a1,a1)}).';
K{2}=KronProd({kron(a1,kron(a0,a1)),kron(a1,a1)}).';
K{3}=KronProd({kron(a1,kron(a1,a0)),kron(a1,a1)}).';
K{4}=KronProd({kron(a1,kron(a1,a1)),kron(a0,a1)}).';
K{5}=KronProd({kron(a1,kron(a1,a1)),kron(a1,a0)}).';
toc%Elapsed time is 0.007476 seconds.
tic;
o=0;
for i=1:5
o=o+K{i}*ft;
end
o=o.'*B;
toc%Elapsed time is 0.015946 seconds.
My code works with the transpose of f, since this consumes a lot less memory. Compare:
f=ft.';
whos f ft
Name Size Bytes Class Attributes f 25x79235168 633956520 double sparse ft 79235168x25 75376 double sparse
  17 Comments
Patrick Mboma
Patrick Mboma on 8 Aug 2022
Sorry, my mistake! I have rechecked and you are right, the results are numerically the same.
Thank you so much !

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!