Strange runtime complexity of eigen(...)

Specific Domains Numerics
1

Hi everyone!

I’m currently trying to look into the runtime complexity of some code which uses an eigendecomposition, and I don’t understand what I’m seeing. Reduced to an MWE, I’m doing the following:

  • Generate a random n*n Matrix{ComplexF64}
  • Measure the runtime of eigen() applied to this matrix
  • Plot this as a function of n

(Code at the end of this post)

From Wikipedia (Eigenvalue algorithm - Wikipedia), I expect this to scale as O(n^3), since I’m getting eigenvectors as well. However, the data I get seems to follow a O(n^2) scaling - why is that?

eigenscaling

using LinearAlgebra
using Plots

ns = 50:50:500
walltimes = Float64[]

A = rand(ComplexF64, 10, 10)
println(@elapsed vals, vecs = eigen(A))
println(vals, vecs)

function measure(n::Int)
    t = 0.0
    for i in 1:10
        B = rand(ComplexF64, n, n)
        t += @elapsed eigen(B)
    end
    return t / 10
end

walltimes = measure.(ns)

plot(ns, walltimes, xscale=:log10, yscale=:log10, marker=:circle, label="Eigen", legend=:topleft)
plot!(ns, walltimes[end] * (ns / maximum(ns)) .^ 2, label="O(n^2)")
plot!(ns, walltimes[end] * (ns / maximum(ns)) .^ 3, label="O(n^3)")
savefig("eigenscaling.png")
2

It’s O(n^3) even if you’re just computing eigenvalues. You’re probably not seeing it because (a) you didn’t go to large enough n and (b) you didn’t turn off multi-threading (which complicates benchmarking because larger sizes benefit from more threads).

See e.g. these benchmarking examples: Complexity of Matrix Operations

3

eigenscaling

Using slightly larger matrices, you can see the trend emerging

1 Like