You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@commons.apache.org by Axel <ax...@gmail.com> on 2014/06/27 16:24:33 UTC
Could we have a roots() method in PolynomilFunction class?
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
[Math] Re: Could we have a roots() method in PolynomialFunctionclass?
Posted by Gilles <gi...@harfang.homelinux.org>.
On Thu, 3 Jul 2014 16:15:58 -0700, Phil Steitz wrote:
>> On Jul 3, 2014, at 2:30 PM, Gilles <gi...@harfang.homelinux.org>
>> 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
>>>> <te...@gmail.com> 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 <ax...@gmail.com> wrote:
>>>>>
>>>>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart
>>>>> <th...@gmail.com> 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: user-unsubscribe@commons.apache.org
>>>>> For additional commands, e-mail: user-help@commons.apache.org
>>
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
>> For additional commands, e-mail: user-help@commons.apache.org
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
> For additional commands, e-mail: user-help@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org
[Math] Re: Could we have a roots() method in PolynomialFunctionclass?
Posted by Gilles <gi...@harfang.homelinux.org>.
On Thu, 3 Jul 2014 16:15:58 -0700, Phil Steitz wrote:
>> On Jul 3, 2014, at 2:30 PM, Gilles <gi...@harfang.homelinux.org>
>> 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
>>>> <te...@gmail.com> 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 <ax...@gmail.com> wrote:
>>>>>
>>>>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart
>>>>> <th...@gmail.com> 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: user-unsubscribe@commons.apache.org
>>>>> For additional commands, e-mail: user-help@commons.apache.org
>>
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
>> For additional commands, e-mail: user-help@commons.apache.org
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
> For additional commands, e-mail: user-help@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: Could we have a roots() method in PolynomilFunction class?
Posted by Phil Steitz <ph...@gmail.com>.
> On Jul 3, 2014, at 2:30 PM, Gilles <gi...@harfang.homelinux.org> 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 <te...@gmail.com> 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 <ax...@gmail.com> wrote:
>>>>
>>>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart
>>>> <th...@gmail.com> 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: user-unsubscribe@commons.apache.org
>>>> For additional commands, e-mail: user-help@commons.apache.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
> For additional commands, e-mail: user-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org
Re: Could we have a roots() method in PolynomilFunctionclass?
Posted by Gilles <gi...@harfang.homelinux.org>.
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 <te...@gmail.com>
> 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 <ax...@gmail.com> wrote:
>>
>>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart
>>> <th...@gmail.com> 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: user-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: user-help@commons.apache.org
>>>
>>>
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org
Re: Could we have a roots() method in PolynomilFunction class?
Posted by Axel <ax...@gmail.com>.
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 <te...@gmail.com> 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 <ax...@gmail.com> wrote:
>
>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart
>> <th...@gmail.com> 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: user-unsubscribe@commons.apache.org
>> For additional commands, e-mail: user-help@commons.apache.org
>>
>>
--
Axel Kramer
---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org
Re: Could we have a roots() method in PolynomilFunction class?
Posted by Ted Dunning <te...@gmail.com>.
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 <ax...@gmail.com> wrote:
> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart
> <th...@gmail.com> 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: user-unsubscribe@commons.apache.org
> For additional commands, e-mail: user-help@commons.apache.org
>
>
Re: Could we have a roots() method in PolynomilFunction class?
Posted by Axel <ax...@gmail.com>.
On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart
<th...@gmail.com> 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: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org
Re: Could we have a roots() method in PolynomilFunction class?
Posted by Thomas Neidhart <th...@gmail.com>.
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: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org