Benchmark on dense overdetermined random matrices

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

Random.TaskLocalRNG()

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

  3.441683 seconds (1.41 M allocations: 2.208 GiB, 4.08% gc time, 18.05% compilation time)
  3.090912 seconds (6.97 M allocations: 370.568 MiB, 4.56% gc time, 96.80% compilation time)
  0.386846 seconds (733.36 k allocations: 33.008 MiB, 19.78% gc time, 74.84% compilation time)
  3.087461 seconds (189.27 k allocations: 2.185 GiB, 9.28% gc time)
  0.097008 seconds (1.89 k allocations: 25.444 MiB, 2.88% gc time)
  0.094953 seconds (123.51 k allocations: 1.885 MiB)
  2.854447 seconds (190.02 k allocations: 2.193 GiB, 3.20% gc time)
  0.100733 seconds (1.94 k allocations: 26.132 MiB, 2.75% gc time)
  0.095013 seconds (123.50 k allocations: 1.884 MiB)
  2.831633 seconds (189.29 k allocations: 2.185 GiB, 3.06% gc time)
  0.090709 seconds (1.84 k allocations: 24.757 MiB)
  0.093717 seconds (123.55 k allocations: 1.885 MiB)
  2.777898 seconds (186.20 k allocations: 2.149 GiB, 2.91% gc time)
  0.092775 seconds (1.84 k allocations: 24.757 MiB)
  0.100888 seconds (130.08 k allocations: 1.985 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  3.44627  14294  1.46101e-8
   2 │     2    100  Optimal  3.08727  14559  1.49012e-8
   3 │     3    100  Optimal  2.85426  14617  1.46683e-8
   4 │     4    100  Optimal  2.83144  14561  1.38825e-8
   5 │     5    100  Optimal  2.77771  14323  1.429e-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.08842       38  7.18865e-9
   2 │     2    100  Optimal  0.0945191     37  7.33417e-9
   3 │     3    100  Optimal  0.0982518     38  7.39237e-9
   4 │     4    100  Optimal  0.0881829     36  1.14669e-8
   5 │     5    100  Optimal  0.0902488     36  1.28639e-8
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.386831   15047  1.46088e-8
   2 │     2    100  Optimal  0.094938   15439  1.48515e-8
   3 │     3    100  Optimal  0.0949981  15437  1.44148e-8
   4 │     4    100  Optimal  0.0937018  15444  1.48318e-8
   5 │     5    100  Optimal  0.100874   16260  1.42488e-8

or run a performance profile:

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