Benchmark on dense random symmetric positive definite matrices
using RandomLinearAlgebraSolvers, Random, LinearAlgebra, SparseArrays
Random.seed!(1234)Random.TaskLocalRNG()Benchmark of methods to solve Ax = b with A an n x n randomly generated symmetric positive definite matrix, and b = A * xref.
using DataFrames, Printf, SolverBenchmark, StoppingN = 5 # number of problems
n = 100 # size of A: n x n100Names of solvers:
names = [:RandomizedKaczmarz, :RandomizedBlockKaczmarz, :RandomizedCD, :RandomizedCD2, :RandomizedNewton]5-element Vector{Symbol}:
:RandomizedKaczmarz
:RandomizedBlockKaczmarz
:RandomizedCD
:RandomizedCD2
:RandomizedNewton#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 5 entries:
:RandomizedBlockKaczmarz => 5×6 DataFrame…
:RandomizedCD => 5×6 DataFrame…
:RandomizedCD2 => 5×6 DataFrame…
:RandomizedKaczmarz => 5×6 DataFrame…
:RandomizedNewton => 5×6 DataFrame…for i=1:N
Ar = rand(n,n); A = 1/sqrt(n) * Ar'*Ar + Matrix{Float64}(I, n, 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 0.566845 seconds (1.10 M allocations: 268.637 MiB, 19.15% gc time, 0.50% compilation time)
0.074540 seconds (1.67 k allocations: 18.248 MiB)
0.040995 seconds (800.01 k allocations: 12.207 MiB)
0.220676 seconds (1.14 M allocations: 29.294 MiB, 75.75% compilation time)
1.701435 seconds (2.76 M allocations: 446.825 MiB, 4.92% gc time, 69.71% compilation time)
0.525842 seconds (1.10 M allocations: 268.557 MiB, 15.43% gc time)
0.076577 seconds (1.72 k allocations: 18.785 MiB)
0.041973 seconds (800.01 k allocations: 12.207 MiB)
0.066025 seconds (800.01 k allocations: 12.207 MiB, 25.40% gc time)
0.489206 seconds (382.22 k allocations: 326.380 MiB, 3.71% gc time)
0.537235 seconds (1.10 M allocations: 268.557 MiB, 16.12% gc time)
0.066341 seconds (1.47 k allocations: 16.101 MiB)
0.043825 seconds (800.01 k allocations: 12.207 MiB)
0.053684 seconds (800.01 k allocations: 12.207 MiB)
0.503657 seconds (382.49 k allocations: 326.483 MiB, 5.76% gc time)
0.527094 seconds (1.10 M allocations: 268.557 MiB, 14.53% gc time)
0.069529 seconds (1.57 k allocations: 17.175 MiB)
0.057993 seconds (800.01 k allocations: 12.207 MiB, 28.23% gc time)
0.048904 seconds (800.01 k allocations: 12.207 MiB)
0.495417 seconds (382.13 k allocations: 326.352 MiB, 3.97% gc time)
0.529796 seconds (1.10 M allocations: 268.557 MiB, 16.09% gc time)
0.072230 seconds (1.62 k allocations: 17.712 MiB)
0.040737 seconds (800.01 k allocations: 12.207 MiB)
0.053803 seconds (800.01 k allocations: 12.207 MiB)
0.497865 seconds (381.75 k allocations: 326.206 MiB, 5.97% gc time)for name in names
@show name
@show stats[name]
endname = :RandomizedKaczmarz
stats[name] = 5×6 DataFrame
Row │ id nvar status time iter score
│ Int64 Int64 Symbol Float64 Int64 Float64
─────┼─────────────────────────────────────────────────────────
1 │ 1 100 IterationLimit 0.566851 100001 10.2994
2 │ 2 100 IterationLimit 0.525845 100001 15.7711
3 │ 3 100 IterationLimit 0.537238 100001 13.4208
4 │ 4 100 IterationLimit 0.527096 100001 12.5685
5 │ 5 100 IterationLimit 0.5298 100001 13.137
name = :RandomizedBlockKaczmarz
stats[name] = 5×6 DataFrame
Row │ id nvar status time iter score
│ Int64 Int64 Symbol Float64 Int64 Float64
─────┼─────────────────────────────────────────────────────
1 │ 1 100 Optimal 0.072386 34 1.46993e-8
2 │ 2 100 Optimal 0.074445 35 4.30919e-9
3 │ 3 100 Optimal 0.0642099 30 9.69521e-9
4 │ 4 100 Optimal 0.067369 32 2.47201e-9
5 │ 5 100 Optimal 0.0701551 33 3.8508e-9
name = :RandomizedCD
stats[name] = 5×6 DataFrame
Row │ id nvar status time iter score
│ Int64 Int64 Symbol Float64 Int64 Float64
─────┼──────────────────────────────────────────────────────────
1 │ 1 100 IterationLimit 0.0409992 100001 433.111
2 │ 2 100 IterationLimit 0.041976 100001 319.675
3 │ 3 100 IterationLimit 0.0438261 100001 381.547
4 │ 4 100 IterationLimit 0.057997 100001 393.617
5 │ 5 100 IterationLimit 0.0407388 100001 503.414
name = :RandomizedCD2
stats[name] = 5×6 DataFrame
Row │ id nvar status time iter score
│ Int64 Int64 Symbol Float64 Int64 Float64
─────┼──────────────────────────────────────────────────────────
1 │ 1 100 IterationLimit 0.220678 100001 28352.9
2 │ 2 100 IterationLimit 0.066025 100001 27199.2
3 │ 3 100 IterationLimit 0.0536861 100001 27964.2
4 │ 4 100 IterationLimit 0.0489049 100001 29093.1
5 │ 5 100 IterationLimit 0.0538061 100001 28734.3
name = :RandomizedNewton
stats[name] = 5×6 DataFrame
Row │ id nvar status time iter score
│ Int64 Int64 Symbol Float64 Int64 Float64
─────┼─────────────────────────────────────────────────
1 │ 1 100 Optimal 1.70095 1010 NaN
2 │ 2 100 Optimal 0.488756 1010 NaN
3 │ 3 100 Optimal 0.503205 1010 NaN
4 │ 4 100 Optimal 0.494952 1010 NaN
5 │ 5 100 Optimal 0.497374 1010 NaNor run a performance profile:
using Plots
gr()
cost(df) = (df.status .!= :Optimal) * Inf + df.time
p = performance_profile(stats, cost)