Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

mathmore: invalid roots for a quartic polynomial #6900

Closed
sbinet opened this issue Dec 1, 2020 · 6 comments · Fixed by #6908
Closed

mathmore: invalid roots for a quartic polynomial #6900

sbinet opened this issue Dec 1, 2020 · 6 comments · Fixed by #6908

Comments

@sbinet
Copy link
Contributor

sbinet commented Dec 1, 2020

trying to find the roots of the following polynomial:

  a x^4 + b x^3 + c x^2 + d x + e = 0

a = 2.2206846808021337
b = 7.643281053997895
c = 8.831759446092846 
d = 3.880673545129404
e = 0.5724551380144077

I get the following roots:

>>> import ROOT
>>> list(ROOT.Math.Polynomial(
2.2206846808021337, 7.643281053997895,
8.831759446092846, 3.880673545129404,
0.5724551380144077).FindRoots())

[(-0.8609914206605772+0j),
 (-0.8609285681365977+0j),
 (-0.8599689425356434-3.142626022335893e-05j),
 (-0.8599689425356434+3.142626022335893e-05j)]

plotting that polynomial, we can easily notice the roots are incorrect:
foo

using numpy.roots (which is using a companion matrix):

>>> import numpy as np
>>> np.roots([
2.2206846808021337, 7.643281053997895,
8.831759446092846, 3.880673545129404,
0.5724551380144077])

array([-1.34283005+0.00000000e+00j, -1.34282804+0.00000000e+00j,
       -0.37809989+1.00708006e-06j, -0.37809989-1.00708006e-06j])

we do get saner values.

@sbinet sbinet added the bug label Dec 1, 2020
@lmoneta lmoneta self-assigned this Dec 2, 2020
@lmoneta
Copy link
Member

lmoneta commented Dec 2, 2020

Hi,
Thank you for reporting this bug !
It looks to be a problem in a routine developed by HEP people, but it never came to GSL, it is copied inside Mathmore,
see https://root.cern/doc/master/complex__quartic_8h_source.html

If I change the code in ROOT::Math::Polynomial::FindRoots to use the generic GSL function, gsl_poly_complex_solve, it
works fine. This uses an iterative procedure instead of the analytical solution. GSL does not provide a function to solve analytically quartic equations.
Probably we should change the code in Polynomial and forget about that quartic implementation until somebody fixes it.
I am not sure if it is used somewhere else (e.g. CLHEP)

Lorenzo

@sbinet
Copy link
Contributor Author

sbinet commented Dec 2, 2020

hi Lorenzo,

I stumbled on this when implementing my own GPL-free polynomial roots-finding algorithm from first principles.
I don't know the specifics of ROOT/GSL code, but in my code go-hep/exp#15 (BSD-3 licensed) I first go through building the cubic resolvent and then follow the wikipedia litterature.
note that for this particular case, what my code gives isn't completely satisfactory, though.
reading a bit more litterature, it would seem going through solving 2 quadratics would lead to better results.
I haven't got to try it out, though.

hth,
-s

@lmoneta
Copy link
Member

lmoneta commented Dec 2, 2020

Hi,
I see, if you are expert and can find the bug in this function, https://root.cern/doc/master/complex__quartic_8h_source.html, it will be great. I am sure somebody else might use that code

@lmoneta
Copy link
Member

lmoneta commented Dec 2, 2020

Looking back at my emails, I found that the routine comes from the LHCb RICH code and it was proposed to GSL, but it was never merged there at the end.

@lmoneta
Copy link
Member

lmoneta commented Dec 2, 2020

The problem seems to be in the calculation of disc at line 151
https://root.cern/doc/master/complex__quartic_8h_source.html#l00151

If I uncomment these following lines

//       more numerical problems with this calculation of disc
//      double CR2 = 729 * rcub * rcub;
//      double CQ3 = 2916 * qcub * qcub * qcub;
//       disc = (CR2 - CQ3) / 2125764.0;

it seems top provide the correct result in your example.
It would be nice to have more test points to validate the code

@sbinet
Copy link
Contributor Author

sbinet commented Dec 2, 2020

I had found this polynomial to test the branch of my code where R==0. (brute force, by using the equivalent of MINUIT to minimize R).

(I am explicitly not looking at GPL-licensed code not to "taint" my BSD-licensed code)

lmoneta added a commit to lmoneta/root that referenced this issue Dec 3, 2020
…d add test

Uncomment some different code that is used to compute the discriminat of the
resolvent cubic equation used to find roots of quartic. This code seems to eprforms better.

This fixes root-project#6900

Add tests for quartic equations
lmoneta added a commit that referenced this issue Dec 19, 2023
…6908)

* Fix in complex_quartic  problem reported in issue #6900 and add test

Uncomment some different code that is used to compute the discriminat of the
resolvent cubic equation used to find roots of quartic. This code seems to eprforms better.

This fixes #6900

Add tests for quartic equations

* Update and fix links and spelling in the reference documentation of ROOT::Math::Polynomial

* Increate test tolerance for fixing failure observed in  i386
maksgraczyk pushed a commit to maksgraczyk/root that referenced this issue Jan 12, 2024
…d add test (root-project#6908)

* Fix in complex_quartic  problem reported in issue root-project#6900 and add test

Uncomment some different code that is used to compute the discriminat of the
resolvent cubic equation used to find roots of quartic. This code seems to eprforms better.

This fixes root-project#6900

Add tests for quartic equations

* Update and fix links and spelling in the reference documentation of ROOT::Math::Polynomial

* Increate test tolerance for fixing failure observed in  i386
vgvassilev pushed a commit to vgvassilev/root that referenced this issue Feb 8, 2024
…d add test (root-project#6908)

* Fix in complex_quartic  problem reported in issue root-project#6900 and add test

Uncomment some different code that is used to compute the discriminat of the
resolvent cubic equation used to find roots of quartic. This code seems to eprforms better.

This fixes root-project#6900

Add tests for quartic equations

* Update and fix links and spelling in the reference documentation of ROOT::Math::Polynomial

* Increate test tolerance for fixing failure observed in  i386
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants