Re: [Boost-users] [EXTERNAL] all roots of a polynomial

Subject: Re: [Boost-users] [EXTERNAL] all roots of a polynomial
From: Dalbey, Keith (kdalbey_at_[hidden])
Date: 2018-02-22 22:12:15

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 the 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 null 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:boost-users-bounces_at_[hidden]] On Behalf Of mdebonis via Boost-users
Sent: Thursday, February 22, 2018 11:38 AM
To: boost-users_at_[hidden]
Cc: mdebonis <mark.debonis_at_[hidden]>
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
Boost-users_at_[hidden]
https://lists.boost.org/mailman/listinfo.cgi/boost-users