Understanding wall time jitter in MATLAB computations

Question

I am studying a research paper on iterative methods to compute generalized inverses of an arbitrary matrix $A$. I am studying the following iterative method:

$$Y_{k+1} = Y_{k} + Y_{k}(I - AY_{k}),$$ given an initial approximation $Y_{0}$. I am having difficulties understanding how to measure the computational time taken by this method over 15 iterations. I made MATLAB code and used tic and toc to compute this. But every time I am clicking on run program it is showing me different computational time values.

Why is the computational time different on different runs?

Here is my code

A = [1 4 0 
     2 3 0 
     2 0 1
     0 0 0]; % given matrix

Y0 = [0.0101 0.0202 0.0202 0
      0.0404 0.0303 0      0
      0      0      0.0101 0]; % initial approximation

I = eye(4);     

tic

for n=1:15    
    Y1 = zeros(4,3);
    % compute sequence of approximations
    Y1 = Y0+Y0*(I-A*Y0) 
    Y0 = Y1;
end

toc

I think you'd get more consistent timings on larger matrices. With a smallish matrix 15 iterations might not take much time for the computation in comparision with "overhead", but the situation should improve with a larger example. — hardmath, Aug 27 '12 at 12:46
@hardmath How much size at least? What's the problem with smaller size matrix? Could you please reply me? — Srijan, Aug 27 '12 at 12:49
Why not try a series of examples, in which you double the size of the matrix A, then double it again, etc. Pretty quickly you'll see that Matlab is spending a considerable amount of time doing the matrix multiplication, etc. in your formula, and proportionately less on such overhead tasks as checking the keyboard, function calls, etc. Matlab is written to perform the arithmetic of matrix computations very efficiently, so you really need to pose difficult tasks to see it working hard at just that. — hardmath, Aug 27 '12 at 12:52
@hardmath Thanks for replying me. But if I want to work with smaller order matrix Couldn't I compute computational time? — Srijan, Aug 27 '12 at 12:55
Well, tell us what results you are getting! You merely allude to not getting consistent results, and I suspect the issue is that the timing of the small example is too brief for the tic/toc mechanism to give precise values. If you are not working with varying sizes of problems, it's not clear why you are interested in timings. Surely the 15 iterations you tested must complete faster than you could measure with a stopwatch. — hardmath, Aug 27 '12 at 13:03
@hardmath These are the timings that I am getting (.001019, 0.001034, 0.001044, 0.001028). I don't have any problem with larger order matrix. I don't have much knowledge about matlab. I got this problem so I asked. — Srijan, Aug 27 '12 at 13:15
If your computational times are varying, why not find the mean and variance of the times. Since your times are not widely spread (as it appears in the previous comment), the mean should be a reasonable estimate. — Paul, Aug 27 '12 at 14:16
Also, tic/toc only has precision down to a millisecond. Your entire runs are completing faster than you can possibly measure with those functions. The small bit of variation is completely meaningless. — Godric Seer, Aug 27 '12 at 15:28

Stefano M · Accepted Answer · 2012-08-28T07:30:13.543

There are several issues in your code.

There is no semi-colon after the Y1 = Y0+Y0*(I-A*Y0) statement. In fact you are timing the screen output of Y1, not the computational time
The iteration should be written as
```
for n=1:15    
    Y0 = Y0+Y0*(I-A*Y0);
end
```
allocation of Y1, assignment to Y1, and then to Y0 are useless.
Finally you could even simplify further Y0 = 2*Y0 - Y0*(A*Y0) ;

Edit

After applying these modification you will see that the measured time becomes very small ($\approx 100 \, \mathrm{\mu s}$ on my machine). Usually for such small elapsed times the tic, toc approach is not considered accurate.

Timing small snippets of code is rather difficult, so please consider my answer here only a simple hint, not an accurate and in depth answer.

Essentially you have to measure a bigger interval (about one second): if you are interested in estimating the time of a single iteration, you can simply increase the number of iterations in your loop and divide the total time by the iteration number. (To be more precise you should also time an empty loop, to estimate the overhead associated to the loop itself.) If you are interested in estimating the total time (init Y0, loop overhead, and 15 iterations) you should repeat your for, end a sizable number of times, and measure the total time. Here is an example adapted from the MATLAB help toc.

REPS = 1000; minTime = Inf; nsum = 10;
tic;
for i=1:REPS
  tstart = tic;
  % init Y0
  Y0 = ...
  for n=1:15    
      Y0 = Y0+Y0*(I-A*Y0);
  end
  telapsed = toc(tstart);
  minTime = min(telapsed,minTime);
end
averageTime = toc/REPS;

You have to experiment with both the number of iterations (first approach) and REPS (second approach) to find a sensible number, in which the tic, toc errors are small enough.

Thanks for valuable suggestions. I applied them. Sorry I didn't understand why to increase number of iterations from 1:15 to 1:1500 while it is taking only 15 iterations for convergence. — Srijan, Aug 28 '12 at 03:23

Understanding wall time jitter in MATLAB computations

1 Answers1