On Thu, 3 Jul 2014 16:15:58 -0700, Phil Steitz wrote:
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.
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 black-box 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 low-level 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.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
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
