diagrams-solve-0.1.1 test suite failure

[peti]

Citing from https://nix-cache.s3.amazonaws.com/log/n980597fmjsmaxqfi9q9ziqsmd5c8q9l-diagrams-solve-0.1.1.drv:

running tests
Running 1 test suites...
Test suite tests: RUNNING...
Solve
  solutions found satisfy quadratic equation: OK
    +++ OK, passed 100 tests.
  solutions found satisfy cubic equation:     FAIL
    *** Failed! Falsifiable (after 62 tests and 27 shrinks): 
    89.0
    0.0
    1.0
    -2286.0
    Use --quickcheck-replay '61 TFGenR 000018C68371466B000000001DCD6500000000000000E26100000018AE17A400 0 9223372036854775806 63 0' to reproduce.

1 out of 2 tests failed (0.00s)
Test suite tests: FAIL

[byorgey]

Thanks for the report. This is actually a known issue; in particular, the issue is that the solver is perhaps not as numerically stable as it could be, and occasionally will fail to return a result within the expected tolerance. I tried to improve this situation with https://github.com/diagrams/diagrams-solve/commit/44ff207fc1bfd6b0241a563ceaf0e199bf364aba but I don't really know what I'm doing and as you can see that experiment has never actually been merged. Ultimately it's a bit silly for us to be using our own homegrown solver methods; I would love to farm this work out to an optimized, dedicated root-finding package instead.

[robinp]

Hit this with (-54, 0, 1, -3155). Please either improve or make the test more tolerant?

[byorgey]

The test is already quite tolerant; no matter how tolerant we make it there always seem to exist some combination of coefficients that make it numerically unstable enough to fail. As explained above we don't have the expertise to improve things. Though it does remind me I should perhaps try using https://herbie.uwplse.org/ and see if it helps.

[blackgnezdo]

And one more:

Solve solutions found satisfy quadratic equation: OK +++ OK, passed 100 tests. solutions found satisfy cubic equation: FAIL *** Failed! Falsifiable (after 67 tests and 14 shrinks): 33.76506136107823 55.0 28.0 -21603.0 Use --quickcheck-replay '66 TFGenR 3158287060CBD4EEF0BE48C7B4E5845AC63027C001E9BE5BD18903178C6E947E 0 15 4 0' to reproduce.

1 out of 2 tests failed (0.03s)

[byorgey]

So I've started looking into better root-finding methods, here are my initial notes.

• The math-functions package has root finding code (using Ridder's algorithm and/or Newton-Raphson) we could depend on, but it only finds a single root and you have to give it a starting bracket, which is not super useful in our context.
• The dsp package has a module Polynomial.Roots containing an implementation of Laguerre's method, which finds all the (complex) roots, but it's GPL and I don't want to depend on the entire dsp package.
• The hmatrix-gsl package has Numeric.GSL.Polynomials which has an interface to a root finder from GSL, but that is an even heavier-weight dependency.
• I had looked before into implementing the Durand-Kerner method which can also find all roots (see misc/DKSolve.hs in the diagrams-lib repo, but I don't think I ever got it to work.
• Apparently the Jenkins-Traub algorithm is widely used for root finding, but the only implementation I could find in Haskell is at https://github.com/frankwang95/jenkins_traub which doesn't seem like it comes with any particular guarantees.

[byorgey]

I wrote a blog post about this: https://byorgey.wordpress.com/2019/02/13/finding-roots-of-polynomials-in-haskell/ Still don't know a good solution to do better than what we have currently.

[jinwoo]

Another instance:

Solve
  solutions found satisfy quadratic equation: OK
    +++ OK, passed 100 tests.
  solutions found satisfy cubic equation:     FAIL
    *** Failed! Falsifiable (after 89 tests and 37 shrinks): 
    2.0
    0.0
    1.0
    -38849.0
    Use --quickcheck-replay '88 TFGenR 919D20CCC52218FC6658C7973CA5C87C9EC7C3038FA024C9939349A6A260CDEA 0 67108863 26 0' to reproduce.

1 out of 2 tests failed (0.03s)