commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles <gil...@harfang.homelinux.org>
Subject [Math] Re: Could we have a roots() method in PolynomialFunction class?
Date Fri, 04 Jul 2014 09:40:03 GMT
On Thu, 3 Jul 2014 16:15:58 -0700, Phil Steitz wrote:
>> On Jul 3, 2014, at 2:30 PM, Gilles <gilles@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 
>>>> <ted.dunning@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 <axelclk@gmail.com> wrote:
>>>>>
>>>>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart
>>>>> <thomas.neidhart@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


Mime
View raw message