Multiplication on the diagonal of a submatrix

I have a matrix A and two index vectors u and v of the same size. I want to compute the product of the entries on the diagonal of A(u,v). I tried prod(diag(A(u,v))). It is faster than the for loop. But A(u,v) also includes the redundant off-diagonal entries. So, I wonder if there is a more efficient way to do it.

n = 10^4; 
d = 50; 
A = rand(n); 
u = randi(n,d,1); 
v = randi(n,d,1); 
tic 
prod_1 = 1; 
for k = 1:50 
    prod_1 = prod_1*A(u(k),v(k));
end 
toc 

Elapsed time is 0.004753 seconds.

tic 
prod_2 = prod(diag(A(u,v)));
toc

Elapsed time is 0.002562 seconds.

[Stephen23]

https://web.archive.org/web/20211210143913/https://www.mathworks.com/matlabcentral/answers/1608125-multiplication-on-the-diagonal-of-a-submatrix

Answer 1

[John D'Errico]

You really want to learn better ways to time things than to use tic and toc. They are not very accurate for short times. Not too bad on moderately long times though.

But in terms of your specific problem, learn to use tools like sub2ind.

n = 1e4; 
d = 50; 
A = rand(n); 
u = randi(n,d,1); 
v = randi(n,d,1); 

prod(diag(A(u,v))) % your idea

ans = 8.4057e-20

prod(A(sub2ind([n,n],u,v))) % a better way. See they produce the same result though.

ans = 8.4057e-20

timeit(@() prod(diag(A(u,v))))

ans = 3.0279e-05

timeit(@() prod(A(sub2ind([n,n],u,v))))

ans = 9.5840e-06

So the sub2ind trick is considerably faster, here a little more than 3x faster. If the size of the submatrix were larger, then it would gain yet more because you really don't want to extract an entire submatrix, then find the diagonal elements of that sub-matrix. Of course, both are faster than the loop, but for large values of d, that loop may not be too bad. For example, if d was nearly as large as n, then the time to just allocate a matrix as large as that will be significant, and then looping is not too bad. Even then though, the sub2ind version will still be fast.

[Quang Huy Pham]

Thank you very much! Timeit and sub2ind are really helpful to me.