.. _ca-poly: **ca_poly.h** -- dense univariate polynomials over the real and complex numbers =============================================================================== A :type:ca_poly_t represents a univariate polynomial over the real or complex numbers (an element of \mathbb{R}[X] or \mathbb{C}[X]), implemented as an array of coefficients of type :type:ca_struct. Most functions are provided in two versions: an underscore method which operates directly on pre-allocated arrays of coefficients and generally has some restrictions (such as requiring the lengths to be nonzero and not supporting aliasing of the input and output arrays), and a non-underscore method which performs automatic memory management and handles degenerate cases. Warnings: * A polynomial is always normalised by removing zero coefficients at the top. Coefficients will not be removed when Calcium is unable to prove that they are zero. The represented degree can therefore be larger than the degree of the mathematical polynomial. When the correct degree is needed, it is important to verify the leading coefficient. (Of course, this will never be an issue with polynomials that are explicitly monic, for example.) * The special values *Undefined*, unsigned infinity and signed infinity supported by the scalar :type:ca_t type are not really meaningful as coefficients of polynomials. We normally assume that the user does not assign those values to coefficients of polynomials, and the functions in this module will likewise normally not generate such coefficients. *Unknown* can still appear as a coefficient representing a number that is inaccessible for computation. A polynomial with numerical coefficients and with a nonzero leading coefficient is called *proper*. The function :func:ca_poly_is_proper can be used to check for violations. Types, macros and constants ------------------------------------------------------------------------------- .. type:: ca_poly_struct .. type:: ca_poly_t Contains a pointer to an array of coefficients (*coeffs*), the used length (*length*), and the allocated size of the array (*alloc*). A *ca_poly_t* is defined as an array of length one of type *ca_poly_struct*, permitting an *ca_poly_t* to be passed by reference. Memory management ------------------------------------------------------------------------------- .. function:: void ca_poly_init(ca_poly_t poly, ca_ctx_t ctx) Initializes the polynomial for use, setting it to the zero polynomial. .. function:: void ca_poly_clear(ca_poly_t poly, ca_ctx_t ctx) Clears the polynomial, deallocating all coefficients and the coefficient array. .. function:: void ca_poly_fit_length(ca_poly_t poly, slong len, ca_ctx_t ctx) Makes sure that the coefficient array of the polynomial contains at least *len* initialized coefficients. .. function:: void _ca_poly_set_length(ca_poly_t poly, slong len, ca_ctx_t ctx) Directly changes the length of the polynomial, without allocating or deallocating coefficients. The value should not exceed the allocation length. .. function:: void _ca_poly_normalise(ca_poly_t poly, ca_ctx_t ctx) Strips any top coefficients which can be proved identical to zero. Assignment and simple values ------------------------------------------------------------------------------- .. function:: void ca_poly_zero(ca_poly_t poly, ca_ctx_t ctx) Sets *poly* to the zero polynomial. .. function:: void ca_poly_one(ca_poly_t poly, ca_ctx_t ctx) Sets *poly* to the constant polynomial 1. .. function:: void ca_poly_x(ca_poly_t poly, ca_ctx_t ctx) Sets *poly* to the monomial *x*. .. function:: void ca_poly_set_ca(ca_poly_t poly, const ca_t c, ca_ctx_t ctx) void ca_poly_set_si(ca_poly_t poly, slong c, ca_ctx_t ctx) Sets *poly* to the constant polynomial *c*. .. function:: void ca_poly_set(ca_poly_t res, const ca_poly_t src, ca_ctx_t ctx) void ca_poly_set_fmpz_poly(ca_poly_t res, const fmpz_poly_t src, ca_ctx_t ctx) void ca_poly_set_fmpq_poly(ca_poly_t res, const fmpq_poly_t src, ca_ctx_t ctx) Sets *poly* the polynomial *src*. .. function:: void ca_poly_set_coeff_ca(ca_poly_t poly, slong n, const ca_t x, ca_ctx_t ctx) Sets the coefficient at position *n* in *poly* to *x*. .. function:: void ca_poly_transfer(ca_poly_t res, ca_ctx_t res_ctx, const ca_poly_t src, ca_ctx_t src_ctx) Sets *res* to *src* where the corresponding context objects *res_ctx* and *src_ctx* may be different. This operation preserves the mathematical value represented by *src*, but may result in a different internal representation depending on the settings of the context objects. Random generation ------------------------------------------------------------------------------- .. function:: void ca_poly_randtest(ca_poly_t poly, flint_rand_t state, slong len, slong depth, slong bits, ca_ctx_t ctx) Sets *poly* to a random polynomial of length up to *len* and with entries having complexity up to *depth* and *bits* (see :func:ca_randtest). .. function:: void ca_poly_randtest_rational(ca_poly_t poly, flint_rand_t state, slong len, slong bits, ca_ctx_t ctx) Sets *poly* to a random rational polynomial of length up to *len* and with entries up to *bits* bits in size. Input and output ------------------------------------------------------------------------------- .. function:: void ca_poly_print(const ca_poly_t poly, ca_ctx_t ctx) Prints *poly* to standard output. The coefficients are printed on separate lines. .. function:: void ca_poly_printn(const ca_poly_t poly, slong digits, ca_ctx_t ctx) Prints a decimal representation of *poly* with precision specified by *digits*. The coefficients are comma-separated and the whole list is enclosed in square brackets. Degree and leading coefficient ------------------------------------------------------------------------------- .. function:: int ca_poly_is_proper(const ca_poly_t poly, ca_ctx_t ctx) Checks that *poly* represents an element of \mathbb{C}[X] with well-defined degree. This returns 1 if the leading coefficient of *poly* is nonzero and all coefficients of *poly* are numbers (not special values). It returns 0 otherwise. It returns 1 when *poly* is precisely the zero polynomial (which does not have a leading coefficient). .. function:: int ca_poly_make_monic(ca_poly_t res, const ca_poly_t poly, ca_ctx_t ctx) Makes *poly* monic by dividing by the leading coefficient if possible and returns 1. Returns 0 if the leading coefficient cannot be certified to be nonzero, or if *poly* is the zero polynomial. .. function:: void _ca_poly_reverse(ca_ptr res, ca_srcptr poly, slong len, slong n, ca_ctx_t ctx) .. function:: void ca_poly_reverse(ca_poly_t res, const ca_poly_t poly, slong n, ca_ctx_t ctx) Sets *res* to the reversal of *poly* considered as a polynomial of length *n*, zero-padding if needed. The underscore method assumes that *len* is positive and less than or equal to *n*. Comparisons ------------------------------------------------------------------------------- .. function:: truth_t _ca_poly_check_equal(ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx) truth_t ca_poly_check_equal(const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx) Checks if *poly1* and *poly2* represent the same polynomial. The underscore method assumes that *len1* is at least as large as *len2*. .. function:: truth_t ca_poly_check_is_zero(const ca_poly_t poly, ca_ctx_t ctx) Checks if *poly* is the zero polynomial. .. function:: truth_t ca_poly_check_is_one(const ca_poly_t poly, ca_ctx_t ctx) Checks if *poly* is the constant polynomial 1. Arithmetic ------------------------------------------------------------------------------- .. function:: void _ca_poly_shift_left(ca_ptr res, ca_srcptr poly, slong len, slong n, ca_ctx_t ctx) void ca_poly_shift_left(ca_poly_t res, const ca_poly_t poly, slong n, ca_ctx_t ctx) Sets *res* to *poly* shifted *n* coefficients to the left; that is, multiplied by x^n. .. function:: void _ca_poly_shift_right(ca_ptr res, ca_srcptr poly, slong len, slong n, ca_ctx_t ctx) void ca_poly_shift_right(ca_poly_t res, const ca_poly_t poly, slong n, ca_ctx_t ctx) Sets *res* to *poly* shifted *n* coefficients to the right; that is, divided by x^n. .. function:: void ca_poly_neg(ca_poly_t res, const ca_poly_t src, ca_ctx_t ctx) Sets *res* to the negation of *src*. .. function:: void _ca_poly_add(ca_ptr res, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx) void ca_poly_add(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx) Sets *res* to the sum of *poly1* and *poly2*. .. function:: void _ca_poly_sub(ca_ptr res, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx) void ca_poly_sub(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx) Sets *res* to the difference of *poly1* and *poly2*. .. function:: void _ca_poly_mul(ca_ptr res, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx) void ca_poly_mul(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx) Sets *res* to the product of *poly1* and *poly2*. .. function:: void _ca_poly_mullow(ca_ptr C, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, slong n, ca_ctx_t ctx) void ca_poly_mullow(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, slong n, ca_ctx_t ctx) Sets *res* to the product of *poly1* and *poly2* truncated to length *n*. .. function:: void ca_poly_mul_ca(ca_poly_t res, const ca_poly_t poly, const ca_t c, ca_ctx_t ctx) Sets *res* to *poly* multiplied by the scalar *c*. .. function:: void ca_poly_div_ca(ca_poly_t res, const ca_poly_t poly, const ca_t c, ca_ctx_t ctx) Sets *res* to *poly* divided by the scalar *c*. .. function:: void _ca_poly_divrem_basecase(ca_ptr Q, ca_ptr R, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, const ca_t invB, ca_ctx_t ctx) int ca_poly_divrem_basecase(ca_poly_t Q, ca_poly_t R, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx) void _ca_poly_divrem(ca_ptr Q, ca_ptr R, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, const ca_t invB, ca_ctx_t ctx) int ca_poly_divrem(ca_poly_t Q, ca_poly_t R, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx) int ca_poly_div(ca_poly_t Q, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx) int ca_poly_rem(ca_poly_t R, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx) If the leading coefficient of *B* can be proved invertible, sets *Q* and *R* to the quotient and remainder of polynomial division of *A* by *B* and returns 1. If the leading coefficient cannot be proved invertible, returns 0. The underscore method takes a precomputed inverse of the leading coefficient of *B*. .. function:: void _ca_poly_pow_ui_trunc(ca_ptr res, ca_srcptr f, slong flen, ulong exp, slong len, ca_ctx_t ctx) void ca_poly_pow_ui_trunc(ca_poly_t res, const ca_poly_t poly, ulong exp, slong len, ca_ctx_t ctx) Sets *res* to *poly* raised to the power *exp*, truncated to length *len*. .. function:: void _ca_poly_pow_ui(ca_ptr res, ca_srcptr f, slong flen, ulong exp, ca_ctx_t ctx) void ca_poly_pow_ui(ca_poly_t res, const ca_poly_t poly, ulong exp, ca_ctx_t ctx) Sets *res* to *poly* raised to the power *exp*. Evaluation and composition ------------------------------------------------------------------------------- .. function:: void _ca_poly_evaluate_horner(ca_t res, ca_srcptr f, slong len, const ca_t x, ca_ctx_t ctx) void ca_poly_evaluate_horner(ca_t res, const ca_poly_t f, const ca_t a, ca_ctx_t ctx) void _ca_poly_evaluate(ca_t res, ca_srcptr f, slong len, const ca_t x, ca_ctx_t ctx) void ca_poly_evaluate(ca_t res, const ca_poly_t f, const ca_t a, ca_ctx_t ctx) Sets *res* to *f* evaluated at the point *a*. .. function:: void _ca_poly_compose_horner(ca_ptr res, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx) void ca_poly_compose_horner(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx) void _ca_poly_compose_divconquer(ca_ptr res, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx) void ca_poly_compose_divconquer(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx) void _ca_poly_compose(ca_ptr res, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx) void ca_poly_compose(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx) Sets *res* to the composition of *poly1* with *poly2*. Derivative and integral ------------------------------------------------------------------------------- .. function:: void _ca_poly_derivative(ca_ptr res, ca_srcptr poly, slong len, ca_ctx_t ctx) void ca_poly_derivative(ca_poly_t res, const ca_poly_t poly, ca_ctx_t ctx) Sets *res* to the derivative of *poly*. The underscore method needs one less coefficient than *len* for the output array. .. function:: void _ca_poly_integral(ca_ptr res, ca_srcptr poly, slong len, ca_ctx_t ctx) void ca_poly_integral(ca_poly_t res, const ca_poly_t poly, ca_ctx_t ctx) Sets *res* to the integral of *poly*. The underscore method needs one more coefficient than *len* for the output array. Power series division ------------------------------------------------------------------------------- .. function:: void _ca_poly_inv_series(ca_ptr res, ca_srcptr f, slong flen, slong len, ca_ctx_t ctx) void ca_poly_inv_series(ca_poly_t res, const ca_poly_t f, slong len, ca_ctx_t ctx) Sets *res* to the power series inverse of *f* truncated to length *len*. .. function:: void _ca_poly_div_series(ca_ptr res, ca_srcptr f, slong flen, ca_srcptr g, slong glen, slong len, ca_ctx_t ctx) void ca_poly_div_series(ca_poly_t res, const ca_poly_t f, const ca_poly_t g, slong len, ca_ctx_t ctx) Sets *res* to the power series quotient of *f* and *g* truncated to length *len*. This function divides by zero if *g* has constant term zero; the user should manually remove initial zeros when an exact cancellation is required. Elementary functions ------------------------------------------------------------------------------- .. function:: void _ca_poly_exp_series(ca_ptr res, ca_srcptr f, slong flen, slong len, ca_ctx_t ctx) void ca_poly_exp_series(ca_poly_t res, const ca_poly_t f, slong len, ca_ctx_t ctx) Sets *res* to the power series exponential of *f* truncated to length *len*. .. function:: void _ca_poly_log_series(ca_ptr res, ca_srcptr f, slong flen, slong len, ca_ctx_t ctx) void ca_poly_log_series(ca_poly_t res, const ca_poly_t f, slong len, ca_ctx_t ctx) Sets *res* to the power series logarithm of *f* truncated to length *len*. .. function:: void _ca_poly_atan_series(ca_ptr res, ca_srcptr f, slong flen, slong len, ca_ctx_t ctx) void ca_poly_atan_series(ca_poly_t res, const ca_poly_t f, slong len, ca_ctx_t ctx) Sets *res* to the power series inverse tangent of *f* truncated to length *len*. Greatest common divisor ------------------------------------------------------------------------------- .. function:: slong _ca_poly_gcd_euclidean(ca_ptr res, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, ca_ctx_t ctx) int ca_poly_gcd_euclidean(ca_poly_t res, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx) slong _ca_poly_gcd(ca_ptr res, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, ca_ctx_t ctx) int ca_poly_gcd(ca_poly_t res, const ca_poly_t A, const ca_poly_t g, ca_ctx_t ctx) Sets *res* to the GCD of *A* and *B* and returns 1 on success. On failure, returns 0 leaving the value of *res* arbitrary. The computation can fail if testing a leading coefficient for zero fails in the execution of the GCD algorithm. The output is normalized to be monic if it is not the zero polynomial. The underscore methods assume \text{lenA} \ge \text{lenB} \ge 1, and that both *A* and *B* have nonzero leading coefficient. They return the length of the GCD, or 0 if the computation fails. The *euclidean* version implements the standard Euclidean algorithm. The default version first checks for rational polynomials or attempts to certify numerically that the polynomials are coprime and otherwise falls back to an automatic choice of algorithm (currently only the Euclidean algorithm). Roots and factorization ------------------------------------------------------------------------------- .. function:: int ca_poly_factor_squarefree(ca_t c, ca_poly_vec_t fac, ulong * exp, const ca_poly_t F, ca_ctx_t ctx) Computes the squarefree factorization of *F*, giving a product F = c f_1 f_2^2 \ldots f_n^n where all f_i with f_i \ne 1 are squarefree and pairwise coprime. The nontrivial factors f_i are written to *fac* and the corresponding exponents are written to *exp*. This algorithm can fail if GCD computation fails internally. Returns 1 on success and 0 on failure. .. function:: int ca_poly_squarefree_part(ca_poly_t res, const ca_poly_t poly, ca_ctx_t ctx) Sets *res* to the squarefree part of *poly*, normalized to be monic. This algorithm can fail if GCD computation fails internally. Returns 1 on success and 0 on failure. .. function:: void _ca_poly_set_roots(ca_ptr poly, ca_srcptr roots, const ulong * exp, slong n, ca_ctx_t ctx) void ca_poly_set_roots(ca_poly_t poly, ca_vec_t roots, const ulong * exp, ca_ctx_t ctx) Sets *poly* to the monic polynomial with the *n* roots given in the vector *roots*, with multiplicities given in the vector *exp*. In other words, this constructs the polynomial (x-r_0)^{e_0} (x-r_1)^{e_1} \cdots (x-r_{n-1})^{e_{n-1}}. Uses binary splitting. .. function:: int _ca_poly_roots(ca_ptr roots, ca_srcptr poly, slong len, ca_ctx_t ctx) int ca_poly_roots(ca_vec_t roots, ulong * exp, const ca_poly_t poly, ca_ctx_t ctx) Attempts to compute all complex roots of the given polynomial *poly*. On success, returns 1 and sets *roots* to a vector containing all the distinct roots with corresponding multiplicities in *exp*. On failure, returns 0 and leaves the values in *roots* arbitrary. The roots are returned in arbitrary order. Failure will occur if the leading coefficient of *poly* cannot be proved to be nonzero, if determining the correct multiplicities fails, or if the builtin algorithms do not have a means to represent the roots symbolically. The underscore method assumes that the polynomial is squarefree. The non-underscore method performs a squarefree factorization. Vectors of polynomials -------------------------------------------------------------------------------- .. type:: ca_poly_vec_struct .. type:: ca_poly_vec_t Represents a vector of polynomials. .. function:: ca_poly_struct * _ca_poly_vec_init(slong len, ca_ctx_t ctx) void ca_poly_vec_init(ca_poly_vec_t res, slong len, ca_ctx_t ctx) Initializes a vector with *len* polynomials. .. function:: void _ca_poly_vec_fit_length(ca_poly_vec_t vec, slong len, ca_ctx_t ctx) Allocates space for *len* polynomials in *vec*. .. function:: void ca_poly_vec_set_length(ca_poly_vec_t vec, slong len, ca_ctx_t ctx) Resizes *vec* to length *len*, zero-extending if needed. .. function:: void _ca_poly_vec_clear(ca_poly_struct * vec, slong len, ca_ctx_t ctx) void ca_poly_vec_clear(ca_poly_vec_t vec, ca_ctx_t ctx) Clears the vector *vec*. .. function:: void ca_poly_vec_append(ca_poly_vec_t vec, const ca_poly_t poly, ca_ctx_t ctx) Appends *poly* to the end of the vector *vec*. .. raw:: latex \newpage