# Strange runtime complexity of eigen(...)

**URL:** <https://discourse.julialang.org/t/strange-runtime-complexity-of-eigen/98392>\
**Category:** Numerics\
**Created:** [May 5, 2023, 4:41pm UTC](https://discourse.julialang.org/t/strange-runtime-complexity-of-eigen/98392 "2023-05-05T16:41:52Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![mritter](https://avatars.discourse-cdn.com/v4/letter/m/e274bd/32.png) [@mritter](https://discourse.julialang.org/u/mritter)\
**Post date:** [May 5, 2023, 4:41pm UTC](https://discourse.julialang.org/t/strange-runtime-complexity-of-eigen/98392/1 "2023-05-05T16:41:52Z")

</div>

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](https://en.wikipedia.org/wiki/Eigenvalue_algorithm)), 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](https://global.discourse-cdn.com/julialang/original/3X/8/d/8de9513135005976a584d193e1d96b43ed43c784.png)

```julia
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")

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [May 5, 2023, 4:55pm UTC](https://discourse.julialang.org/t/strange-runtime-complexity-of-eigen/98392/2 "2023-05-05T16:55:23Z")

</div>

> [@mritter](#):
>
> 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?

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](https://nbviewer.org/github/mitmath/1806/blob/fall22/notes/Complexity.ipynb)

---

<div class="post-metadata">

**Author:** ![jishnub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jishnub/32/33620_2.png) [@jishnub](https://discourse.julialang.org/u/jishnub)\
**Post date:** [May 5, 2023, 5:18pm UTC](https://discourse.julialang.org/t/strange-runtime-complexity-of-eigen/98392/3 "2023-05-05T17:18:16Z")

</div>

![eigenscaling](https://global.discourse-cdn.com/julialang/original/3X/0/e/0e16398e818f93aae6c1860259d0f917d1b752d8.png)

Using slightly larger matrices, you can see the trend emerging