Timing and flop counts¶
using FundamentalsNumericalComputation
n = 6
A = randn(n,n)
x = ones(n)
y = zeros(n)
for i = 1:n
for j = 1:n
y[i] = y[i] + A[i,j]*x[j] # 2 flops
end
end
Each of the loops implies a summation of flops. The total flop count for this algorithm is [ \sum_{i=1}^n \sum_{j=1}^n 2 = \sum_{i=1}^n 2n = 2n^2. ] Since the matrix \(A\) has \(n^2\) elements, all of which have to be involved in the product, it seems unlikely that we could get a flop count that is smaller than \(O(n^2)\).
Let’s run an experiment with the built-in matrix-vector multiplication. We assume that flops dominate the computation time and thus measure elapsed time.
n = 400:400:4000
t = zeros(size(n))
for (i,n) in enumerate(n)
A = randn(n,n)
x = randn(n)
t[i] = @elapsed for j = 1:10; A*x; end
end
The reason for doing multiple repetitions at each value of \(n\) is to avoid having times so short that the resolution of the timer is a factor.
pretty_table((n=n,t=t),["size" "time";"" "(sec)"],backend=:html)
| size | time |
|---|---|
| (sec) | |
| 400 | 0.004014938 |
| 800 | 0.000561443 |
| 1200 | 0.003525531 |
| 1600 | 0.009102276 |
| 2000 | 0.015614555 |
| 2400 | 0.022680646 |
| 2800 | 0.031008941 |
| 3200 | 0.039923662 |
| 3600 | 0.049990345 |
| 4000 | 0.061064288 |