目录

Using PolyRoot to Solve Polynomial Roots

The polynomial root solver is used to calculate the real roots of a univariate polynomial. It takes a sparse polynomial representation as input for root solving and is suitable for scenarios that require high-precision polynomial root calculation, such as computer-aided design, signal processing, and control theory.

The related definition is as follows: A polynomial is described by the FAST_Poly structure in sparse format. The coeff array stores the coefficients of each term, and the pow array stores the corresponding exponents, which must be sorted in ascending order of exponents. For example, the polynomial can be represented as coeff = {1, -2, 3} and pow = {0, 1, 2}.

API Description

For details about the APIs, please refer to the API Reference.

API Description
FAST_ErrorCode HMS_FAST_PolyRoot_ComputeRoots (const FAST_Poly *poly, const size_t maxRootCount, double *root, size_t *rootCount) Computes a specified number of real roots of a polynomial.
FAST_ErrorCode HMS_FAST_PolyRoot_ComputeSingle (const FAST_Poly *poly, double *root) Computes the real root of the polynomial with the largest absolute value.
FAST_ErrorCode HMS_FAST_PolyRoot_ComputeRootIntervals (const FAST_Poly *poly, const size_t maxRootCount, double *leftBoundary, double *rightBoundary, size_t *rootCount) Computes the isolation intervals for a specified number of real roots of a polynomial, outputting the left and right bounds of each real root.

Development Procedure

  1. Link the related dynamic library in the CMake script.

    find_library(
    lib_fast_solver
    NAMES fast_solver
)
target_link_libraries(entry PRIVATE ${lib_fast_solver})

  2. Construct the FAST_Poly structure and populate the coefficient array coeff and exponent array pow (the exponents must be sorted in ascending order).

  3. Call the HMS_FAST_PolyRoot_ComputeRoots API to calculate the roots of a polynomial.

#include <cstdio>
#include <cstdlib>
#include "FASTKit/fast_solver_polynomial.h"

int main() {
    // Construct the polynomial f(x) = x^2 - 3x + 2 = (x-1)(x-2), whose roots are 1.0 and 2.0.
    // Coefficient array: [constant term, linear coefficient, quadratic coefficient]
    double coeff[] = {2.0, -3.0, 1.0};
    // Exponent array: [exponents corresponding to each term]
    uint32_t pow[] = {0, 1, 2};
    size_t length = 3;

    // Initialize the FAST_Poly structure.
    FAST_Poly poly;
    poly.coeff = coeff;
    poly.pow = pow;
    poly.length = length;

    // Define the array for storing the roots and the root count.
    double roots[2];
    size_t rootCount = 0;
    FAST_ErrorCode ret;

    // Call the API to compute the roots of the polynomial.
    ret = HMS_FAST_PolyRoot_ComputeRoots(&poly, 2, roots, &rootCount);
    if (ret != FAST_ERROR_CODE_SUCCESS) {
        printf("Failed to compute roots: %d\n", ret);
        return ret;
    }

    printf("Found %zu roots:\n", rootCount);
    for (size_t i = 0; i < rootCount; ++i) {
        printf("  root[%zu] = %f\n", i, roots[i]);
    }

    /*
     * Found 2 roots:
     *   root[0] = 1.000000
     *   root[1] = 2.000000
     */

    printf("ret = %d\n", ret);
    return 0;
}

Precautions

  1. When constructing the FAST_Poly structure and populating the coeff and pow arrays, note that the pow array must be sorted in ascending order of exponents.

  2. If the pow array is not sorted in ascending order of exponents, the function returns the FAST_ERROR_CODE_ILLEGAL_INPUT error code, indicating that the input parameters are invalid.