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