> On Jul 3, 2014, at 2:30 PM, Gilles <gil...@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 <ted.dunn...@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 <axel...@gmail.com> wrote: >>>> >>>> On Fri, Jun 27, 2014 at 10:56 PM, Thomas Neidhart >>>> <thomas.neidh...@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-unsubscr...@commons.apache.org >>>> For additional commands, e-mail: user-h...@commons.apache.org > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: user-unsubscr...@commons.apache.org > For additional commands, e-mail: user-h...@commons.apache.org > --------------------------------------------------------------------- To unsubscribe, e-mail: user-unsubscr...@commons.apache.org For additional commands, e-mail: user-h...@commons.apache.org