Jutho / KrylovKit.jl

Krylov methods for linear problems, eigenvalues, singular values and matrix functions
Other
284 stars 37 forks source link

Implement BiCGStab #50

Closed lkdvos closed 3 years ago

lkdvos commented 3 years ago

First implementation of BiCGStab, preliminary benchmarks seem to indicate comparable performance to GMRES, however this is dependent on a lot of parameters (Krylovdimension, operator size, specific operator, ...) and thus this is not a quantitative test.

##############################################
10 
####################
GMRES{ModifiedGramSchmidt2, Float64}(ModifiedGramSchmidt2(), 2, 10, 1.2696590058460974e-14, 0)
BechmarkTools.Trial: 10000 samples with 1 evaluations.
 Range (min … max):  33.959 μs …  4.468 ms  ┊ GC (min … max): 0.00% … 97.31%
 Time  (median):     38.578 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   42.177 μs ± 84.703 μs  ┊ GC (mean ± σ):  4.40% ±  2.18%

      █▅▇▁▃                                                    
  ▃▇▇██████▆▅▄▄▃▃▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  34 μs           Histogram: frequency by time        76.5 μs <

 Memory estimate: 21.92 KiB, allocs estimate: 371.

GMRES{ModifiedGramSchmidt2, Float64}(ModifiedGramSchmidt2(), 50, 30, 1.2696590058460974e-14, 0)
BechmarkTools.Trial: 10000 samples with 1 evaluations.
 Range (min … max):  34.969 μs …  2.955 ms  ┊ GC (min … max): 0.00% … 97.67%
 Time  (median):     36.582 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   41.049 μs ± 80.944 μs  ┊ GC (mean ± σ):  5.42% ±  2.75%

  ▅██▇▆▄▂▂▁▁▂▁▂▁▂▂▂▃▂▂▂▁▁▁▁                                   ▂
  ██████████████████████████▇▇▇▆▅▅▄▅▄▄▃▅▅▄▁▄▃▁▄▅▅▅▅▅▅▅▅▅▆▅▆▅▆ █
  35 μs        Histogram: log(frequency) by time      68.3 μs <

 Memory estimate: 36.00 KiB, allocs estimate: 371.

BiCGStab{Float64}(1500, 1.2696590058460974e-14, 0)
BechmarkTools.Trial: 10000 samples with 1 evaluations.
 Range (min … max):  38.888 μs …  3.081 ms  ┊ GC (min … max): 0.00% … 97.93%
 Time  (median):     39.798 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   42.926 μs ± 66.868 μs  ┊ GC (mean ± σ):  3.45% ±  2.19%

   ▆██▆▅▃▂               ▁▁▂▂▂▂▂▂▁ ▁▁             ▁▁          ▂
  █████████▇▆▆▆▆▇███▇▆████████████████▇▇▇▇██▇▆▆▇████▇▇▇▆▇▇▇▇▆ █
  38.9 μs      Histogram: log(frequency) by time      54.3 μs <

 Memory estimate: 23.17 KiB, allocs estimate: 486.

##############################################
100 
####################
GMRES{ModifiedGramSchmidt2, Float64}(ModifiedGramSchmidt2(), 2, 100, 3.5471700924607985e-13, 0)
BechmarkTools.Trial: 1654 samples with 1 evaluations.
 Range (min … max):  2.784 ms …   7.459 ms  ┊ GC (min … max): 0.00% … 40.83%
 Time  (median):     2.858 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   3.016 ms ± 535.550 μs  ┊ GC (mean ± σ):  2.64% ±  7.97%

  █▇▆▄▃▁▂▁▁▁                                                   
  ██████████▇▆█▆▇▇▇▆▅▄▁▄▄▆▁▅▄▄▄▅▁▄▁▄▄▅▄▆▁▁▁▁▄▅▄▄▁▁▁▁▁▁▁▁▁▆▇▇▇ █
  2.78 ms      Histogram: log(frequency) by time      5.61 ms <

 Memory estimate: 1.32 MiB, allocs estimate: 16807.

GMRES{ModifiedGramSchmidt2, Float64}(ModifiedGramSchmidt2(), 50, 30, 3.5471700924607985e-13, 0)
BechmarkTools.Trial: 246 samples with 1 evaluations.
 Range (min … max):  18.958 ms … 31.952 ms  ┊ GC (min … max): 0.00% … 9.95%
 Time  (median):     19.532 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   20.311 ms ±  1.897 ms  ┊ GC (mean ± σ):  2.55% ± 4.59%

  ▅█▃▁                                                         
  ████▆▄▅▃▃▂▃▁▁▃▅▅▄▄▃▃▂▂▂▁▁▁▂▁▁▃▁▃▁▁▁▁▁▁▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃ ▃
  19 ms           Histogram: frequency by time          30 ms <

 Memory estimate: 9.01 MiB, allocs estimate: 98746.

BiCGStab{Float64}(1500, 3.5471700924607985e-13, 0)
BechmarkTools.Trial: 402 samples with 1 evaluations.
 Range (min … max):  11.592 ms …  17.670 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     12.145 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   12.453 ms ± 871.056 μs  ┊ GC (mean ± σ):  1.87% ± 4.27%

    ▁▁█▄▁▂▄                                                     
  ▃▅████████▅▅▅▄▄▂▃▃▃▃▁▃▃▃▁▃▃▃▃▄▆▃▃▃▃▃▂▁▁▂▂▁▂▁▃▁▁▂▁▁▁▁▁▃▁▁▁▁▁▂ ▃
  11.6 ms         Histogram: frequency by time         15.9 ms <

 Memory estimate: 5.96 MiB, allocs estimate: 33029.

##############################################
1000 
####################
GMRES{ModifiedGramSchmidt2, Float64}(ModifiedGramSchmidt2(), 2, 1000, 1.1154523617852167e-11, 0)
BechmarkTools.Trial: 3 samples with 1 evaluations.
 Range (min … max):  2.122 s …   2.173 s  ┊ GC (min … max): 0.27% … 0.24%
 Time  (median):     2.137 s              ┊ GC (median):    0.27%
 Time  (mean ± σ):   2.144 s ± 26.256 ms  ┊ GC (mean ± σ):  0.31% ± 0.10%

  █               █                                       ██ 
  █▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  2.12 s         Histogram: frequency by time        2.17 s <

 Memory estimate: 109.16 MiB, allocs estimate: 1878943.

GMRES{ModifiedGramSchmidt2, Float64}(ModifiedGramSchmidt2(), 50, 30, 1.1154523617852167e-11, 0)
BechmarkTools.Trial: 16 samples with 1 evaluations.
 Range (min … max):  317.520 ms … 347.255 ms  ┊ GC (min … max): 0.50% … 0.46%
 Time  (median):     321.755 ms               ┊ GC (median):    0.49%
 Time  (mean ± σ):   326.272 ms ±   9.941 ms  ┊ GC (mean ± σ):  0.55% ± 0.17%

   █                                                             
  ▇█▇▁▁▇▇▁▇▇▁▇▁▁▇▁▁▁▁▁▁▁▁▁▁▁▁▇▁▁▁▁▁▁▁▁▇▁▁▁▁▁▁▇▁▁▁▁▁▁▁▁▁▁▁▁▇▁▁▁▇ ▁
  318 ms           Histogram: frequency by time          347 ms <

 Memory estimate: 50.04 MiB, allocs estimate: 98746.

BiCGStab{Float64}(1500, 1.1154523617852167e-11, 0)
BechmarkTools.Trial: 11 samples with 1 evaluations.
 Range (min … max):  458.184 ms … 511.958 ms  ┊ GC (min … max): 0.29% … 0.26%
 Time  (median):     480.803 ms               ┊ GC (median):    0.28%
 Time  (mean ± σ):   486.912 ms ±  18.079 ms  ┊ GC (mean ± σ):  0.28% ± 0.01%

  ▁              █▁      ▁ ▁               ▁       ▁▁        ▁▁▁ 
  █▁▁▁▁▁▁▁▁▁▁▁▁▁▁██▁▁▁▁▁▁█▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁██▁▁▁▁▁▁▁▁██ ▁
  458 ms           Histogram: frequency by time          512 ms <

 Memory estimate: 47.03 MiB, allocs estimate: 33029.
Jutho commented 3 years ago

Thanks Lukas; I am going to merge the current version and make some small changes afterwards.