MATLAB: Speed up a matrix multiplication with one logical matrix

speed up matrix multiplication

I have a matrix multiplication P*C, where these two matrices change their values and their matrix dimensions during each step of the "while" loop.
The P matrix is a double matrix, while the C matrix is a logical matrix, with all values equal to 1 or 0.
The code is the following:
NU=2000;
NC=100;
P = rand(NU,NU);
C = zeros(NU,NC);
UFL = false(NU,1);
ID_vector = [1:NU]';
C(1,1) =1;
UFL(1) =1;
while ne(sum(UFL),NU)
    ID_NA = ID_vector(not(UFL));
    ID_AS = ID_vector(UFL);
    A = P(ID_NA,ID_AS)*C(ID_AS,:); %matrix multiplication to speed up    
    [~,IDX] = max(max(A,[],2));
    USX = ID_NA(IDX);
    [~,COX] = min(A(IDX,:));
    C(USX,COX) = 1;
    UFL(USX) = true;
end
There is a way to speed up this matrix multiplication?
Considering that binary nature of the matrix C, I think that the matrix multiplication should be speed up interpreting the multiplication as a selective sum, but I am unable to write the correct code.

Best Answer

In practice the matrix multiplication is likely to be fastest. Matrix multiplication of large enough matrices is delegated to high performce multithreaded libraries that use all of your cores. In order to form "selective sum" then you would have to find() and indexing, or else use logical indexing, and the overhead required to do that work conditionally is more than the overhead of just going ahead and doing the calculation.
See the below benchmark
function logmult
rng(655321);
N = 50;
S = 10000;
V = rand(1,S);
L = rand(1,S) < .2;
F1 = @() fun1(V,L);
F2 = @() fun2(V,L);
F3 = @() fun3(V,L);
t1 = zeros(1,N);
t2 = zeros(1,N);
t3 = zeros(1,N);
for K = 1 : N; t1(K) = timeit(F1,0); end
for K = 1 : N; t2(K) = timeit(F2,0); end
for K = 1 : N; t3(K) = timeit(F3,0); end
x = 1  : N;
plot(x, t1, 'b', x, t2, 'g', x, t3, 'k')
legend({'matrix multiply', 'logical idx sum', 'find sum'})
end
function out = fun1(V,L)
    out = V*L.';
end
function out = fun2(V,L)
    out = sum(V(L));
end
function out = fun3(V,L)
    out = sum(V(find(L))); %#ok<FNDSB>
end
Related Question