Are element-wise inequalities inherently slow and the best that I can get?

I'm trying to speed up some code for dynamic programming. The current bottleneck is checking whether a point is in a set using a half-space representation (i.e. A*x <= b). In particular, for a given A,b, I want to check many x.

For example,

A = [-1; 1];
b = [-0.1;1];
m = 1e6;
x = rand(1,m);
out = A*x <= b;

An alternative is to turn A, b into matrices using repmat such that it becomes

A_mat = repmat(A,1,m);
b_mat = repmat(b,1,m);
out_mat = all(A_mat.*x <= b_mat);

Finally, I tried this, which wouldn't reasonably be faster.

out_mat_2 = all([A_mat(1,:).*x <= b_mat(1,:);A_mat(2,:).*x <= b_mat(2,:)]);

When I run this in the time profiler, I get producing out_mat is fastest followed by out. However, in my actual code (not the MRE), I see that output_mat_2 is fastest followed by output_mat. Over 150 calls to the function containing the above code where m is about 2e5, I get the attached time profile.

Why would out_mat_2 ever be faster than out_mat and is there a different way to do this computation that is faster than these three?

Thanks!

[Torsten]

A = [-1; 1];
b = [-0.1;1];
m = 1e6;
x = rand(1,1);
out = A*x <= b;

You know that m is not used here and that this is an unfair comparison to

A_mat = repmat(A,1,m);
b_mat = repmat(b,1,m);
out_mat = all(A_mat.*x <= b_mat);

?

[Sean Anderson]

whoops, I switched between l and m and didn't update that earlier chunk of code. Let me fix that, thanks!

EDIT: updated post. Cheers

Answer 1

[Nipun]

Hi Sean,

I understand that you are trying to figure out a faster way to check if an element belongs to a set using half-space representation. Based on your inputs, I can see that the profiler shows that slicing matrices and comparing row wise is faster. I assume that you are trying to find the fastest way of solving half space representations.

Firstly, I should mention that MATLAB stores matrices in a column first order. In your code, all matrices are basically row - vectors. For speed up, consider taking it's transpose to get a column vector. Based on hardware implementations and MATLAB implementation, column operations should be quite faster than row operations.

A_1 = [-1; 1]';
b_1 = [-0.1;1]';
x_1 = x';
tic;
for i=1:150
out_1 = x_1*A_1<=b_1;
end
toc

In the above code, I take the transpose and run the computation for 150 iterations. The time elapsed is 0.6 seconds. If I convert this to a matrix based input code, I get the following:

A_mat_1 = A_mat';
b_mat_1 = b_mat';
tic;
for i=1:150
out_mat_1 = all(x*A_mat_1 <= b_mat_1);
end
toc;

Time elapsed reduces to 0.2 seconds. Hope this helps.

Regards,

Nipun