Re: Could we have a roots() method in PolynomilFunction class?
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()? 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 -- Axel Kramer - To unsubscribe, e-mail: user-unsubscr...@commons.apache.org For additional commands, e-mail: user-h...@commons.apache.org
Re: Could we have a roots() method in PolynomilFunction class?
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---
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
Re: Could we have a roots() method in PolynomilFunction class?
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
Re: Could we have a roots() method in PolynomilFunction class?
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
Re: Could we have a roots() method in PolynomilFunction class?
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
Could we have a roots() method in PolynomilFunction class?
Hello
Jira seems to be down?
So I'm trying here to post my request for an enhancement:
Could we have a roots() method in PolynomialFunction class?
For example I ported the code in this stackoverflow question to apache
commons math by using the EigenDecomposition class:
http://stackoverflow.com/questions/13805644/finding-roots-of-polynomial-in-java/13805708#13805708
See the attached file for an example.
--
Axel Kramer
Symja Library - Java Symbolic Math System
https://bitbucket.org/axelclk/symja_android_library/wiki/Home
package org.matheclipse.tests.examples;
import org.apache.commons.math3.complex.Complex;
import org.apache.commons.math3.exception.MathArithmeticException;
import org.apache.commons.math3.linear.Array2DRowRealMatrix;
import org.apache.commons.math3.linear.EigenDecomposition;
import org.apache.commons.math3.linear.RealMatrix;
public class FindRoot {
/**
* p
* Given a set of polynomial coefficients, compute the roots of the polynomial. Depending on the polynomial being considered the
* roots may contain complex number. When complex numbers are present they will come in pairs of complex conjugates.
* /p
*
* @param coefficients
*Coefficients of the polynomial.
* @return The roots of the polynomial
*/
public static Complex[] findRoots(double... coefficients) {
int N = coefficients.length - 1;
// Construct the companion matrix
RealMatrix c = new Array2DRowRealMatrix(N, N);
double a = coefficients[N];
for (int i = 0; i N; i++) {
c.setEntry(i, N - 1, -coefficients[i] / a);
}
for (int i = 1; i N; i++) {
c.setEntry(i, i - 1, 1);
}
try {
EigenDecomposition ed = new EigenDecomposition(c);
double[] realValues = ed.getRealEigenvalues();
double[] imagValues = ed.getImagEigenvalues();
Complex[] roots = new Complex[realValues.length];
for (int i = 0; i N; i++) {
roots[i] = new Complex(realValues[i], imagValues[i]);
}
return roots;
} catch (MathArithmeticException ime) {
ime.printStackTrace();
}
return null;
}
public static void main(String[] args) {
// (2.5*x^2+1650
Complex[] roots = findRoots(1650, 0, 2.5);
if (roots != null) {
for (int i = 0; i roots.length; i++) {
System.out.println(roots[i]);
}
}
}
}
-
To unsubscribe, e-mail: user-unsubscr...@commons.apache.org
For additional commands, e-mail: user-h...@commons.apache.org
Re: Could we have a roots() method in PolynomilFunction class?
On 06/27/2014 04:24 PM, Axel wrote: Hello Jira seems to be down? So I'm trying here to post my request for an enhancement: Could we have a roots() method in PolynomialFunction class? For example I ported the code in this stackoverflow question to apache commons math by using the EigenDecomposition class: http://stackoverflow.com/questions/13805644/finding-roots-of-polynomial-in-java/13805708#13805708 See the attached file for an example. Hi Alex, 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? Thomas - To unsubscribe, e-mail: user-unsubscr...@commons.apache.org For additional commands, e-mail: user-h...@commons.apache.org
