[jira] [Commented] (MATH-1217) Add ways to calculate roots and companion matrix of a polynomial

["Thomas Neidhart (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/MATH-1217?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14498079#comment-14498079 ] 

Thomas Neidhart commented on MATH-1217:
---------------------------------------

Suggest to add the following code to PolynomialFunction:

{code}
    /**
     * Returns the companion matrix for the polynomial.
     *
     * @see <a href="http://en.wikipedia.org/wiki/Companion_matrix">Companion matrix (Wikipedia)</a>
     * @return a new companion matrix
     * @since 4.0
     */
    public RealMatrix companionMatrix() {
        final int degree = degree();

        final double cn = coefficients[degree];
        final RealMatrix companion = MatrixUtils.createRealMatrix(degree, degree);
        // set the subdiagonal elements to 1
        for (int i = 1; i < degree; i++) {
            companion.setEntry(i, i - 1, 1);
        }

        for (int i = 0; i < degree; i++) {
            companion.setEntry(i, degree - 1, -coefficients[i] / cn);
        }

        return companion;
    }

    /**
     * Find all complex roots for the polynomial.
     *
     * @return the complex roots of the polynomial.
     * @throws MaxCountExceededException if the root finding algorithm failed to converge
     * @since 4.0
     */
    public Complex[] roots() {
        final EigenDecomposition eigen = new EigenDecomposition(companionMatrix());
        final double[] realEigenvalues = eigen.getRealEigenvalues();
        final double[] imagEigenvalues = eigen.getImagEigenvalues();
        final Complex[] roots = new Complex[realEigenvalues.length];
        for (int i = 0; i < roots.length; i++) {
            roots[i] = new Complex(realEigenvalues[i], imagEigenvalues[i]);
        }
        return roots;
    }
{code}

The reason to use the eigenvalue method is as follows:

 * numpy does the same
 * numerical recipes mentions that this method is more robust than the Laguerre solver

If we use the eigenvalue method we need to resolve MATH-1216 first as this will increase the robustness of the eigen decomposition.

> Add ways to calculate roots and companion matrix of a polynomial
> ----------------------------------------------------------------
>
>                 Key: MATH-1217
>                 URL: https://issues.apache.org/jira/browse/MATH-1217
>             Project: Commons Math
>          Issue Type: New Feature
>            Reporter: Thomas Neidhart
>
> As requested on the user mailing list a while ago.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)