14
$\begingroup$

I am comparing two iterative methods for inverting random square matrices. Since the matrices are random, every test case takes both different amounts of iterations and different elapsed times. My question is, on top of mean CPU time, is the mean value of iterations taken by both the methods useful information for comparing the methods.

$\endgroup$
  • 4
    $\begingroup$ I reworded your question to hopefully make it more clear. Please make sure that I did not change your meaning in any way. $\endgroup$ – Godric Seer Jun 12 '13 at 15:27
  • 3
    $\begingroup$ @GodricSeer Your edit has improved my question. Thanks $\endgroup$ – srijan Jun 12 '13 at 16:35
12
$\begingroup$

In general, both methods of performance comparisons have their place.

  • Comparing cpu time is in a sense the most interesting metric, because at the end of the day you are really interested in which of the methods is faster. (But make sure that the termination criteria are comparable; e.g., that both methods yield an approximation with the same accuracy). The drawback is that this only tells you which method (and more importantly, which implementation) is faster on the machine you performed the tests on. There is no guarantee that a different machine with different architecture or software would pick the same winner.

  • Comparing iteration numbers, on the other hand, is machine independent, but potentially misleading if the two methods have very different iterations - in this case the method with fewer but more expensive iterations might not be preferable (e.g., Newton vs. gradient methods for optimization if you only need very low accuracy).

So, yes, it makes sense to give both numbers [1], and I've frequently seen it done in publications. There is also a third option:

  • Comparing numbers of elementary operations. If both iterations consist of the same kind of suitably expensive operation, but require a different number (possibly not even the same number in each iteration), it makes sense to count the total number of these operations. In your case, a likely candidate would be matrix-vector or matrix-matrix multiplications.

[1] Definitely present statistics over multiple runs; if you show means, don't forget to include standard deviations as well.

$\endgroup$
  • 5
    $\begingroup$ Don't just take means! If you have enough test points with random inputs, plot a distribution. $\endgroup$ – Bill Barth Jun 12 '13 at 16:55
  • 1
    $\begingroup$ @BillBarth - good point, although that might not always be feasible; but giving standard deviations together with the mean should always be possible. In fact, which statistics to present for reporting performance sounds like an excellent follow-up question. $\endgroup$ – Christian Clason Jun 12 '13 at 17:06
  • $\begingroup$ @BillBarth You made a good point. But, I am using several test matrices in increasing order. For such cases it is not feasible to plot the distribution since then I have to plot the distributions for all other test matrices. That is why I wanted to tabulate them. Thanks for your comments. $\endgroup$ – srijan Jun 12 '13 at 18:31
  • 1
    $\begingroup$ @srijan: You'll have the data, you should plot histograms for yourself wherever you can. You don't have to publish them all, but I promise you that a graph of the distribution will tell you more than a sea of numbers or just the averages ever will. $\endgroup$ – Bill Barth Jun 13 '13 at 2:54
  • $\begingroup$ I would include the execution time per iteration. Since each matrix is different, you can have different number of iterations with different execution times. Together with what @Cristian said, execution time per iteration would be usefull. $\endgroup$ – jbcolmenares May 10 '14 at 4:15
4
$\begingroup$

I find the number of iterations to be a misleading metric because it suggests "speed" when it is not. For a simple example of comparing a few different preconditioners that shows this difference, see here: http://www.dealii.org/developer/doxygen/deal.II/step_6.html#Possibilitiesforextensions

$\endgroup$
  • $\begingroup$ Thanks for the answer. I am not able to understand this line 'number of iterations to be a misleading metric because it suggests "speed" when it is not'. The example that you have suggested is somewhat difficult for me to understand. $\endgroup$ – srijan Jun 12 '13 at 16:44
  • $\begingroup$ What I'm saying is that we often present "number of iterations" to be equivalent to "CPU time used", implying that a method that requires fewer iterations is also faster. But that isn't true, as shown by the figures I linked to. $\endgroup$ – Wolfgang Bangerth Jun 12 '13 at 21:55
  • $\begingroup$ Now, I fully understood your point. Same I have observed with the newtons method for approximating inverse of a square matrix. A s the order of method increases, initially cpu time as well as number of iterations both decreases but as the order increases cpu time start increases even though number of iterations decreases. Thank you very much for your answer. $\endgroup$ – srijan Jun 13 '13 at 1:28
2
$\begingroup$

In case it's not clear in the other answers, what number-of-iterations is good for is big-O arguments.

It's not good for absolute speed, because that depends on the average-time-per-iteration, which may differ between methods by a large factor.

For example, there is a tendency to ignore the cost of calculating array indices, and that may well account for a large fraction of the CPU time.

ADDED: Also, as I've pointed out elsewhere, for every invocation of the method there is typically a setup cost. Then if the matrices are typically not very large, that setup cost can itself account for a large fraction of CPU time (such that removing it would make a large difference in speed).

$\endgroup$

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.