last day (15 days later) » 

7:20 PM
0
Q: Whats wrong with my running time calculation?

NunoxicI am running a linear algebra iterative method (PCG) for solving Ax=b, the dimension of the matrix is 10000x10000. So, I did 2 preliminary analyses: Memory Analysis The size of the matrix dominates the total storage required. Thats about 1E4 x 1E4 = 1E8 elements of double precision which is ...

 
I'd be careful saying that cache doesn't help at all. Even if the data doesn't fit in cache, any amount of locality will still help drastically.
 
But then, the time for floating point operations is dominant here. Even if I assume that I have a GB worth of cache, I still have 1000 s worth of computation.
 
You do realize that a modern computer can do way more than 1 operation/cycle?
 
@Mysticial How do I account for that? I have tried reading my processor's (i3 330M) documentation but couldn't find out how to account for this. What would it be called?
 
It depends on how well the code is written. A Core i3 can do up to 4 (double-precision) floating-point operations per cycle. Then you have to account for the number of cores. And I highly suspect that your equation is wrong - as the implementation is probably using something with fewer operations.
 
7:20 PM
@Mysticial, I specifically made sure that I was using a single thread. Regarding the PCG implementation, its not possible to proceed without a MatVec and that is necessarily O(N^2). If i3 does 4 DP operations / sec, the time would fall to 250 seconds. That is still an error of 100%. Where else could I have gone wrong?
 
Don't forget that the big-O is only asympototic. It can vary wildly for smaller sizes. I'd go into to more detail, but I'm having trouble following your math.
 
@Mysticial
You have a minute to discuss this?
 
make it quick though
 
OK. For N^2 operations with constant 50, I would need 50 E8 operations in total per iteration,
thats a total of 450 x 50E8 for 450 iterations
and then I divide by clockrate 2.13e9 to give \approx 1000 seconds of running time
 
why would you think the constant is necessarily 50?
behavior of small sizes doesn't necessarily translate to large sizes - especially on modern computers
 
7:25 PM
No, the constant has been calculated by running the code for sizes from 8000 to 19000
i.e 8k x 8k to 19k x 19k
and the plot of the points is fairly straight
n = 8000:500:19001
for it=n
tic;rand(it,it)*rand(it,1);

t_mv(c)=toc;

c=c+1;

end

w=polyfit(n.^2,t_mv*2.13E9,1);

mv(big)=w(1);
 
No, I meant that your 50*10^8 is probably a lot smaller than you think it is.
 
This was my MATLAB code
 
It's matlab. They use optimized libraries that reduce the amount of operations that are needed. plain and simple
 
How would I find out the real number in that case?
 
You can't unless you hook it up to a profiler that can read hardware counters.
 
7:28 PM
I tried searching for them but none of them gave flop counts. What you are saying is my leading constant could be lesser (leading to lesser number of total operations required), is that correct?
 
correct
 
Is there any other way to approximate (theoretically) the run time of an algorithm?
 
make a graph and extrapolate... anyways, I gotta go
 

last day (15 days later) »