3
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – hardmath Aug 27 '12 at 12:46
  • $\begingroup$ @hardmath How much size at least? What's the problem with smaller size matrix? Could you please reply me? $\endgroup$ – srijan Aug 27 '12 at 12:49
  • $\begingroup$ 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. $\endgroup$ – hardmath Aug 27 '12 at 12:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Paul Aug 27 '12 at 14:16
  • 3
    $\begingroup$ 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. $\endgroup$ – Godric Seer Aug 27 '12 at 15:28
10
$\begingroup$

There are several issues in your code.

  1. 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

  2. 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.

  3. 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – srijan Aug 28 '12 at 3:23
  • $\begingroup$ @srijan see the edited answer. $\endgroup$ – Stefano M Aug 28 '12 at 7:30

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.