Example Polynomial Roots - Revision history

Peter at 15:31, 7 July 2021

2021-07-07T15:31:20Z

Peter at 00:51, 19 May 2017

2017-05-19T00:51:34Z

Peter at 01:00, 10 August 2015

2015-08-10T01:00:25Z

Peter at 02:44, 1 April 2015

2015-04-01T02:44:16Z

Peter at 05:37, 22 March 2015

2015-03-22T05:37:08Z

Peter: Created page with "Eigenvalue decomposition can be used to find the roots in a polynomial by constructing the so called [http://en.wikipedia.org/wiki/Companion_matrix companion matrix]. While f..."

2015-03-22T05:36:18Z

Created page with "Eigenvalue decomposition can be used to find the roots in a polynomial by constructing the so called [http://en.wikipedia.org/wiki/Companion_matrix companion matrix]. While f..."

New page

Eigenvalue decomposition can be used to find the roots in a polynomial by constructing the so called [http://en.wikipedia.org/wiki/Companion_matrix companion matrix]. While faster techniques do exist for root finding, this is one of the most stable and probably the easiest to implement.

Because the companion matrix is not symmetric a generalized eigenvalue [MatrixDecomposition decomposition] is needed. The roots of the polynomial may also be [http://en.wikipedia.org/wiki/Complex_number complex]. Complex eigenvalues is the only instance in which EJML supports complex arithmetic. Depending on the application one might need to check to see if the eigenvalues are real or complex.

Example on GitHub:
* [https://github.com/lessthanoptimal/ejml/blob/master/examples/src/org/ejml/example/PolynomialRootFinder.java PolynomialRootFinder]

= Example Code =

<syntaxhighlight lang="java">
public class PolynomialRootFinder {

/**
* <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>
*
* <p>
* Coefficients are ordered from least to most significant, e.g: y = c[0] + x*c[1] + x*x*c[2].
* </p>
*
* @param coefficients Coefficients of the polynomial.
* @return The roots of the polynomial
*/
public static Complex64F[] findRoots(double... coefficients) {
int N = coefficients.length-1;

// Construct the companion matrix
DenseMatrix64F c = new DenseMatrix64F(N,N);

double a = coefficients[N];
for( int i = 0; i < N; i++ ) {
c.set(i,N-1,-coefficients[i]/a);
}
for( int i = 1; i < N; i++ ) {
c.set(i,i-1,1);
}

// use generalized eigenvalue decomposition to find the roots
EigenDecomposition<DenseMatrix64F> evd = DecompositionFactory.eig(N,false);

evd.decompose(c);

Complex64F[] roots = new Complex64F[N];

for( int i = 0; i < N; i++ ) {
roots[i] = evd.getEigenvalue(i);
}

return roots;
}
}
</syntaxhighlight>

@@ Line 5: / Line 5: @@
 External Resources:
 * [https://github.com/lessthanoptimal/ejml/blob/v0.31/examples/src/org/ejml/example/PolynomialRootFinder.java PolynomialRootFinder.java source code]
 = Example Code =
@@ Line 11: / Line 10: @@
 <syntaxhighlight lang="java">
 public class PolynomialRootFinder {
      /**
       * <p>
@@ Line 26: / Line 24: @@
       * @return The roots of the polynomial
       */
-     public static Complex_F64[] findRoots(double... coefficients) {
+     public static Complex_F64[] findRoots( double... coefficients ) {
-         int N = coefficients.length-1;
+         int N = coefficients.length - 1;
          // Construct the companion matrix
-         DMatrixRMaj c = new DMatrixRMaj(N,N);
+         DMatrixRMaj c = new DMatrixRMaj(N, N);
          double a = coefficients[N];
-         for( int i = 0; i < N; i++ ) {
+         for (int i = 0; i < N; i++) {
-             c.set(i,N-1,-coefficients[i]/a);
+             c.set(i, N - 1, -coefficients[i]/a);
+         }
-         for( int i = 1; i < N; i++ ) {
+         for (int i = 1; i < N; i++) {
-             c.set(i,i-1,1);
+             c.set(i, i - 1, 1);
+         }
          // use generalized eigenvalue decomposition to find the roots
-         EigenDecomposition_F64<DMatrixRMaj> evd =  DecompositionFactory_DDRM.eig(N,false);
+         EigenDecomposition_F64<DMatrixRMaj> evd = DecompositionFactory_DDRM.eig(N, false);
          evd.decompose(c);
@@ Line 47: / Line 45: @@
          Complex_F64[] roots = new Complex_F64[N];
-         for( int i = 0; i < N; i++ ) {
+         for (int i = 0; i < N; i++) {
              roots[i] = evd.getEigenvalue(i);
+         }

@@ Line 3: / Line 3: @@
 Because the companion matrix is not symmetric a generalized eigenvalue [MatrixDecomposition decomposition] is needed.  The roots of the polynomial may also be [http://en.wikipedia.org/wiki/Complex_number complex].
-Example on GitHub:
+External Resources:
-* [https://github.com/lessthanoptimal/ejml/blob/v0.27/examples/src/org/ejml/example/PolynomialRootFinder.java PolynomialRootFinder]
+* [https://github.com/lessthanoptimal/ejml/blob/v0.27/examples/src/org/ejml/example/PolynomialRootFinder.java PolynomialRootFinder.java source code]
 = Example Code =

@@ Line 1: / Line 1: @@
 Eigenvalue decomposition can be used to find the roots in a polynomial by constructing the so called [http://en.wikipedia.org/wiki/Companion_matrix companion matrix].  While faster techniques do exist for root finding, this is one of the most stable and probably the easiest to implement.
-Because the companion matrix is not symmetric a generalized eigenvalue [MatrixDecomposition decomposition] is needed.  The roots of the polynomial may also be [http://en.wikipedia.org/wiki/Complex_number complex].  Complex eigenvalues is the only instance in which EJML supports complex arithmetic.  Depending on the application one might need to check to see if the eigenvalues are real or complex.
+Because the companion matrix is not symmetric a generalized eigenvalue [MatrixDecomposition decomposition] is needed.  The roots of the polynomial may also be [http://en.wikipedia.org/wiki/Complex_number complex].
 Example on GitHub: