Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Efficiently computing large numbers of vector norms
Replies: 16   Last Post: Nov 15, 2012 8:32 AM

 Messages: [ Previous | Next ]
 Matt J Posts: 4,997 Registered: 11/28/09
Re: Efficiently computing large numbers of vector norms
Posted: Nov 13, 2012 7:03 PM

"Harry Commin" wrote in message <k7u6mu\$ltc\$1@newscl01ah.mathworks.com>...
> I cannot repeat your test, as I get an "Out of Memory" error. Furthermore, I require that A1 and A2 change on each iteration. Therefore, the KronProd() operation must also go inside the tic/toc.
>
> Perhaps you could copy and paste my code (for which I get comparable performance using a simple loop):

==============

OK. Well, if A1 and A2 have to change, then that will obviously increase overhead. However, I still find that the gap between KronProd and the other approaches increases with N1, N2. Here are the results of my tests

Single Loop = 38.3979 secs
No Loop = 31.6648 secs
Fast KronProd = 7.1126 secs

but with the modified code below. Note that I removed all of the ctranspose operations from the loops, because in reality they are avoidable and contribute unnecessary overhead. Note that kron(A1,A2)' is implemented much faster as kron(A1',A2') and you could construct A1 and A2 as QixNi to avoid the need to transpose. Also, you should not need to transpose the final result, either. If you want the result to be Q2xQ1 instead of Q1xQ2, then you should apply kron(A2,A1) instead of kron(A1,A2). I've incorporated all of these ideas into the modified code.

Ntrials = 5;

% Data Dimensions
N1 = 9*5; N2 = 7*5;
Q1 = 180; Q2 = 63;

% Data
A1 = randn(N1,Q1) + 1j*randn(N1,Q1);
A2 = randn(N2,Q2) + 1j*randn(N2,Q2);
X2 = randn(N1*N2,N1*N2) + 1j*randn(N1*N2,N1*N2);

A1=A1';
A2=A2';

tic
Z2b = zeros(Q1,Q2);
for trial = 1:Ntrials
for j = 1:Q2
Z2b(:,j) = sum(abs(kron(A1,A2(j,:))*X2).^2,2);
end
end
t = toc;
disp(['Single Loop = ',num2str(t), ' secs'])

tic
for trial = 1:Ntrials
Z2c = reshape(sum(abs(kron(A2,A1)*X2).^2,2),Q2,Q1);
end
t = toc;
disp(['No Loop = ',num2str(t), ' secs'])

tic
for trial = 1:Ntrials
Z2d = reshape(sum(abs(KronProd({A1,A2})*X2).^2,2),Q2,Q1);
end
t = toc;
disp(['Fast KronProd = ',num2str(t), ' secs'])

Date Subject Author
11/7/12 Harry Commin
11/7/12 Harry Commin
11/8/12 Teja Muppirala
11/8/12 Teja Muppirala
11/8/12 Bruno Luong
11/8/12 Matt J
11/9/12 Matt J
11/12/12 Harry Commin
11/12/12 Harry Commin
11/13/12 Matt J
11/13/12 Harry Commin
11/13/12 Matt J
11/13/12 Harry Commin
11/13/12 Matt J
11/14/12 Harry Commin
11/15/12 Harry Commin
11/15/12 Matt J