sicmutils.polynomial — sicmutils 0.21.1

->expression clj/s

(->expression p vars)

Accepts a Polynomial p and a sequence of symbols for each indeterminate, and emits the canonical form of the symbolic expression that represents Polynomial p.

A similar result could be achieved by calling (apply p vars); but Polynomial application uses Horner's rule, and form of the returned result will be different.

NOTE: this is the output stage of Flat Polynomial canonical form simplification. The input stage is handled by expression->.

NOTE See analyzer for an instance usable by sicmutils.expression.analyze/make-analyzer.

->power-series clj/s

(->power-series p)

Given a univariate polynomial p, returns a series/PowerSeries representation of the supplied Polynomial.

Given a series/PowerSeries, acts as identity.

Non-Polynomial coefficients return series/PowerSeries instances via series/constant; any multivariate Polynomial throws an exception.

NOTE use lower-arity to generate a univariate polynomial in the first indeterminate, given a multivariate polynomial.

->str clj/s

(->str p)

(->str p n)

Returns a string representation of the supplied Polynomial instance p.

The optional argument n specifies how many terms to include in the returned string before an ellipsis cuts them off.

->terms clj/s

(->terms p)

Given some Polynomial, returns the terms entry of the type. Handles other types as well:

• Acts as identity on vectors, interpreting them as vectors of terms
• any zero-valued p returns []
• any other coefficient returns a vector of a single constant term.

abs clj/s

(abs p)

If the leading-coefficient of p is negative, returns (negate p), else acts as identity.

add clj/s

(add p q)

Returns the sum of polynomials p and q, with appropriate handling for non-Polynomial coefficient inputs on either or both sides.

analyzer clj/s

Singleton sicmutils.expression.analyze/ICanonicalize instance.

arg-scale clj/s

(arg-scale p factors)

Given some Polynomial p, returns a new Polynomial generated by substituting each indeterminate x_i for f_i * x_i, where f_i is a factor supplied in the factors sequence.

When p is a multivariate Polynomial, each factor must be either a non-Polynomial or a Polynomial with the same arity as p.

arg-shift clj/s

(arg-shift p shifts)

Given some Polynomial p, returns a new Polynomial generated by substituting each indeterminate x_i for s_i + x_i, where s_i is a shift supplied in the shifts sequence.

When p is a multivariate Polynomial, each shift must be either a non-Polynomial or a Polynomial with the same arity as p.

arity clj/s

(arity p)

Returns the declared arity of the supplied Polynomial, or 0 for non-polynomial arguments.

c*xn clj/s

(c*xn arity c n)

Given some arity, a coefficient c and an exponent n, returns a monomial representing $c{x_0}^n$. The first indeterminate is always exponentiated.

Similar to make, this function attempts to drop down to scalar-land if possible:

• If c is [[sicmutils.value/zero?]], returns c
• if n is zero?, returns (constant arity c)

NOTE that negative exponents are not allowed.

coeff? clj/s

(coeff? x)

Returns true if the input x is explicitly not an instance of Polynomial, false otherwise.

Equivalent to (not (polynomial? x)).

coefficients clj/s

(coefficients p)

Returns a sequence of the coefficients of the supplied polynomial p. A coefficient is treated here as a monomial, and returns a sequence of itself.

If p is zero, returns an empty list.

constant clj/s

(constant c)

(constant arity c)

Given some coefficient c, returns a Polynomial instance with a single constant term referencing c.

arity defaults to 1; supply it to set the arity of the returned Polynomial.

contract clj/s

(contract p n)

If p is contractible? at index n, returns a new Polynomial instance of arity 1 less than p with all variable indices > n decremented.

For non-Polynomial inputs, acts as identity. Throws if p is not explicitly contractible?.

For example:

(= (make 2 {[1 2] 3 [3 4] 5})
   (contract
     (make 3 {[0 1 2] 3 [0 3 4] 5}) 0))

contractible? clj/s

(contractible? p n)

Returns true if n is a valid variable index for the Polynomial p, and the variable with that index has no powers greater than 0 in p, false otherwise.

cube clj/s

(cube p)

Returns the cube of polynomial p. Equivalent to (mul p (mul p p)).

degree clj/s

(degree p)

(degree p i)

Returns the degree of the supplied polynomial.

the degree of a polynomial is the highest of the degrees of the polynomial's individual terms with non-zero coefficients. The degree of an individual term is the sum of all exponents in the term.

Optionally, degree takes an indeterminate index i; in this case, degree returns the maximum power found for the ith indeterminate across all terms.

NOTE when passed either a 0 or a zero-polynomial, degree returns -1. See Wikipedia's 'degree of the zero polynomial' for color on why this is the case.

divide clj/s

(divide u v)

Given two polynomials u and v, returns a pair of polynomials of the form [quotient, remainder] using polynomial long division.

The contract satisfied by this returned pair is that

u == (add (mul quotient v) remainder)

divisible? clj/s

(divisible? n d)

Returns true if the numerator n is evenly divisible by d (ie, leaves no remainder), false otherwise.

NOTE that this performs a full division with divide. If you're planning on doing this, you may as well call divide and check that the remainder satisfies [[sicmutils.value/zero?]].

drop-leading-term clj/s

(drop-leading-term p)

Given some Polynomial p, returns p without its leading-term. non-Polynomial p inputs are treated at constant polynomials and return 0.

NOTE that drop-leading-term will return a non-Polynomial if the result of the mapping has only a constant term.

eq clj/s

(eq this that)

Returns true if the Polynomial this is equal to that. If that is a Polynomial, this and that are equal if they have equal terms and equal arity. Coefficients are compared using sicmutils.value/=.

If that is non-Polynomial, eq only returns true if this is a monomial and its coefficient is equal to that (again using sicmutils.value/=).

evaluate clj/s

(evaluate p xs)

Returns the result of evaluating a multivariate Polynomial p at the values in the sequence xs using Horner's rule.

If p is a non-Polynomial coefficient, acts as identity.

Supplying too many arguments in xs (ie, a greater number than the arity of p) will throw an exception. Too few arguments will result in a partial evaluation of p, leaving the remaining indeterminates with their variable indices shifted down.

For example:

(= (make [0 0 '(* 3 (expt x 2) y) 0 '(* 5 (expt x 2) (expt y 3))])
   (simplify
     (evaluate
       (make 3 {[2 1 2] 3 [2 3 4] 5}) ['x 'y])))

evenly-divide clj/s

(evenly-divide u v)

Returns the result of dividing the polynomial u by v (non-Polynomial instances are allowed).

Throws an exception if the division leaves a remainder. Else, returns the quotient.

expression-> clj/s

(expression-> expr)

(expression-> expr cont)

(expression-> expr cont v-compare)

Converts the supplied symbolic expression expr into Flat Polynomial canonical form (ie, a Polynomial instance). expr should be a bare, unwrapped expression built out of Clojure data structures.

Returns the result of calling continuation cont with the Polynomial and the list of variables corresponding to each indeterminate in the Polynomial. (contdefaults to vector).

The second optional argument v-compare allows you to provide a Comparator between variables. Sorting indeterminates by v-compare will determine the order of the indeterminates in the generated Polynomial. The list of variables passed to cont will be sorted using v-compare.

Absorbing an expression with expression-> and emitting it again with ->expression will generate the canonical form of an expression, with respect to the operations in the [[operators-known]] set.

This kind of simplification proceeds purely symbolically over the known Flat Polynomial operations; other operations outside the arithmetic available in polynomials over commutative rings should be factored out by an expression analyzer (see sicmutils.expression.analyze/make-analyzer) before calling expression->.

NOTE See analyzer for an instance usable by sicmutils.expression.analyze/make-analyzer.

expt clj/s

(expt p n)

Returns a polynomial generated by raising the input polynomial p to the (integer) power n.

Negative exponents are not supported. For negative polynomial exponentation, see rational-function/expt.

extend clj/s

(extend p n)

Interpolates a new variable into the supplied Polynomial p at index n by incrementing any existing variable index >= n.

Returns a new Polynomial of arity 1 greater than the arity of p, or equal to (inc n) if n is greater than the arity of p.

For non-Polynomial inputs (or negative n), acts as identity.

from-points clj/s

(from-points xs)

Given a sequence of points of the form [x, f(x)], returns a univariate polynomial that passes through each input point.

The degree of the returned polynomial is equal to (dec (count xs)).

horner-with-error clj/s

(horner-with-error a z)

(horner-with-error a z cont)

Takes a univariate polynomial a, an argument z and a continuation cont (vector by default) and calls the continuation with (SEE BELOW).

This Horner's rule evaluator is restricted to numerical coefficients and univariate polynomials. It returns by calling cont with 4 arguments:

• the computed value
• the values of the first two derivatives
• an estimate of the roundoff error incurred in computing the value

The recurrences used are from Kahan's 18 Nov 1986 paper 'Roundoff in Polynomial Evaluation', generalized for sparse representations and another derivative by GJS.

For $p = A(z)$, $q = A'(z)$, $r = A''(z)$, and $e$ = error in $A(x)$,

$$p_{j+n} = z^n p_j + a_{j+n}$$

$$e_{j+n} = |z|^n ( e_j + (n-1) p_j ) + |p_{j+n}|$$

$$q_{j+n} = z^n q_j + n z^{n-1} p_j$$

$$r_{j+n} = z^n r_j + n z^{n-1} q_j + 1/2 n (n-1) z^{n-2} p_j$$

identity clj/s

(identity)

(identity arity)

(identity arity i)

Generates a Polynomial instance representing a single indeterminate with constant 1.

When called with no arguments, returns a monomial of arity 1 that acts as identity in the first indeterminate.

The one-argument version takes an explicit arity, but still sets the identity to the first indeterminate.

The two-argument version takes an explicit i and returns a monomial of arity arity with an exponent of 1 in the ith indeterminate.

leading-base-coefficient clj/s

(leading-base-coefficient p)

Similar to leading-coefficient, but of the coefficient itself is a Polynomial, recurses down until it reaches a non-Polynomial lead coefficient.

If p is a non-Polynomial coefficient, acts as identity.

leading-coefficient clj/s

(leading-coefficient p)

Returns the coefficient of the leading (highest degree) term of the Polynomial p.

If p is a non-Polynomial coefficient, acts as identity.

leading-exponents clj/s

(leading-exponents p)

Returns the exponents of the leading (highest degree) term of the Polynomial p.

If p is a non-Polynomial coefficient, returns [[exponent/empty]].

leading-term clj/s

(leading-term p)

Returns the leading (highest degree) term of the Polynomial p.

If p is a non-Polynomial coefficient, returns a term with zero exponents and p as its coefficient.

linear clj/s

(linear arity i root)

Given some arity, an indeterminate index i and some constant root, returns a polynomial of the form x_i - root. The returned polynomial represents a linear equation in the ith indeterminate.

If root is 0, linear is equivalent to the two-argument version of identity.

lower-arity clj/s

(lower-arity p)

Given a multivariate Polynomial p, returns an equivalent univariate Polynomial whose coefficients are polynomials of arity equal to one less than the arity of p.

Use raise-arity to undo this transformation. See with-lower-arity for a function that packages these two transformations.

NOTE that lower-arity will drop a coefficient down to a non-Polynomial if the result of extracting the first variable leaves a constant term.

lowest-degree clj/s

(lowest-degree p)

Returns the lowest degree found across any term in the supplied Polynomial. If a non-Polynomial is supplied, returns either 0 or -1 if the input is itself a 0.

See degree for a discussion of this -1 case.

make clj/s

(make dense-coefficients)

(make arity expts->coef)

Generates a Polynomial instance (or a bare coefficient!) from either:

• a sequence of dense coefficients of a univariate polynomial (in ascending order)
• an explicit arity, and a sparse mapping (or sequence of pairs) of exponent => coefficient

In the first case, the sequence is interpreted as a dense sequence of coefficients of an arity-1 (univariate) polynomial. The coefficients begin with the constant term and proceed to each higher power of the indeterminate. For example, x^2 - 1 can be constructed by (make [-1 0 1]).

In the 2-arity case,

• arity is the number of indeterminates
• expts->coef is a map of an exponent representation to a coefficient.

The exponent portion of the mapping can be any of:

• a proper exponent entry created by sicmutils.polynomial.exponent
• a map of the form {variable-index, power}
• a dense vector of variable powers, like [3 0 1] for $x^3z$. The length of each vector should be equal to arity, in this case.

For example, any of the following would generate $4x^2y + 5xy^2$:

(make 2 [[[2 1] 4] [[1 2] 5]])
(make 2 {[2 1] 4, [1 2] 5})
(make 2 {{0 2, 1 1} 4, {0 1, 1 2} 5})

NOTE: make will try and return a bare coefficient if possible. For example, the following form will return a constant, since there are no explicit indeterminates with powers > 0:

(make 10 {{} 1 {} 2})
;;=> 3

See constant if you need an explicit Polynomial instance wrapping a constant.

map-coefficients clj/s

(map-coefficients f p)

Given a Polynomial, returns a new Polynomial instance generated by applying f to the coefficient of each term in p and filtering out all resulting zeros.

Given a non-Polynomial coefficient, returns (f p).

NOTE that map-coefficients will return a non-Polynomial if the result of the mapping has only a constant term.

map-exponents clj/s

(map-exponents f p)

(map-exponents f p new-arity)

Given a Polynomial, returns a new Polynomial instance generated by applying f to the exponents of each term in p and filtering out all resulting zeros. The resulting Polynomial will have either the same arity as p, or the explicit, optional new-arity argument. (This is because f might increase or decrease the total arity.)

Given a non-Polynomial coefficient, if (f empty-exponents) produces a non-zero result, errors without an explicit new-arity argument..

NOTE that map-exponents will return a non-Polynomial if the result of the mapping has only a constant term.

monic? clj/s

(monic? p)

Returns true if p is a monic polynomial, false otherwise.

A monic polynomial is a univariate polynomial with a leading coefficient that responds true to [[sicmutils.value/one?]]. This means that any coefficient that responds true to [[sicmutils.value/one?]] also qualifies as a monic polynomial.

monomial? clj/s

(monomial? p)

Returns true if p is either:

• a Polynomial instance with a single term, or
• a non-Polynomial coefficient,

false otherwise.

mul clj/s

(mul p q)

Returns the product of polynomials p and q, with appropriate handling for non-Polynomial coefficient inputs on either or both sides.

multivariate? clj/s

(multivariate? p)

Returns true if p is a Polynomial of arity > 1, false otherwise.

negate clj/s

(negate p)

Returns the negation of polynomial p, ie, a polynomial with all coefficients negated.

negative? clj/s

(negative? p)

Returns true if the leading-base-coefficient of p is generic/negative?, false otherwise.

new-variables clj/s

(new-variables n)

Returns a sequence of n monomials of arity n, each with an exponent of 1 for the ith indeterminate (where i matches the position in the returned sequence).

normalize clj/s

(normalize p)

(normalize p c)

Given a polynomial p, returns a normalized polynomial generated by dividing through either the leading-coefficient of p or an optional, explicitly supplied scaling factor c.

For example:

(let [p (make [5 3 2 2 10])]
  (univariate->dense (normalize p)))
;;=> [1/2 3/10 1/5 1/5 1]

partial-derivative clj/s

(partial-derivative p i)

Given some Polynomial p, returns the partial derivative of p with respect to the ith indeterminate. Throws if i is an invalid indeterminate index for p.

For non-Polynomial inputs, returns 0.

partial-derivatives clj/s

(partial-derivatives p)

Returns the sequence of partial derivatives of Polynomial p with respect to each indeterminate. The returned sequence has length equal to the arity of p.

For non-Polynomial inputs, returns an empty sequence.

Polynomial cljs

polynomial? clj/s

(polynomial? x)

Returns true if the supplied argument is an instance of Polynomial, false otherwise.

pseudo-remainder clj/s

(pseudo-remainder u v)

Returns the pseudo-remainder of univariate polynomials u and v.

NOTE: Fractions won't appear in the result; instead the divisor is multiplied by the leading coefficient of the dividend before quotient terms are generated so that division will not result in fractions.

Returns a pair of

• the remainder
• the integerizing factor needed to make this happen.

Similar in spirit to Knuth's algorithm 4.6.1R, except we don't multiply the remainder through during gaps in the remainder. Since you don't know up front how many times the integerizing multiplication will be done, we also return the number d for which d * u = q * v + r.

raise-arity clj/s

(raise-arity p a)

Given either a non-Polynomial coefficient or a univariate Polynomial with possibly-Polynomial coefficients, returns a new Polynomial of arity a generated by attaching the polynomial coefficients back as variables starting with 1.

raise-arity undoes the transformation of lower-arity. See with-lower-arity for a function that packages these two transformations.

reciprocal clj/s

(reciprocal p)

(reciprocal p i)

Given a polynomial p, returns the reciprocal polynomial with respect to the ith indeterminate. i defaults to 0.

The reciprocal polynomial of p with respect to i is generated by

• treating the polynomial as univariate with respect to i and pushing all other terms into the coefficients of the polynomial
• reversing the order of these coefficients
• flattening the polynomial out again

For example, note that the entries for the first indeterminate are reversed:

(= (make 3 {[3 0 0] 5 [2 0 1] 2 [0 2 1] 3})
   (reciprocal
     (make 3 {[0 0 0] 5 [1 0 1] 2 [3 2 1] 3})))

scale clj/s

(scale p c)

Given some polynomial p and a coefficient c, returns a new Polynomial generated by multiplying each coefficient of p by c (on the right).

See scale-l if left multiplication is important.

NOTE that scale will return a non-Polynomial if the result of the mapping has only a constant term.

scale-l clj/s

(scale-l c p)

Given some polynomial p and a coefficient c, returns a new Polynomial generated by multiplying each coefficient of p by c (on the left).

See scale if right multiplication is important.

NOTE that scale-l will return a non-Polynomial if the result of the mapping has only a constant term.

square clj/s

(square p)

Returns the square of polynomial p. Equivalent to (mul p p).

sub clj/s

(sub p q)

Returns the difference of polynomials p and q, with appropriate handling for non-Polynomial coefficient inputs on either or both sides.

touchard clj/s

(touchard n)

Returns the nth Touchard polynomial.

These are also called Bell polynomials (in Mathematica, implemented as BellB) or /exponential polynomials/.

trailing-coefficient clj/s

(trailing-coefficient p)

Returns the coefficient of the trailing (lowest degree) term of the Polynomial p.

If p is a non-Polynomial coefficient, acts as identity.

univariate->dense clj/s

(univariate->dense x)

(univariate->dense x x-degree)

Given a univariate Polynomial (see univariate?) returns a dense vector of the coefficients of each term in ascending order.

For example:

(univariate->dense (make [1 0 0 2 3 4]))
;;=> [1 0 0 2 3 4]

Supplying the second argument x-degree will pad the right side of the returning coefficient vector to be the max of x-degree and (degree x).

NOTE use lower-arity to generate a univariate polynomial in the first indeterminate, given a multivariate polynomial.

univariate? clj/s

(univariate? p)

Returns true if p is a Polynomial of arity 1, false otherwise.

valid-arity? clj/s

(valid-arity? p i)

Given some input p and an indeterminate index i, returns true if 0 <= i < (arity p), false otherwise.

with-lower-arity clj/s

(with-lower-arity u v continue)

Given:

• multivariate Polynomials u and v
• a continue function that accepts two univariate Polynomials with possibly-Polynomial coefficients,

Returns the result of calling lower-arity on u and v, passing the results to continue and using raise-arity to raise the result back to the original shared arity of u and v.

The exception is that if continue returns a non-Polynomial, with-lower-arity will not attempt to re-package it as a Polynomial.