commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ted Dunning <ted.dunn...@gmail.com>
Subject Re: Could we have a roots() method in PolynomilFunction class?
Date Sat, 28 Jun 2014 18:26:00 GMT
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
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message