calc: Polynomials
11.4 Polynomials
================
A “polynomial” is a sum of terms which are coefficients times various
powers of a “base” variable. For example, ‘2 x^2 + 3 x - 4’ is a
polynomial in ‘x’. Some formulas can be considered polynomials in
several different variables: ‘1 + 2 x + 3 y + 4 x y^2’ is a polynomial
in both ‘x’ and ‘y’. Polynomial coefficients are often numbers, but
they may in general be any formulas not involving the base variable.
The ‘a f’ (‘calc-factor’) [‘factor’] command factors a polynomial
into a product of terms. For example, the polynomial ‘x^3 + 2 x^2 + x’
is factored into ‘x*(x+1)^2’. As another example, ‘a c + b d + b c + a
d’ is factored into the product ‘(a + b) (c + d)’.
Calc currently has three algorithms for factoring. Formulas which
are linear in several variables, such as the second example above, are
merged according to the distributive law. Formulas which are
polynomials in a single variable, with constant integer or fractional
coefficients, are factored into irreducible linear and/or quadratic
terms. The first example above factors into three linear terms (‘x’,
‘x+1’, and ‘x+1’ again). Finally, formulas which do not fit the above
criteria are handled by the algebraic rewrite mechanism.
Calc’s polynomial factorization algorithm works by using the general
root-finding command (‘a P’) to solve for the roots of the polynomial.
It then looks for roots which are rational numbers or complex-conjugate
pairs, and converts these into linear and quadratic terms, respectively.
Because it uses floating-point arithmetic, it may be unable to find
terms that involve large integers (whose number of digits approaches the
current precision). Also, irreducible factors of degree higher than
quadratic are not found, and polynomials in more than one variable are
not treated. (A more robust factorization algorithm may be included in
a future version of Calc.)
The rewrite-based factorization method uses rules stored in the
variable ‘FactorRules’. 
Rewrite Rules, for a discussion of the
operation of rewrite rules. The default ‘FactorRules’ are able to
factor quadratic forms symbolically into two linear terms, ‘(a x + b) (c
x + d)’. You can edit these rules to include other cases if you wish.
To use the rules, Calc builds the formula ‘thecoefs(x, [a, b, c, ...])’
where ‘x’ is the polynomial base variable and ‘a’, ‘b’, etc., are
polynomial coefficients (which may be numbers or formulas). The
constant term is written first, i.e., in the ‘a’ position. When the
rules complete, they should have changed the formula into the form
‘thefactors(x, [f1, f2, f3, ...])’ where each ‘fi’ should be a factored
term, e.g., ‘x - ai’. Calc then multiplies these terms together to get
the complete factored form of the polynomial. If the rules do not
change the ‘thecoefs’ call to a ‘thefactors’ call, ‘a f’ leaves the
polynomial alone on the assumption that it is unfactorable. (Note that
the function names ‘thecoefs’ and ‘thefactors’ are used only as
placeholders; there are no actual Calc functions by those names.)
The ‘H a f’ [‘factors’] command also factors a polynomial, but it
returns a list of factors instead of an expression which is the product
of the factors. Each factor is represented by a sub-vector of the
factor, and the power with which it appears. For example, ‘x^5 + x^4 -
33 x^3 + 63 x^2’ factors to ‘(x + 7) x^2 (x - 3)^2’ in ‘a f’, or to ‘[
[x, 2], [x+7, 1], [x-3, 2] ]’ in ‘H a f’. If there is an overall
numeric factor, it always comes first in the list. The functions
‘factor’ and ‘factors’ allow a second argument when written in algebraic
form; ‘factor(x,v)’ factors ‘x’ with respect to the specific variable
‘v’. The default is to factor with respect to all the variables that
appear in ‘x’.
The ‘a c’ (‘calc-collect’) [‘collect’] command rearranges a formula
as a polynomial in a given variable, ordered in decreasing powers of
that variable. For example, given ‘1 + 2 x + 3 y + 4 x y^2’ on the
stack, ‘a c x’ would produce ‘(2 + 4 y^2) x + (1 + 3 y)’, and ‘a c y’
would produce ‘(4 x) y^2 + 3 y + (1 + 2 x)’. The polynomial will be
expanded out using the distributive law as necessary: Collecting ‘x’ in
‘(x - 1)^3’ produces ‘x^3 - 3 x^2 + 3 x - 1’. Terms not involving ‘x’
will not be expanded.
The “variable” you specify at the prompt can actually be any
expression: ‘a c ln(x+1)’ will collect together all terms multiplied by
‘ln(x+1)’ or integer powers thereof. If ‘x’ also appears in the formula
in a context other than ‘ln(x+1)’, ‘a c’ will treat those occurrences as
unrelated to ‘ln(x+1)’, i.e., as constants.
The ‘a x’ (‘calc-expand’) [‘expand’] command expands an expression by
applying the distributive law everywhere. It applies to products,
quotients, and powers involving sums. By default, it fully distributes
all parts of the expression. With a numeric prefix argument, the
distributive law is applied only the specified number of times, then the
partially expanded expression is left on the stack.
The ‘a x’ and ‘j D’ commands are somewhat redundant. Use ‘a x’ if
you want to expand all products of sums in your formula. Use ‘j D’ if
you want to expand a particular specified term of the formula. There is
an exactly analogous correspondence between ‘a f’ and ‘j M’. (The ‘j D’
and ‘j M’ commands also know many other kinds of expansions, such as
‘exp(a + b) = exp(a) exp(b)’, which ‘a x’ and ‘a f’ do not do.)
Calc’s automatic simplifications will sometimes reverse a partial
expansion. For example, the first step in expanding ‘(x+1)^3’ is to
write ‘(x+1) (x+1)^2’. If ‘a x’ stops there and tries to put this
formula onto the stack, though, Calc will automatically simplify it back
to ‘(x+1)^3’ form. The solution is to turn simplification off first
(Simplification Modes), or to run ‘a x’ without a numeric prefix
argument so that it expands all the way in one step.
The ‘a a’ (‘calc-apart’) [‘apart’] command expands a rational
function by partial fractions. A rational function is the quotient of
two polynomials; ‘apart’ pulls this apart into a sum of rational
functions with simple denominators. In algebraic notation, the ‘apart’
function allows a second argument that specifies which variable to use
as the “base”; by default, Calc chooses the base variable automatically.
The ‘a n’ (‘calc-normalize-rat’) [‘nrat’] command attempts to arrange
a formula into a quotient of two polynomials. For example, given ‘1 +
(a + b/c) / d’, the result would be ‘(b + a c + c d) / c d’. The
quotient is reduced, so that ‘a n’ will simplify ‘(x^2 + 2x + 1) / (x^2
- 1)’ by dividing out the common factor ‘x + 1’, yielding ‘(x + 1) / (x
- 1)’.
The ‘a \’ (‘calc-poly-div’) [‘pdiv’] command divides two polynomials
‘u’ and ‘v’, yielding a new polynomial ‘q’. If several variables occur
in the inputs, the inputs are considered multivariate polynomials.
(Calc divides by the variable with the largest power in ‘u’ first, or,
in the case of equal powers, chooses the variables in alphabetical
order.) For example, dividing ‘x^2 + 3 x + 2’ by ‘x + 2’ yields ‘x +
1’. The remainder from the division, if any, is reported at the bottom
of the screen and is also placed in the Trail along with the quotient.
Using ‘pdiv’ in algebraic notation, you can specify the particular
variable to be used as the base: ‘pdiv(A,B,X)’. If ‘pdiv’ is given only
two arguments (as is always the case with the ‘a \’ command), then it
does a multivariate division as outlined above.
The ‘a %’ (‘calc-poly-rem’) [‘prem’] command divides two polynomials
and keeps the remainder ‘r’. The quotient ‘q’ is discarded. For any
formulas ‘a’ and ‘b’, the results of ‘a \’ and ‘a %’ satisfy ‘a = q b +
r’. (This is analogous to plain ‘\’ and ‘%’, which compute the integer
quotient and remainder from dividing two numbers.)
The ‘a /’ (‘calc-poly-div-rem’) [‘pdivrem’] command divides two
polynomials and reports both the quotient and the remainder as a vector
‘[q, r]’. The ‘H a /’ [‘pdivide’] command divides two polynomials and
constructs the formula ‘q + r/b’ on the stack. (Naturally if the
remainder is zero, this will immediately simplify to ‘q’.)
The ‘a g’ (‘calc-poly-gcd’) [‘pgcd’] command computes the greatest
common divisor of two polynomials. (The GCD actually is unique only to
within a constant multiplier; Calc attempts to choose a GCD which will
be unsurprising.) For example, the ‘a n’ command uses ‘a g’ to take the
GCD of the numerator and denominator of a quotient, then divides each by
the result using ‘a \’. (The definition of GCD ensures that this
division can take place without leaving a remainder.)
While the polynomials used in operations like ‘a /’ and ‘a g’ often
have integer coefficients, this is not required. Calc can also deal
with polynomials over the rationals or floating-point reals.
Polynomials with modulo-form coefficients are also useful in many
applications; if you enter ‘(x^2 + 3 x - 1) mod 5’, Calc automatically
transforms this into a polynomial over the field of integers mod 5: ‘(1
mod 5) x^2 + (3 mod 5) x + (4 mod 5)’.
Congratulations and thanks go to Ove Ewerlid
(‘ewerlid@mizar.DoCS.UU.SE’), who contributed many of the polynomial
routines used in the above commands.
Decomposing Polynomials, for several useful functions for
extracting the individual coefficients of a polynomial.
Info Catalog
calc: Simplifying Formulas
calc: Algebra
calc: Calculus