commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles <gil...@harfang.homelinux.org>
Subject Re: Could we have a roots() method in PolynomilFunction class?
Date Thu, 03 Jul 2014 21:30:35 GMT
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 <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


Mime
View raw message