Number of flops in Gaussian Elimination Matlab code

Question

I am having a hard time trying to understand why this Matlab code to perform Gaussian Elimination without pivoting using LU factorization takes (2/3) * n^3 flops. (FLOPs: floating point operations and not FLOPS: floating point operations per second)

function x = GaussianElimination(A,b)

n = length(b);
for k = 1:n-1
    for i = k+1:n
        mult = A(i,k)/A(k,k);
        A(i,k+1:n) = A(i,k+1:n)-mult*A(k,k+1:n);
        b(i) = b(i) - mult*b(k);
    end
end

x = zeros(n,1);
x(n) = b(n)/A(n,n);

for k = n-1:-1:1
    x(k) = (b(k) - A(k,k+1:n)*x(k+1:n))/A(k,k);
end

end

If anyone could explain to me how flops are counted for those nested loops that start at k+1 I would be grateful.

PS: I am not talking about algorithmic complexity here.

Answer 1

I finally figured it out myself.

FLOPs are counted a little different than algorithmic complexity in the sense that lower order terms are still ignored but the coefficient in front of the highest order term does matter.

In this specific example, since we ignore lower order terms, we only look at +, -, *, / operations in the triple nested loop and ignore other floating point operations in the rest of the algorithm. i.e. the following line

    A(i,k+1:n) = A(i,k+1:n)-mult*A(k,k+1:n);

• first loop runs from 1 to n
• second loop runs from k to n
• third loop runs from k to n (implicit in Matlab code with the use of :)

Thus, this line runs almost n^3 times and precisely n*n + (n-1)*(n-1) + ... + 2*2 + 1*1 times which is equivalent to (1/3)*n^3 flops when ignoring lower order terms.

However, this line has two floating point operations: a - operation and a * operation.

Therefore, this gives (2/3)*n^3.