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