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.
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 , 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.
 Definitely present statistics over multiple runs; if you show means, don't forget to include standard deviations as well.
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
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).