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 blackbox 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 lowlevel 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 rootfinding mentions in passing when is says
>>>> that
>>>> matrixfree 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 standalone 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, email: userunsubscribe@commons.apache.org
>>>>> For additional commands, email: userhelp@commons.apache.org
>>
>>
>>
>> 
>> To unsubscribe, email: userunsubscribe@commons.apache.org
>> For additional commands, email: userhelp@commons.apache.org
>>
>
> 
> To unsubscribe, email: userunsubscribe@commons.apache.org
> For additional commands, email: userhelp@commons.apache.org

To unsubscribe, email: userunsubscribe@commons.apache.org
For additional commands, email: userhelp@commons.apache.org
