A few of the iterative matrix algorithms (CG,GMRES etc.) I have authored are acting rather funny. They converge to the right answers but take abnormally long time to run. I am in the process of finding out why.
One of the first steps I thought is to find out the algorithmic complexity of the methods. For instance, I need to know if CG is indeed taking $O(N^2)$ as expected and similar.
How do I find out the exact algorithmic complexity of the methods? (I am looking for some way for to get the exact bound on the algorithm like $N^2 + 5N$).
And even before that, is this a valid first step for improving performance?
As of now, I am concentrating on single core performance (which by itself is pretty bad right now).
I am also looking at trying to determine the memory accesses. Is there any Free software (not necessarily Open Source) which would allow me to do so in a nice GUI? I use VTune for parallel but it is useless for serial.
I have tried googling but all algorithm problems end up in the search/sort portion of computing which is quite different from iterative matrix algorithms.
I have tried solving the algorithm for matrix sizes from 1 to 1000, plot the graph of average time taken for that size and curve fit it (quadratic). But I don't seem to be getting anywhere through this.
EDIT: Just to be clear, I want to verify that the complexity of the algorithm in practice is the same as the one predicted by theory. I want to verify that my algorithm of say, Matrix-Vector is indeed $O(N^2)$.
Further, I don't mind knowing per iteration complexity.