Use gauss_elimination_interval to solve A*b = x in contractors

[Kolaru]

This PR forces the used of (preconditionned) Gauss elimination in Newton contractor.

It required some adjustement as the previous definition of the algorithm for SArray was incorrect. In order to stay simple, this PR drops support for vector and matrices that are neither MArray or SArray

The change result in small perfomance improvements. Unfortunately not enough to test the functions mentionned in #108 and #86 in a reasonnable amount of time, but it is a first step towards solving these issues.

Other changes:

• The benchmarks have been changed to use SArray rather thant Array.
• Due to the previous, gauss_seidel_contractor had to be modified to handle SArray efficiently.
• The Smiley tests now also test Krawczyk method.

And finally here is the benchmark report. Note that the improvements concerning the functions in linear_eq.jl do not give much information as the benchmarks where modified.

---

Benchmark report

# Benchmark Report for *IntervalRootFinding* ## Job Properties * Time of benchmarks: - Target: 8 Feb 2019 - 01:46 - Baseline: 8 Feb 2019 - 01:49 * Package commits: - Target: 91e0a4 - Baseline: 8f605c * Julia commits: - Target: 80516c - Baseline: 80516c * Julia command flags: - Target: None - Baseline: None * Environment variables: - Target: None - Baseline: None ## Results A ratio greater than `1.0` denotes a possible regression (marked with :x:), while a ratio less than `1.0` denotes a possible improvement (marked with :white_check_mark:). Only significant results - results that indicate possible regressions or improvements - are shown below (thus, an empty table means that all benchmark results remained invariant between builds). | ID | time ratio | memory ratio | |-------------------------------------------------------------------|------------------------------|------------------------------| | `["Dietmar-Ratz", "Dietmar-Ratz 9", "Krawczyk"]` | 0.92 (5%) :white_check_mark: | 1.00 (1%) | | `["Linear equations", "n = 10", "Gauss elimination"]` | 0.61 (5%) :white_check_mark: | 1.08 (1%) :x: | | `["Linear equations", "n = 10", "Gauss seidel contractor"]` | 0.74 (5%) :white_check_mark: | 0.47 (1%) :white_check_mark: | | `["Linear equations", "n = 10", "Gauss seidel"]` | 0.63 (5%) :white_check_mark: | 0.14 (1%) :white_check_mark: | | `["Linear equations", "n = 2", "Gauss elimination"]` | 0.14 (5%) :white_check_mark: | 0.17 (1%) :white_check_mark: | | `["Linear equations", "n = 2", "Gauss seidel contractor"]` | 0.44 (5%) :white_check_mark: | 0.06 (1%) :white_check_mark: | | `["Linear equations", "n = 2", "Gauss seidel"]` | 0.31 (5%) :white_check_mark: | 0.02 (1%) :white_check_mark: | | `["Linear equations", "n = 5", "Gauss elimination"]` | 0.61 (5%) :white_check_mark: | 0.53 (1%) :white_check_mark: | | `["Linear equations", "n = 5", "Gauss seidel contractor"]` | 0.84 (5%) :white_check_mark: | 0.20 (1%) :white_check_mark: | | `["Linear equations", "n = 5", "Gauss seidel"]` | 0.71 (5%) :white_check_mark: | 0.06 (1%) :white_check_mark: | | `["Rastigrin stationary points", "Newton"]` | 0.83 (5%) :white_check_mark: | 0.86 (1%) :white_check_mark: | | `["Smiley", "Smiley and Chun (2001), Example 2.2", "Newton"]` | 0.97 (5%) | 0.98 (1%) :white_check_mark: | | `["Smiley", "Smiley and Chun (2001), Example 5.2", "Newton"]` | 0.78 (5%) :white_check_mark: | 0.83 (1%) :white_check_mark: | | `["Smiley", "Smiley and Chun (2001), Example 5.4", "Newton"]` | 1.00 (5%) | 1.01 (1%) :x: | ## Benchmark Group List Here's a list of all the benchmark groups executed by this job: - `["Dietmar-Ratz", "Dietmar-Ratz 1"]` - `["Dietmar-Ratz", "Dietmar-Ratz 2"]` - `["Dietmar-Ratz", "Dietmar-Ratz 3"]` - `["Dietmar-Ratz", "Dietmar-Ratz 4"]` - `["Dietmar-Ratz", "Dietmar-Ratz 5"]` - `["Dietmar-Ratz", "Dietmar-Ratz 6"]` - `["Dietmar-Ratz", "Dietmar-Ratz 7"]` - `["Dietmar-Ratz", "Dietmar-Ratz 8"]` - `["Dietmar-Ratz", "Dietmar-Ratz 9"]` - `["Linear equations", "n = 10"]` - `["Linear equations", "n = 2"]` - `["Linear equations", "n = 5"]` - `["Rastigrin stationary points"]` - `["Smiley", "Smiley and Chun (2001), Example 2.2"]` - `["Smiley", "Smiley and Chun (2001), Example 5.2"]` - `["Smiley", "Smiley and Chun (2001), Example 5.4"]` ## Julia versioninfo ### Target ``` Julia Version 1.1.0 Commit 80516ca202 (2019-01-21 21:24 UTC) Platform Info: OS: Windows (x86_64-w64-mingw32) Microsoft Windows [version 10.0.17763.292] CPU: Intel(R) Core(TM) i5-6600K CPU @ 3.50GHz: speed user nice sys idle irq #1 3504 MHz 20717015 0 12064281 136707359 2893265 ticks #2 3504 MHz 20986640 0 8425671 140076125 221156 ticks #3 3504 MHz 27314125 0 7700046 134474265 157843 ticks #4 3504 MHz 27567140 0 8096406 133824890 168750 ticks Memory: 15.95343017578125 GB (8450.8984375 MB free) Uptime: 295600.0 sec Load Avg: 0.0 0.0 0.0 WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-6.0.1 (ORCJIT, skylake) ``` ### Baseline ``` Julia Version 1.1.0 Commit 80516ca202 (2019-01-21 21:24 UTC) Platform Info: OS: Windows (x86_64-w64-mingw32) Microsoft Windows [version 10.0.17763.292] CPU: Intel(R) Core(TM) i5-6600K CPU @ 3.50GHz: speed user nice sys idle irq #1 3504 MHz 20752468 0 12070468 136819640 2894718 ticks #2 3504 MHz 21026109 0 8430671 140185578 221281 ticks #3 3504 MHz 27361468 0 7704109 134576781 157890 ticks #4 3504 MHz 27616078 0 8101140 133925140 168750 ticks Memory: 15.95343017578125 GB (8412.49609375 MB free) Uptime: 295754.0 sec Load Avg: 0.0 0.0 0.0 WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-6.0.1 (ORCJIT, skylake) ```

[codecov-io]

Codecov Report

Merging #111 into master will increase coverage by 0.63%. The diff coverage is 70.37%.

@@            Coverage Diff             @@
##           master     #111      +/-   ##
==========================================
+ Coverage   58.48%   59.12%   +0.63%     
==========================================
  Files          11       11              
  Lines         542      526      -16     
==========================================
- Hits          317      311       -6     
+ Misses        225      215      -10

Impacted Files	Coverage Δ
src/IntervalRootFinding.jl	5.55% <ø> (ø)	:arrow_up:
src/linear_eq.jl	74.13% <70.37%> (+7.92%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 004994d...d375e57. Read the comment docs.

[dpsanders]

From what I've read, it's recommended to use interval Gauss-Seidel. Probably we should change \ to use that.

[dpsanders]

Or is that what's already being done?

[dpsanders]

Sorry this fell off the radar; it looks very nice.

@Kolaru Are you able to come back to this or should I try to?

[Kolaru]

I tried to rebase or merge, but the conflicts come from #153 with which I'm not familiar, making it hard. So if you still have the changes in mind you may have more luck than me. Otherwise I'll take a deeper look, probably next week.