Mailing-List: contact user-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Commons Users List" <user@commons.apache.org>
Received-SPF: pass (nike.apache.org: domain of phil.steitz@gmail.com
 designates 209.85.220.53 as permitted sender)
From: Phil Steitz <phil.steitz@gmail.com>
Content-Type: text/plain;
	charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (1.0)
Subject: Re: Could we have a roots() method in PolynomilFunction class?
Message-Id: <28C10486-770D-45A1-BB03-6D7DAD38550E@gmail.com>
Date: Thu, 3 Jul 2014 16:15:58 -0700
References: 
 <CAKHAbN8OhHBe81LA92E0sxrYjEhjCK5mp3N_x05Eqr1AHH3Ngg@mail.gmail.com>
 <53ADDA64.7070602@gmail.com>
 <CAKHAbN8oc2=BL9TiR+nVjB1rKZBU03d7YU42tChif0ZLa_mOfA@mail.gmail.com>
 <CAJwFCa0YLouqysrMiHW=564GPKQ9yjHkuotbKOWZYV4Lb4wdGQ@mail.gmail.com>
 <CAKHAbN8RKgLrnbXS8=BKrFdNqmhScAHa+4AHp=CZv8wpF=vOvw@mail.gmail.com>
 <cb988bcd1b74f85a1d42bbce3bbebe8d@scarlet.be>
In-Reply-To: <cb988bcd1b74f85a1d42bbce3bbebe8d@scarlet.be>
To: Commons Users List <user@commons.apache.org>


> On Jul 3, 2014, at 2:30 PM, Gilles <gilles@harfang.homelinux.org> wrote:
>=20
>> 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?"
>>=20
>> Which in the first step delegates to LaguerreSolver#solveAllComplex()?
>=20
> 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").]
>=20
> 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?
>=20
> ---CUT---
> import org.apache.commons.math3.analysis.polynomials.PolynomialFunction;
> import org.apache.commons.math3.analysis.solvers.LaguerreSolver;
> import org.apache.commons.math3.complex.Complex;
>=20
> public class PolynomialRoots {
>    private static final LaguerreSolver solver =3D new LaguerreSolver();
>=20
>    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() meth=
od directly in the PolynialFunction class.  We can then choose whatever nume=
rical technique we like to back it, starting with Laguerre and refining / sp=
ecializing to data as we get better ideas.

Phil
>=20
>=20
> Best regards,
> Gilles
>=20
>=20
>>=20
>>> On Sat, Jun 28, 2014 at 8:26 PM, Ted Dunning <ted.dunning@gmail.com> wro=
te:
>>> That is one article, but it doesn't actually compare the numerical
>>> stability or efficiency of this method.  It just invokes the stability o=
f
>>> "numerical linear algebra".  Whether this is a good way to compute roots=
 is
>>> an open question.
>>>=20
>>> 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.
>>>=20
>>> 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 whi=
ch
>>> implements multiplication making use of the special form of the companio=
n
>>> 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 th=
e
>>> real state of things.  If the eigenvalue objects accept something like a=

>>> LinearOperator object, then it is likely to work.
>>>=20
>>> This article[1] seems to suggest that there may be some numerical issues=

>>> with large coefficients.  That isn't surprising since many algorithms ha=
ve
>>> similar problems.
>>>=20
>>> [1]
>>> http://noether.math.uoa.gr/conferences/sla2014/sites/default/files/Dopic=
o.pdf
>>>=20
>>>=20
>>>> On Sat, Jun 28, 2014 at 6:33 AM, Axel <axelclk@gmail.com> wrote:
>>>>=20
>>>> 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 wh=
ich
>>>> > method to compute the roots is more robust?
>>>>=20
>>>> The attached link in the stackoverflow question to this paper:
>>>> http://techdigest.jhuapl.edu/TD/td2804/Williams.pdf
>>>>=20
>>>> has this conclusion:
>>>> "We have discussed some eigenvector methods for finding the roots of mu=
lti-
>>>> 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."
>>>>=20
>>>> So I think the "EigenDecomposition method" is more appropriate if you
>>>> don't have an initial guess to start from getting the roots!?
>>>>=20
>>>> --
>>>> Axel Kramer
>>>>=20
>>>> ---------------------------------------------------------------------
>>>> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
>>>> For additional commands, e-mail: user-help@commons.apache.org
>=20
>=20
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
> For additional commands, e-mail: user-help@commons.apache.org
>=20

---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org