all roots of a polynomial

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

all roots of a polynomial

Boost - Users mailing list
Hello,

I found Boost while searching for a C++ library which can do accurate
polynomial root finding. The problem is that the documentation does not make
it very clear how to implement this tool.

Does anyone by any chance have some sample code on implementing this feature
or steer me in the direction of an example in the documentation? I would
like to use the best decimal place accuracy (it appears that you can get
50-place here?)

Thanks!



--
Sent from: http://boost.2283326.n4.nabble.com/Boost-Users-f2553780.html
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: all roots of a polynomial

Boost - Users mailing list
Hi,

In boost/math/example, you will find 5 example files:

https://github.com/boostorg/math/tree/develop/example

https://github.com/boostorg/math/blob/develop/example/root_finding_fifth.cpp

https://github.com/boostorg/math/blob/develop/example/root_finding_multiprecision_example.cpp

https://github.com/boostorg/math/blob/develop/example/root_finding_n_example.cpp

https://github.com/boostorg/math/blob/develop/example/root_finding_start_locations.cpp

https://github.com/boostorg/math/blob/develop/example/root_n_finding_algorithms.cpp


​​

‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐

On February 22, 2018 12:38 PM, mdebonis via Boost-users <[hidden email]> wrote:

> ​​
>
> Hello,
>
> I found Boost while searching for a C++ library which can do accurate
>
> polynomial root finding. The problem is that the documentation does not make
>
> it very clear how to implement this tool.
>
> Does anyone by any chance have some sample code on implementing this feature
>
> or steer me in the direction of an example in the documentation? I would
>
> like to use the best decimal place accuracy (it appears that you can get
>
> 50-place here?)
>
> Thanks!
>
>
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Sent from: http://boost.2283326.n4.nabble.com/Boost-Users-f2553780.html
>
> Boost-users mailing list
>
> [hidden email]
>
> https://lists.boost.org/mailman/listinfo.cgi/boost-users


_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] all roots of a polynomial

Boost - Users mailing list
In reply to this post by Boost - Users mailing list
My previous attempt was rightly rejected because the attached paper was too large for the distribution list (don't want to spam the inbox of people who aren't interested) so here's the Bibtex citation instead

@article{mason2005toa,
  title={TOA/FOA geolocation solutions using multivariate resultants},
  author={Mason, Jeff and Romero, Louis},
  journal={Navigation},
  volume={52},
  number={3},
  pages={163--177},
  year={2005},
  publisher={Wiley Online Library}
}

But I can email the paper to anyone who is interested if you contact me directly.

I've written a "MultiDimPoly" C++ library based on the Multivariate Resultant technique described in the cited paper.   The library can find all common real roots for an arbitrary set of multidimensional polynomials (but combining a large number of high dimensional polynomials makes the construction of the resultant matrix take a long time, but 4th order polynomials in 5 variables is easily doable).   At this point I can't share the MultiDimPoly library with you because I work for a government lab and everything has to go through a formal "Review and Approval" process before it can be released to the public to prevent the accidental release of sensitive information.  There is absolutely nothing sensitive in this particular library but it still has to go through the R&A process and I'm a few years away from making the request (because the MultiDimPoly library was written to support a next generation geolocation library that isn't ready for public release yet, it generalizes th
 e algorithm described in the cited paper by Mason and Romero).

 If I can get approval from the Department Of Energy (they put limits on how many people employed by the labs can go to each to each conference) to go to the World Congress on Computational Mechanics in New York City this July, I may be able to release the MATLAB prototype version of the MultiDimPoly library there.  But in the meantime, to help you out somewhat, the gist of the assembly algorithm for the multivariate resultant matrix is to create a function analogous to MATLAB's intersect(...,'rows') function that can match up multidimensional polynomial powers to find the indices of the columns of the resultant matrix to copy in coefficients from the polynomials you want to solve for the common roots of.  

The C++ MultiDimLibrary uses the Armadillo matrix library to provide access to the complex (real plus imaginary numbers) Generalized Eigenvalue Problem decomposition (and for other reasons).  The MultiDimPoly library uses Gauss Newton (based on the Pseudo inverse rather than a traditional implementation of least squares to avoid singularity problems) iteration to polish the roots returned by the multivariate resultant solve with Non-linear Least Squares, so you can get close to machine accuracy in the roots.  Note that there is a singularity (solutions disappear into the null space of the resultant matrix) when the solution value of the eigenvalue unknown is zero, so you have to be a little careful in how you set up the system of polynomials, or the particular solution that you want my be lost in the null space which is indistinguishable from every other eigenvector in the null space (the eigenvector you want could be any of an infinite number of linear combinations of the nu
 ll space eigenvectors returned by the GEVP solve).  

Other features of the MultiDimPoly library include that you can add substract and multiply multidimensional polynomials as if they were numbers (overloaded +, -, *) operators.  In terms of "division", the matlab version also has some factoring capabilities and you can also get the "inverse" of a matrix of polynomials by using cramer's rule (you get a matrix of polynomials in the numerator and a discriminant polynomial in the denominator).  You can of course evaluate polynomials.  The C++ version uses std::vector<std::vector<MultiDimPoly> > instead of a MultiDimPolyMatrix class so it doesn't have the division capabilities but it's a LOT faster than the MATLAB library (the function comparable to intersect(...,'rows') is a lot faster).

Sincerely,
Keith Dalbey

-----Original Message-----
From: Boost-users [mailto:[hidden email]] On Behalf Of mdebonis via Boost-users
Sent: Thursday, February 22, 2018 11:38 AM
To: [hidden email]
Cc: mdebonis <[hidden email]>
Subject: [EXTERNAL] [Boost-users] all roots of a polynomial

Hello,

I found Boost while searching for a C++ library which can do accurate polynomial root finding. The problem is that the documentation does not make it very clear how to implement this tool.

Does anyone by any chance have some sample code on implementing this feature or steer me in the direction of an example in the documentation? I would like to use the best decimal place accuracy (it appears that you can get 50-place here?)

Thanks!



--
Sent from: http://boost.2283326.n4.nabble.com/Boost-Users-f2553780.html
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: all roots of a polynomial

Boost - Users mailing list
In reply to this post by Boost - Users mailing list
> -----Original Message-----
> From: Boost-users [mailto:[hidden email]] On Behalf Of mdebonis via Boost-users
> Sent: 22 February 2018 18:38
> To: [hidden email]
> Cc: mdebonis
> Subject: [Boost-users] all roots of a polynomial
>
> Hello,
>
> I found Boost while searching for a C++ library which can do accurate
> polynomial root finding. The problem is that the documentation does not make
> it very clear how to implement this tool.
>
> Does anyone by any chance have some sample code on implementing this feature
> or steer me in the direction of an example in the documentation? I would
> like to use the best decimal place accuracy (it appears that you can get
> 50-place here?)

The index of http://www.boost.org/doc/libs/1_66_0/libs/math/doc/html/index.html should help find

http://www.boost.org/doc/libs/1_66_0/libs/math/doc/html/root_finding.html

and

http://www.boost.org/doc/libs/1_66_0/libs/math/doc/html/math_toolkit/roots_deriv.html

is probably what you want.

(You may find Wolfram Alpha helpful if your finding derivatives is as rusty as mine).

You can get hundreds of decimal digits precision if that is your wish.

http://www.boost.org/doc/libs/1_66_0/libs/math/doc/html/math_toolkit/root_finding_examples/multiprecision_root.html

To install Boost, you just need to follow the basic instructions that install the header files .hpp onto your hard drive at your
chosen location.

(Boost.Math is header only, so you need not worry about building or downloading any libraries).

You should then be able to run the several examples.

Enjoy!

Paul

---
Paul A. Bristow
Prizet Farmhouse
Kendal UK LA8 8AB
+44 (0) 1539 561830



_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users