3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Have you considered measuring execution time for a range of input sizes (the $n$ in $O(n)$) and plotting that to see how execution time scales with your input? $\endgroup$ – Aron Ahmadia May 16 '13 at 22:33
  • $\begingroup$ @AronAhmadia Yes. But I'm trying to look at the mathematical side of it $n\rightarrow\infty$ $\endgroup$ – JNF May 17 '13 at 5:17
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Pedantic comment - the function name was flops, not flop. +1 anyway. $\endgroup$ – user840 May 27 '13 at 1:32
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. Is there a way to know regarding find, or even sin? $\endgroup$ – JNF May 17 '13 at 5:22
  • 1
    $\begingroup$ @JNF Instead of C=A*B, you can perform any operation that you want. $\endgroup$ – Nico Schlömer May 17 '13 at 9:16
  • $\begingroup$ There is a function timeit on MATLAB's file exchange that does measuring of execution time for statements in a robust way. However, without providing the data for the plot. $\endgroup$ – Jan May 17 '13 at 10:02
  • $\begingroup$ @Nico I got that. Just wondering if I could skip the testing and find it all officially written down. $\endgroup$ – JNF May 19 '13 at 5:07
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think this is only an option for the latest version of matlab (2013), no? $\endgroup$ – Paul May 26 '13 at 2:56
  • 1
    $\begingroup$ I have just checked Matlab2008b. There you have the profiler and it also pins down the lines where the most execution time was spent. So, to check small scripts, I think everything is there already in 2008. $\endgroup$ – Jan May 27 '13 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.