What is the Complexity of MATLAB operations

Question

I'm trying to analyze the complexity of MATLAB code I wrote.

I'm trying to figure out how much (in terms of $O$ or $\Theta$) to give functions like find, matrix * operator, matrix .* operator, and others.

Is there a way to calculate this? Or a reference?

Answer 1

Matlab 6 used to have a function flop to count them, but it was removed in later versions. The main reason was technical (they switched to LAPACK as the linear algebra core, and it did not return a flop count).

Today this option isn't available anymore; there is no easy equivalent, so if you wish to have one you'll have to count them yourself using the definition and your best guess on how these operations are implemented. It should be easy to come up with big-O estimates; not always so to pin down the exact constant. In the examples you ask for it is easy to guess what Matlab is doing and counting the operations by hand, but it isn't always so.

In some cases, such as the QR/Francis algorithm for computing eigenvalues (eig), this "constant" will depend on the specific matrix. Appendix C of Higham's Function of Matrices contains good reference values for some dense linear algebra operations. However, the real answer depends on the details of Matlab and LAPACK implementation, which is ultimately unknown since the former is closed source, and it will often change from version to version.

In addition, let me point out that the answer depends on how you define $O$ / $\Theta$ complexity. A common choice in most theoretical papers is "arithmetic operations such as sums and products count 1, everything else is free" (sometimes called flop count). With this definition, however, find costs zero, since it makes a bunch of comparisons but no true arithmetic operation. To play devil's advocate, you can even replace a floating point operation with a bunch of comparisons and assignments. So there are plenty of reasons to think that it is not a good choice.

For a less contrived example, consider Gaussian elimination with complete pivoting: it has the same flop-count cost as partial pivoting, but it involves $O(n^3)$ comparisons rather than $O(n^2)$, and these comparisons increase its actual cost.

Moreover, the execution time on a modern computer does not depend (only) on flops anymore. Details such as memory layout, cache misses, branch prediction have a large impact. There is no easy way to tell how long an operation will take, apart from running it and measuring the time. Check out this thread for an illuminating example. There is a whole research area on how to reduce "hidden costs" such as memory access in linear algebra operations; check for instance the section "communication-avoiding algorithms" on Jim Demmel's home page.

The performance of Matlab itself is another can of worms. Matlab is an interpreted language, and it does lots of additional work and bookkeeping between the lines. If you use Matlab profiler to check which instructions take the most time, you'll often find that the culprits are surprisingly unusual lines such as memory allocations, comparisons, or calls to functions which do almost nothing. Merely putting a function in a namespace or a class can have a huge impact on its execution time. A JIT compiler (Matlab accelerator) optimizes some tight cycles, but since it is itself closed-source and continuously evolving, it's impossible to predict if and when it will kick in. The Mathworks explicitly refuse to provide an interface to tell if a function has been JIT-compiled or not.

Answer 2

The cost of standard operations like find-and-replace, maxtrix-matrix multiplications and elementwise matrix-matrix multiplications is well-known: Check out the corresponding wiki site.

If you'd really like to know what your MATLAB installation does, you can always go ahead and measure the time, e.g.,

t = zeros(1,100);
for n = 1:100
    A = rand(n,n);
    B = rand(n,n);
    tic;
    C = A*B;
    t(n) = toc;
end
plot(t)

This may also give you some insight in cache behavior and such.

Answer 3

To check your implementation as a whole, you can use MATLAB's profiler. It is a built-in functionality that analyses your code in terms of execution time.

It provides an interface to all kind of measurements and you can dig into the results down to execution time of particular code lines.