Hello
Jira seems to be down? So I'm trying here to post my request for an enhancement: Could we have a roots() method in PolynomialFunction class? For example I ported the code in this stackoverflow question to apache commons math by using the EigenDecomposition class: http://stackoverflow.com/questions/13805644/finding-roots-of-polynomial-in-java/13805708#13805708 See the attached file for an example. -- Axel Kramer Symja Library - Java Symbolic Math System https://bitbucket.org/axelclk/symja_android_library/wiki/Home --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] FindRoot.java (2K) Download Attachment |
On 06/27/2014 04:24 PM, Axel wrote:
> Hello > > Jira seems to be down? > So I'm trying here to post my request for an enhancement: > > Could we have a roots() method in PolynomialFunction class? > For example I ported the code in this stackoverflow question to apache > commons math by using the EigenDecomposition class: > http://stackoverflow.com/questions/13805644/finding-roots-of-polynomial-in-java/13805708#13805708 > > See the attached file for an example. Hi Alex, I did take a look at the stackoverflow question, and there is already a way to do this in Commons Math using the LaguerreSolver via the solveComplex and solveAllComplex methods. But it might be good to support a second way using EigenDecomposition as a stand-alone solver. I like the idea to add a roots() method to PolynomialFunction, but which method to compute the roots is more robust? Thomas --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart
<[hidden email]> wrote: ... > I did take a look at the stackoverflow question, and there is already a > way to do this in Commons Math using the LaguerreSolver via the > solveComplex and solveAllComplex methods. > > But it might be good to support a second way using EigenDecomposition as > a stand-alone solver. > > I like the idea to add a roots() method to PolynomialFunction, but which > method to compute the roots is more robust? The attached link in the stackoverflow question to this paper: http://techdigest.jhuapl.edu/TD/td2804/Williams.pdf has this conclusion: "We have discussed some eigenvector methods for finding the roots of multi- variate polynomials. Unlike iterative, numerical methods typically applied to this problem, the methods outlined in this article possess the numerical stability of numerical linear algebra, do not require a good initial guess of the solution, and give all solutions simultaneously. Furthermore, if the initial guess is poor enough, the methods outlined herein may converge more quickly than iterative methods." So I think the "EigenDecomposition method" is more appropriate if you don't have an initial guess to start from getting the roots!? -- Axel Kramer --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
That is one article, but it doesn't actually compare the numerical
stability or efficiency of this method. It just invokes the stability of "numerical linear algebra". Whether this is a good way to compute roots is an open question. The other major question here is operation count. Computing eigenvalues of an explicit matrix is likely to be very intensive computationally. The wikipedia page on root-finding mentions in passing when is says that matrix-free methods are typically used with the eigenvalue approaches. This suggests that the preferable means to implement this idea is not to build the matrix in question, but to use an abstract linear operator which implements multiplication making use of the special form of the companion matrix. I am not sure if this approach is viable in the Commons matrix framework. I suspect not, but really don't have much of a clue about the real state of things. If the eigenvalue objects accept something like a LinearOperator object, then it is likely to work. This article[1] seems to suggest that there may be some numerical issues with large coefficients. That isn't surprising since many algorithms have similar problems. [1] http://noether.math.uoa.gr/conferences/sla2014/sites/default/files/Dopico.pdf On Sat, Jun 28, 2014 at 6:33 AM, Axel <[hidden email]> wrote: > On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart > <[hidden email]> wrote: > ... > > I did take a look at the stackoverflow question, and there is already a > > way to do this in Commons Math using the LaguerreSolver via the > > solveComplex and solveAllComplex methods. > > > > But it might be good to support a second way using EigenDecomposition as > > a stand-alone solver. > > > > I like the idea to add a roots() method to PolynomialFunction, but which > > method to compute the roots is more robust? > > The attached link in the stackoverflow question to this paper: > http://techdigest.jhuapl.edu/TD/td2804/Williams.pdf > > has this conclusion: > "We have discussed some eigenvector methods for finding the roots of multi- > variate polynomials. Unlike iterative, numerical methods typically > applied to this > problem, the methods outlined in this article possess the numerical > stability of > numerical linear algebra, do not require a good initial guess of the > solution, and give all > solutions simultaneously. Furthermore, if the initial guess is poor > enough, the methods > outlined herein may converge more quickly than iterative methods." > > So I think the "EigenDecomposition method" is more appropriate if you > don't have an initial guess to start from getting the roots!? > > -- > Axel Kramer > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [hidden email] > For additional commands, e-mail: [hidden email] > > |
Ok,
but what about my main question: "Could we have a roots() method in PolynomialFunction class?" Which in the first step delegates to LaguerreSolver#solveAllComplex()? On Sat, Jun 28, 2014 at 8:26 PM, Ted Dunning <[hidden email]> wrote: > That is one article, but it doesn't actually compare the numerical > stability or efficiency of this method. It just invokes the stability of > "numerical linear algebra". Whether this is a good way to compute roots is > an open question. > > The other major question here is operation count. Computing eigenvalues of > an explicit matrix is likely to be very intensive computationally. The > wikipedia page on root-finding mentions in passing when is says that > matrix-free methods are typically used with the eigenvalue approaches. > > This suggests that the preferable means to implement this idea is not to > build the matrix in question, but to use an abstract linear operator which > implements multiplication making use of the special form of the companion > matrix. I am not sure if this approach is viable in the Commons matrix > framework. I suspect not, but really don't have much of a clue about the > real state of things. If the eigenvalue objects accept something like a > LinearOperator object, then it is likely to work. > > This article[1] seems to suggest that there may be some numerical issues > with large coefficients. That isn't surprising since many algorithms have > similar problems. > > [1] > http://noether.math.uoa.gr/conferences/sla2014/sites/default/files/Dopico.pdf > > > On Sat, Jun 28, 2014 at 6:33 AM, Axel <[hidden email]> wrote: > >> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart >> <[hidden email]> wrote: >> ... >> > I did take a look at the stackoverflow question, and there is already a >> > way to do this in Commons Math using the LaguerreSolver via the >> > solveComplex and solveAllComplex methods. >> > >> > But it might be good to support a second way using EigenDecomposition as >> > a stand-alone solver. >> > >> > I like the idea to add a roots() method to PolynomialFunction, but which >> > method to compute the roots is more robust? >> >> The attached link in the stackoverflow question to this paper: >> http://techdigest.jhuapl.edu/TD/td2804/Williams.pdf >> >> has this conclusion: >> "We have discussed some eigenvector methods for finding the roots of multi- >> variate polynomials. Unlike iterative, numerical methods typically >> applied to this >> problem, the methods outlined in this article possess the numerical >> stability of >> numerical linear algebra, do not require a good initial guess of the >> solution, and give all >> solutions simultaneously. Furthermore, if the initial guess is poor >> enough, the methods >> outlined herein may converge more quickly than iterative methods." >> >> So I think the "EigenDecomposition method" is more appropriate if you >> don't have an initial guess to start from getting the roots!? >> >> -- >> Axel Kramer >> >> --------------------------------------------------------------------- >> To unsubscribe, e-mail: [hidden email] >> For additional commands, e-mail: [hidden email] >> >> -- Axel Kramer --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
On Thu, 3 Jul 2014 18:14:41 +0200, Axel wrote:
> Ok, > but what about my main question: > "Could we have a roots() method in PolynomialFunction class?" > > Which in the first step delegates to > LaguerreSolver#solveAllComplex()? I guess that people want to be careful before changing the API of "PolynomialFunction". [E.g. it would create a dependency towards the "o.a.c.m.complex" package. It might be better to add the functionality in that package (e.g. in "ComplexUtils").] Could you explain what you need with more details? In particular, what do you expect to get in addition to what the following code can already provide? ---CUT--- import org.apache.commons.math3.analysis.polynomials.PolynomialFunction; import org.apache.commons.math3.analysis.solvers.LaguerreSolver; import org.apache.commons.math3.complex.Complex; public class PolynomialRoots { private static final LaguerreSolver solver = new LaguerreSolver(); public static Complex[] solve(PolynomialFunction p) { return solver.solveAllComplex(p.getCoefficients(), 0d); } } ---CUT--- Best regards, Gilles > > On Sat, Jun 28, 2014 at 8:26 PM, Ted Dunning <[hidden email]> > wrote: >> That is one article, but it doesn't actually compare the numerical >> stability or efficiency of this method. It just invokes the >> stability of >> "numerical linear algebra". Whether this is a good way to compute >> roots is >> an open question. >> >> The other major question here is operation count. Computing >> eigenvalues of >> an explicit matrix is likely to be very intensive computationally. >> The >> wikipedia page on root-finding mentions in passing when is says that >> matrix-free methods are typically used with the eigenvalue >> approaches. >> >> This suggests that the preferable means to implement this idea is >> not to >> build the matrix in question, but to use an abstract linear operator >> which >> implements multiplication making use of the special form of the >> companion >> matrix. I am not sure if this approach is viable in the Commons >> matrix >> framework. I suspect not, but really don't have much of a clue >> about the >> real state of things. If the eigenvalue objects accept something >> like a >> LinearOperator object, then it is likely to work. >> >> This article[1] seems to suggest that there may be some numerical >> issues >> with large coefficients. That isn't surprising since many >> algorithms have >> similar problems. >> >> [1] >> >> http://noether.math.uoa.gr/conferences/sla2014/sites/default/files/Dopico.pdf >> >> >> On Sat, Jun 28, 2014 at 6:33 AM, Axel <[hidden email]> wrote: >> >>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart >>> <[hidden email]> wrote: >>> ... >>> > I did take a look at the stackoverflow question, and there is >>> already a >>> > way to do this in Commons Math using the LaguerreSolver via the >>> > solveComplex and solveAllComplex methods. >>> > >>> > But it might be good to support a second way using >>> EigenDecomposition as >>> > a stand-alone solver. >>> > >>> > I like the idea to add a roots() method to PolynomialFunction, >>> but which >>> > method to compute the roots is more robust? >>> >>> The attached link in the stackoverflow question to this paper: >>> http://techdigest.jhuapl.edu/TD/td2804/Williams.pdf >>> >>> has this conclusion: >>> "We have discussed some eigenvector methods for finding the roots >>> of multi- >>> variate polynomials. Unlike iterative, numerical methods typically >>> applied to this >>> problem, the methods outlined in this article possess the numerical >>> stability of >>> numerical linear algebra, do not require a good initial guess of >>> the >>> solution, and give all >>> solutions simultaneously. Furthermore, if the initial guess is poor >>> enough, the methods >>> outlined herein may converge more quickly than iterative methods." >>> >>> So I think the "EigenDecomposition method" is more appropriate if >>> you >>> don't have an initial guess to start from getting the roots!? >>> >>> -- >>> Axel Kramer >>> >>> >>> --------------------------------------------------------------------- >>> To unsubscribe, e-mail: [hidden email] >>> For additional commands, e-mail: [hidden email] >>> >>> --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
> On Jul 3, 2014, at 2:30 PM, Gilles <[hidden email]> wrote: > >> On Thu, 3 Jul 2014 18:14:41 +0200, Axel wrote: >> Ok, >> but what about my main question: >> "Could we have a roots() method in PolynomialFunction class?" >> >> Which in the first step delegates to LaguerreSolver#solveAllComplex()? > > I guess that people want to be careful before changing the API of > "PolynomialFunction". [E.g. it would create a dependency towards > the "o.a.c.m.complex" package. It might be better to add the > functionality in that package (e.g. in "ComplexUtils").] > > Could you explain what you need with more details? > In particular, what do you expect to get in addition to what the > following code can already provide? > > ---CUT--- > import org.apache.commons.math3.analysis.polynomials.PolynomialFunction; > import org.apache.commons.math3.analysis.solvers.LaguerreSolver; > import org.apache.commons.math3.complex.Complex; > > public class PolynomialRoots { > private static final LaguerreSolver solver = new LaguerreSolver(); > > public static Complex[] solve(PolynomialFunction p) { > return solver.solveAllComplex(p.getCoefficients(), 0d); > } > } > ---CUT--- I agree with Thomas that it would be good to expose a Complex[] roots() method directly in the PolynialFunction class. We can then choose whatever numerical technique we like to back it, starting with Laguerre and refining / specializing to data as we get better ideas. Phil > > > Best regards, > Gilles > > >> >>> On Sat, Jun 28, 2014 at 8:26 PM, Ted Dunning <[hidden email]> wrote: >>> That is one article, but it doesn't actually compare the numerical >>> stability or efficiency of this method. It just invokes the stability of >>> "numerical linear algebra". Whether this is a good way to compute roots is >>> an open question. >>> >>> The other major question here is operation count. Computing eigenvalues of >>> an explicit matrix is likely to be very intensive computationally. The >>> wikipedia page on root-finding mentions in passing when is says that >>> matrix-free methods are typically used with the eigenvalue approaches. >>> >>> This suggests that the preferable means to implement this idea is not to >>> build the matrix in question, but to use an abstract linear operator which >>> implements multiplication making use of the special form of the companion >>> matrix. I am not sure if this approach is viable in the Commons matrix >>> framework. I suspect not, but really don't have much of a clue about the >>> real state of things. If the eigenvalue objects accept something like a >>> LinearOperator object, then it is likely to work. >>> >>> This article[1] seems to suggest that there may be some numerical issues >>> with large coefficients. That isn't surprising since many algorithms have >>> similar problems. >>> >>> [1] >>> http://noether.math.uoa.gr/conferences/sla2014/sites/default/files/Dopico.pdf >>> >>> >>>> On Sat, Jun 28, 2014 at 6:33 AM, Axel <[hidden email]> wrote: >>>> >>>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart >>>> <[hidden email]> wrote: >>>> ... >>>> > I did take a look at the stackoverflow question, and there is already a >>>> > way to do this in Commons Math using the LaguerreSolver via the >>>> > solveComplex and solveAllComplex methods. >>>> > >>>> > But it might be good to support a second way using EigenDecomposition as >>>> > a stand-alone solver. >>>> > >>>> > I like the idea to add a roots() method to PolynomialFunction, but which >>>> > method to compute the roots is more robust? >>>> >>>> The attached link in the stackoverflow question to this paper: >>>> http://techdigest.jhuapl.edu/TD/td2804/Williams.pdf >>>> >>>> has this conclusion: >>>> "We have discussed some eigenvector methods for finding the roots of multi- >>>> variate polynomials. Unlike iterative, numerical methods typically >>>> applied to this >>>> problem, the methods outlined in this article possess the numerical >>>> stability of >>>> numerical linear algebra, do not require a good initial guess of the >>>> solution, and give all >>>> solutions simultaneously. Furthermore, if the initial guess is poor >>>> enough, the methods >>>> outlined herein may converge more quickly than iterative methods." >>>> >>>> So I think the "EigenDecomposition method" is more appropriate if you >>>> don't have an initial guess to start from getting the roots!? >>>> >>>> -- >>>> Axel Kramer >>>> >>>> --------------------------------------------------------------------- >>>> To unsubscribe, e-mail: [hidden email] >>>> For additional commands, e-mail: [hidden email] > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [hidden email] > For additional commands, e-mail: [hidden email] > --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
On Thu, 3 Jul 2014 16:15:58 -0700, Phil Steitz wrote:
>> On Jul 3, 2014, at 2:30 PM, Gilles <[hidden email]> >> wrote: >> >>> On Thu, 3 Jul 2014 18:14:41 +0200, Axel wrote: >>> Ok, >>> but what about my main question: >>> "Could we have a roots() method in PolynomialFunction class?" >>> >>> Which in the first step delegates to >>> LaguerreSolver#solveAllComplex()? >> >> I guess that people want to be careful before changing the API of >> "PolynomialFunction". [E.g. it would create a dependency towards >> the "o.a.c.m.complex" package. It might be better to add the >> functionality in that package (e.g. in "ComplexUtils").] >> >> Could you explain what you need with more details? >> In particular, what do you expect to get in addition to what the >> following code can already provide? >> >> ---CUT--- >> import >> org.apache.commons.math3.analysis.polynomials.PolynomialFunction; >> import org.apache.commons.math3.analysis.solvers.LaguerreSolver; >> import org.apache.commons.math3.complex.Complex; >> >> public class PolynomialRoots { >> private static final LaguerreSolver solver = new >> LaguerreSolver(); >> >> public static Complex[] solve(PolynomialFunction p) { >> return solver.solveAllComplex(p.getCoefficients(), 0d); >> } >> } >> ---CUT--- > > I agree with Thomas that it would be good to expose a Complex[] > roots() method directly in the PolynialFunction class. We can then > choose whatever numerical technique we like to back it, starting with > Laguerre and refining / specializing to data as we get better ideas. At this point, I didn't see any convincing argument that one choice is good and the other bad. A while back (when I cleaned up a the "solvers" package), I suggested that the next step would be to move the "Complex" root finders to a dedicated package and API. It is a more general issue. Also, I wonder whether it is a good idea to create a black-box root solver for polynomials, given that the algorithms to solve them can vary heavily depending on the degree. In an application, it would be fine; in a low-level library, we provide the means, and users choose the method. [Further discussion in that direction should go through "dev".] As for the OP's question, Thomas indicated that it can be done already. Hence: no changes required (unless the above code falls short of some as yet undefined expectation). Gilles >>> >>>> On Sat, Jun 28, 2014 at 8:26 PM, Ted Dunning >>>> <[hidden email]> wrote: >>>> That is one article, but it doesn't actually compare the numerical >>>> stability or efficiency of this method. It just invokes the >>>> stability of >>>> "numerical linear algebra". Whether this is a good way to compute >>>> roots is >>>> an open question. >>>> >>>> The other major question here is operation count. Computing >>>> eigenvalues of >>>> an explicit matrix is likely to be very intensive computationally. >>>> The >>>> wikipedia page on root-finding mentions in passing when is says >>>> that >>>> matrix-free methods are typically used with the eigenvalue >>>> approaches. >>>> >>>> This suggests that the preferable means to implement this idea is >>>> not to >>>> build the matrix in question, but to use an abstract linear >>>> operator which >>>> implements multiplication making use of the special form of the >>>> companion >>>> matrix. I am not sure if this approach is viable in the Commons >>>> matrix >>>> framework. I suspect not, but really don't have much of a clue >>>> about the >>>> real state of things. If the eigenvalue objects accept something >>>> like a >>>> LinearOperator object, then it is likely to work. >>>> >>>> This article[1] seems to suggest that there may be some numerical >>>> issues >>>> with large coefficients. That isn't surprising since many >>>> algorithms have >>>> similar problems. >>>> >>>> [1] >>>> >>>> http://noether.math.uoa.gr/conferences/sla2014/sites/default/files/Dopico.pdf >>>> >>>> >>>>> On Sat, Jun 28, 2014 at 6:33 AM, Axel <[hidden email]> wrote: >>>>> >>>>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart >>>>> <[hidden email]> wrote: >>>>> ... >>>>> > I did take a look at the stackoverflow question, and there is >>>>> already a >>>>> > way to do this in Commons Math using the LaguerreSolver via the >>>>> > solveComplex and solveAllComplex methods. >>>>> > >>>>> > But it might be good to support a second way using >>>>> EigenDecomposition as >>>>> > a stand-alone solver. >>>>> > >>>>> > I like the idea to add a roots() method to PolynomialFunction, >>>>> but which >>>>> > method to compute the roots is more robust? >>>>> >>>>> The attached link in the stackoverflow question to this paper: >>>>> http://techdigest.jhuapl.edu/TD/td2804/Williams.pdf >>>>> >>>>> has this conclusion: >>>>> "We have discussed some eigenvector methods for finding the roots >>>>> of multi- >>>>> variate polynomials. Unlike iterative, numerical methods >>>>> typically >>>>> applied to this >>>>> problem, the methods outlined in this article possess the >>>>> numerical >>>>> stability of >>>>> numerical linear algebra, do not require a good initial guess of >>>>> the >>>>> solution, and give all >>>>> solutions simultaneously. Furthermore, if the initial guess is >>>>> poor >>>>> enough, the methods >>>>> outlined herein may converge more quickly than iterative >>>>> methods." >>>>> >>>>> So I think the "EigenDecomposition method" is more appropriate if >>>>> you >>>>> don't have an initial guess to start from getting the roots!? >>>>> >>>>> -- >>>>> Axel Kramer >>>>> >>>>> >>>>> --------------------------------------------------------------------- >>>>> To unsubscribe, e-mail: [hidden email] >>>>> For additional commands, e-mail: [hidden email] >> >> >> >> --------------------------------------------------------------------- >> To unsubscribe, e-mail: [hidden email] >> For additional commands, e-mail: [hidden email] >> > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [hidden email] > For additional commands, e-mail: [hidden email] --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
Free forum by Nabble | Edit this page |