You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@commons.apache.org by Gilles <gi...@harfang.homelinux.org> on 2014/07/03 23:30:35 UTC
Re: Could we have a roots() method in PolynomilFunctionclass?
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
[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