Why would A \ b grow with O(n^2)?

Hello,

I was curious how long it would take my laptop to solve Ax = b for square A as a function of the problem size. I tried to profile it using BenchmarkTools:

ns = [1,2,3,5,7,10,20,30,50,70,100,200,300,500,700,1000,2000,3000,5000,7000,10000]
ts = Array{Float64}(undef, length(ns))
for (i,n) in enumerate(ns)
    b = @benchmark $(rand(n,n)) \ $(rand(n))
    ts[i] = median(b).time
end

and found that it seems to grow quadratically, in O(n^2). I expected it to grow in O(n^3).

image
The gray trendline is n^2 / 10^7.

I’m running Julia single-threaded and the matrices are dense, so I am not sure why this would be. Is there something wrong with how I am benchmarking it? Is there some property of positive dense matrices that I am missing? Is it actually using multiple threads under the hood?

Thank you!

I think this is just using BLAS so unless you set BLAS threads to 1 it’s probably multi threaded.

2 Likes

I think you are right. LinearAlgebra.BLAS.get_num_threads() is telling me BLAS can use up to 8 threads.

I figured out how to set the number of BLAS threads. Will verify that. Thank you!

The cost is probably dominated by lu, which in practice scales much better than O(N^3) up to extremely large sizes.

4 Likes

Setting BLAS to use 1 thread is giving me O(n^3) scaling starting around n=200. Thank you!

Selection_734

4 Likes

Relevant article by Nick Trefethen: https://people.maths.ox.ac.uk/trefethen/sept23lms.pdf

3 Likes