Does vectorization change the complexity?

Question

I wrote a code in MATLAB with the complexity O(n^3). I removed one of the loop and used the vectorized form instead. As a result the run time decreased. I understand in general the vectorization enhances the performance. What I am not sure is that I assumed the vectorization does not change the complexity.

I did some experiments as follows:

When I increased the input size by factor of 2 the run time increased by about a factor of 2.5(I expected by about factor of 8).

Now I am not sure if my initial assumption(which is the vectorization does not change the complexity.) is valid. Does any one have an insight?

Thank you.

It depends on the function you use. For instance using a function such as bsxfun increases the speed while it is just a for-loop written as c++/mex file. In such cases, I do not think vectorizing the code changes the complexity. — NKN
Thanks for your insight. Do you know why the run time is not increased proportionate (when increases in input size)? When I used for loop it was close to expected increase but when I vectorized it was not close. I used MATLAB. I just gave a range to index(rather than on column) and remove the for loop.mathworks.com/help/matlab/matlab_prog/vectorization.html — Crimson
@Crimson Well with vectorized approaches, you are processing more data per period of time, so there's lot more data transfers, which might be affected by the memory bandwidth, etc. So, I don't think it would be a linear scale. Vectorization vs Performance vs Memory is an unique game. I am not too conversant with the complexity definitions though. — Divakar
Thanks for the comment . So it seems it related to enhancing the load and store operations and data transfer rather than a change in complexity. — Crimson
I'm mostly guessing, so only comment, but here goes. I don't think that vectorization should change complexity. I.e. I'd think that the vectorized version of O(n^3) code should also be O(n^3), but with a much smaller prefactor. But here's the catch: this is only asymptotic behaviour (so you need very large n to clearly see this), and there's usually a lot of fluff in your code (overhead from the point of view of your vectorization) that scales differently. So you really need huge n and scaling across multiple orders of magnitude to say anything empirical about complexity. — Andras Deak

mpaskov mpaskov · Accepted Answer · 2016-10-12T20:36:40

In the very general way I think the difference is actually throughput (latency) vs number of operations (complexity). If you would build a very dedicated ASIC for you algorithm you would have to n^3 operations. By vectorizing you are saying that some of these operations can be performed independently from each other in parallel. Matlab and current processors are more clever and can do certain operations in 'parallel' e.g. a 64bit processor could do 2-32bit summations 4-16bit etc.

Think of two algorithms both in O(n^3), a where each operation must be done complete independent (you can vectorize this algorithm) and b the other where they must be series (you can not vectorize it). Special hardware for each of those would both require n^3 operations. However, by using more hardware/gates for a you can finish the task in as quick as 1 clock cycle, while for b more hardware/gates does not help you and the task will take n^3 clock cycle.

EDIT:

Some code to illustrate the vectorization speed, although complexity (#operation) would not increase

clear variable;

Iterations = 100;
n = 2^20;
a = randi(100,[1,n]);
b = randi(100,[1,n]);

profile on;
for loop=1:Iterations
    % Full vector approach
    vector = a*b.';

    % Partial vector approach
    vector2 = sum(a.*b);

    % Direct mathematical approach
    serial = 0;
    for id=1:n
        serial = serial + a(id)*b(id);
    end
end
profile viewer;

now technically matlab has some extra overhead per operation like checking if the operation makes sense etc, thus slowing for loop significantly. But in general this is just an example to illustrate a trend.

Does vectorization change the complexity?

1 Answers