I 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 approximately 0.8 GB of data. The number of iterations required for convergence was 450. Since this won't fit in cache, I assume no cache benefits, that would mean 450 x 0.8 = 360 GB of data transfer. With a memory bandwidth of 10 GB/s, thats approximately 36 seconds for memory transfers.
- Flop Analysis
I calculated that I will be carrying out 1 matrix vector (dominant operation) per iteration for 450 iterations. That is
cN^2 operations/iterations x 450 iterations =
450c N^2 operations with a 2.13GHz processor (ensured to work on a single processor only). That is
21.12c for N=10000.
To find c, I carried out MatVecs for all sizes from 1 to 19000, plotted the graph for No. of Operations vs (Dimension)^2 (Operations = slope x Dim^2) where
No. of Operations = Time x 2.13 GHz. I used the slope of this (linear) graph as
. Which came out to be
Thus, total time = 21.12c = 1000 seconds.
Thus, assuming both memory transfer and operations happen concurrently, theoretically, it should take 1000 seconds.
But in reality, the code took 120 seconds maximum. Where did I go wrong? My calculation is fairly off.