Benchmark on dense overdetermined random matrices

using RandomLinearAlgebraSolvers, Random, LinearAlgebra, SparseArrays
Random.seed!(1234)

MersenneTwister(1234)

Benchmark of methods to solve Ax = b with A a randomly generated m x n matrix, and b = A * xref.

using DataFrames, Printf, SolverBenchmark, Stopping

N = 5 # number of problems
m, n = 10000, 100 # size of A: m x n

(10000, 100)

Names of solvers:

names = [:RandomizedKaczmarz, :RandomizedBlockKaczmarz, :RandomizedCD]

3-element Vector{Symbol}:
 :RandomizedKaczmarz
 :RandomizedBlockKaczmarz
 :RandomizedCD

#Initialization of the DataFrame for n problems.
stats = Dict(name => DataFrame(
         :id     => 1:N,
         :nvar   => zeros(Int64, N),
         :status => [:Unknown for i = 1:N],
         :time   => NaN*ones(N),
         :iter   => zeros(Int64, N),
         :score  => NaN*ones(N)) for name in names)

Dict{Symbol, DataFrames.DataFrame} with 3 entries:
  :RandomizedBlockKaczmarz => 5×6 DataFrame…
  :RandomizedCD            => 5×6 DataFrame…
  :RandomizedKaczmarz      => 5×6 DataFrame…

for i=1:N

  A = 100 * rand(m, n)
  xref = 100 * rand(n)
  b = A * xref

  x0 = zeros(size(A,2))
  la_stop = RLAStopping(A, b, max_iter = 100000, rtol = sqrt(eps()), atol = sqrt(eps()))
  for name in names

    #solve the problem
    reinit!(la_stop, rstate = true, x = x0, res = similar(b))
    la_stop.meta.start_time = time()
    @time eval(name)(la_stop, r = 80, is_zero_start=true)
    sol = la_stop.current_state.x

    #update the stats from the Stopping
    stats[name].nvar[i]   = n
    stats[name].status[i] = status(la_stop)
    stop_has_time = (la_stop.current_state.current_time != nothing)
    stats[name].time[i]   =  stop_has_time ? la_stop.current_state.current_time - la_stop.meta.start_time : time() - la_stop.meta.start_time
    stats[name].iter[i]   = la_stop.meta.nb_of_stop
    stats[name].score[i]  = norm(la_stop.current_state.current_score, Inf)

  end

end

  4.177661 seconds (1.38 M allocations: 2.319 GiB, 3.70% gc time, 16.67% compilation time)
  3.461385 seconds (6.97 M allocations: 384.682 MiB, 4.17% gc time, 93.79% compilation time)
  0.405600 seconds (634.05 k allocations: 30.086 MiB, 9.38% gc time, 69.70% compilation time)
  3.642128 seconds (193.15 k allocations: 2.230 GiB, 11.08% gc time)
  0.191112 seconds (1.80 k allocations: 25.871 MiB, 1.59% gc time)
  0.112197 seconds (122.99 k allocations: 1.877 MiB)
  3.388028 seconds (198.22 k allocations: 2.289 GiB, 3.11% gc time)
  0.196151 seconds (1.85 k allocations: 26.589 MiB)
  0.114658 seconds (124.93 k allocations: 1.906 MiB)
  3.251137 seconds (192.43 k allocations: 2.222 GiB, 2.96% gc time)
  0.184378 seconds (1.75 k allocations: 25.152 MiB)
  0.115335 seconds (126.67 k allocations: 1.933 MiB)
  3.256168 seconds (190.53 k allocations: 2.200 GiB, 2.72% gc time)
  0.201888 seconds (1.85 k allocations: 26.589 MiB, 1.52% gc time)
  0.117429 seconds (128.14 k allocations: 1.955 MiB)

for name in names
    @show name
    @show stats[name]
end

name = :RandomizedKaczmarz
stats[name] = 5×6 DataFrame
 Row │ id     nvar   status   time     iter   score
     │ Int64  Int64  Symbol   Float64  Int64  Float64
─────┼───────────────────────────────────────────────────
   1 │     1    100  Optimal  4.18271  15015  1.49012e-8
   2 │     2    100  Optimal  3.64192  14858  1.42609e-8
   3 │     3    100  Optimal  3.3878   15248  1.4843e-8
   4 │     4    100  Optimal  3.25093  14802  1.47847e-8
   5 │     5    100  Optimal  3.25596  14656  1.46392e-8
name = :RandomizedBlockKaczmarz
stats[name] = 5×6 DataFrame
 Row │ id     nvar   status   time      iter   score
     │ Int64  Int64  Symbol   Float64   Int64  Float64
─────┼────────────────────────────────────────────────────
   1 │     1    100  Optimal  3.45584      37  9.45874e-9
   2 │     2    100  Optimal  0.185861     36  1.00117e-8
   3 │     3    100  Optimal  0.190756     37  9.69158e-9
   4 │     4    100  Optimal  0.178815     35  1.16997e-8
   5 │     5    100  Optimal  0.196617     37  6.17001e-9
name = :RandomizedCD
stats[name] = 5×6 DataFrame
 Row │ id     nvar   status   time      iter   score
     │ Int64  Int64  Symbol   Float64   Int64  Float64
─────┼────────────────────────────────────────────────────
   1 │     1    100  Optimal  0.405579  15573  1.48983e-8
   2 │     2    100  Optimal  0.112179  15374  1.4407e-8
   3 │     3    100  Optimal  0.11464   15616  1.48257e-8
   4 │     4    100  Optimal  0.115318  15834  1.4662e-8
   5 │     5    100  Optimal  0.117413  16018  1.42925e-8

or run a performance profile:

using Plots
gr()
cost(df) = (df.status .!= :Optimal) * Inf + df.time
p = performance_profile(stats, cost)