doc/htex/UP.htex

% Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
% All rights reserved.
%
% Redistribution and use in source and binary forms, with or without
% modification, are permitted provided that the following conditions are
% met:
%
%     - Redistributions of source code must retain the above copyright
%       notice, this list of conditions and the following disclaimer.
%
%     - Redistributions in binary form must reproduce the above copyright
%       notice, this list of conditions and the following disclaimer in
%       the documentation and/or other materials provided with the
%       distribution.
%
%     - Neither the name of The Numerical ALgorithms Group Ltd. nor the
%       names of its contributors may be used to endorse or promote products
%       derived from this software without specific prior written permission.
%
% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
% IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
% TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
% PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
% OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
% EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
% PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES-- LOSS OF USE, DATA, OR
% PROFITS-- OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
% LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
% NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
% SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


The domain constructor \spadtype{UnivariatePolynomial}
\index{polynomial!one variable}
(abbreviated \spadtype{UP})
creates domains of univariate polynomials in a specified variable.
For example, the domain
\spadtype{UP(a1,POLY FRAC INT)} provides polynomials in the single variable
\spad{a1} whose coefficients are general polynomials with rational
number coefficients.

\beginImportant
\noindent {\bf Restriction:}
\texht{\begin{quotation}\noindent}{\newline\indent{5}}
\Language{} does not allow you to create types where
\spadtype{UnivariatePolynomial} is contained in the coefficient type of
\spadtype{Polynomial}. Therefore,
\spadtype{UP(x,POLY INT)} is legal but \spadtype{POLY UP(x,INT)} is not.
\texht{\end{quotation}}{\indent{0}}
\endImportant

\xtc{
\spadtype{UP(x,INT)} is the domain of polynomials in the single
variable \spad{x} with integer coefficients.
}{
\spadcommand{(p,q) : UP(x,INT) \bound{pdec}\bound{qdec}}
}
\xtc{
}{
\spadcommand{p := (3*x-1)^2 * (2*x + 8) \free{pdec}\bound{p}}
}
\xtc{
}{
\spadcommand{q := (1 - 6*x + 9*x^2)^2 \free{qdec}\bound{q}}
}
\xtc{
The usual arithmetic operations are available for univariate
polynomials.
}{
\spadcommand{p^2 + p*q  \free{p q}}
}
\xtc{
The operation \spadfunFrom{leadingCoefficient}{UnivariatePolynomial}
extracts the coefficient of the term of highest degree.
}{
\spadcommand{leadingCoefficient p \free{p}}
}
\xtc{
The operation \spadfunFrom{degree}{UnivariatePolynomial} returns
the degree of the polynomial.
Since the polynomial has only one variable, the variable is not supplied
to operations like \spadfunFrom{degree}{UnivariatePolynomial}.
}{
\spadcommand{degree p \free{p}}
}
\xtc{
The reductum of the polynomial, the polynomial obtained by
subtracting the term of highest order, is returned by
\spadfunFrom{reductum}{UnivariatePolynomial}.
}{
\spadcommand{reductum p \free{p}}
}
\xtc{
The operation \spadfunFrom{gcd}{UnivariatePolynomial} computes the
greatest common divisor of two polynomials.
}{
\spadcommand{gcd(p,q) \free{p q}}
}
\xtc{
The operation \spadfunFrom{lcm}{UnivariatePolynomial} computes the
least common multiple.
}{
\spadcommand{lcm(p,q) \free{p q}}
}
\xtc{
The operation \spadfunFrom{resultant}{UnivariatePolynomial}
computes the resultant of two univariate polynomials.
In the case of \spad{p} and \spad{q}, the resultant is \spad{0} because they
share a common root.
}{
\spadcommand{resultant(p,q) \free{p q}}
}
\xtc{
To compute the derivative of a univariate polynomial with respect to its
variable, use \spadfunFrom{D}{UnivariatePolynomial}.
}{
\spadcommand{D p \free{p}}
}
\xtc{
Univariate polynomials can also be used as if they were functions.
To evaluate a univariate polynomial at some point, apply
the polynomial to the point.
}{
\spadcommand{p(2) \free{p}}
}
\xtc{
The same syntax is used for composing two univariate polynomials, i.e.
substituting one polynomial for the variable in another.
This substitutes \spad{q} for the variable in \spad{p}.
}{
\spadcommand{p(q) \free{p q}}
}
\xtc{
This substitutes \spad{p} for the variable in \spad{q}.
}{
\spadcommand{q(p) \free{p q}}
}
\xtc{
To obtain a list of coefficients of the polynomial, use
\spadfunFrom{coefficients}{UnivariatePolynomial}.
}{
\spadcommand{l := coefficients p \free{p}\bound{l}}
}
\xtc{
From this you can use \spadfunFrom{gcd}{UnivariatePolynomial}
and \spadfunFrom{reduce}{List}
to compute the content of the polynomial.
}{
\spadcommand{reduce(gcd,l) \free{l}}
}
\xtc{
Alternatively (and more easily),
you can just call \spadfunFrom{content}{UnivariatePolynomial}.
}{
\spadcommand{content p \free{p}}
}

Note that the operation \spadfunFrom{coefficients}{UnivariatePolynomial}
omits the zero coefficients from the list.
Sometimes it is useful to convert a univariate polynomial
to a vector whose \eth{i} position contains the degree \spad{i-1}
coefficient of the polynomial.
\xtc{
}{
\spadcommand{ux := (x^4+2*x+3)::UP(x,INT) \bound{ux}}
}
\xtc{
To get a complete vector of coefficients, use the operation
\spadfunFrom{vectorise}{UnivariatePolynomial}, which takes a
univariate polynomial and an integer denoting the length of the
desired vector.
}{
\spadcommand{vectorise(ux,5) \free{ux}}
}

It is common to want to do something to every term of a polynomial,
creating a new polynomial in the process.
\xtc{
This is a function for iterating across the terms of a polynomial,
squaring each term.
}{
\begin{spadsrc}[\bound{squareTerms}]
squareTerms(p) ==
  reduce(+,[t^2 for t in monomials p])
\end{spadsrc}
}
\xtc{
Recall what \spad{p} looked like.
}{
\spadcommand{p \free{p}}
}
\xtc{
We can demonstrate \userfun{squareTerms} on \spad{p}.
}{
\spadcommand{squareTerms p \free{p}\free{squareTerms}}
}

When the coefficients of the univariate polynomial belong to a
field,\footnote{For example, when the coefficients are rational
numbers, as opposed to integers.  The important property of
a field is that non-zero elements can be divided and produce
another element. The quotient of the integers 2 and 3 is not
another integer.}
it is possible to compute quotients and remainders.
\xtc{
}{
\spadcommand{(r,s) : UP(a1,FRAC INT) \bound{rdec}\bound{sdec}}
}
\xtc{
}{
\spadcommand{r := a1^2 - 2/3  \free{rdec}\bound{r}}
}
\xtc{
}{
\spadcommand{s := a1 + 4       \free{sdec}\bound{s}}
}
\xtc{
When the coefficients are rational numbers or rational expressions, the
operation \spadfunFrom{quo}{UnivariatePolynomial} computes the quotient
of two polynomials.
}{
\spadcommand{r quo s \free{r s}}
}
\xtc{
The operation
\spadfunFrom{rem}{UnivariatePolynomial} computes the remainder.
}{
\spadcommand{r rem s \free{r s}}
}
\xtc{
The operation \spadfunFrom{divide}{UnivariatePolynomial} can be used to
return a record of both components.
}{
\spadcommand{d := divide(r, s) \free{r s}\bound{d}}
}
\xtc{
Now we check the arithmetic!
}{
\spadcommand{r - (d.quotient * s + d.remainder) \free{r s d}}
}
\xtc{
It is also possible to integrate univariate polynomials when the
coefficients belong to a field.
}{
\spadcommand{integrate r \free{r}}
}
\xtc{
}{
\spadcommand{integrate s \free{s}}
}

One application of univariate polynomials is to see expressions in terms
of a specific variable.
%
\xtc{
We start with a polynomial in \spad{a1} whose coefficients
are quotients of polynomials in \spad{b1} and \spad{b2}.
}{
\spadcommand{t : UP(a1,FRAC POLY INT) \bound{tdec}}
}
\xtc{
Since in this case we are not talking about using multivariate
polynomials in only two variables, we use \spadtype{Polynomial}.
We also use \spadtype{Fraction} because we want fractions.
}{
\spadcommand{t := a1^2 - a1/b2 + (b1^2-b1)/(b2+3) \free{tdec}\bound{t}}
}
\xtc{
We push all the variables into a single quotient of polynomials.
}{
\spadcommand{u : FRAC POLY INT := t \bound{u}\free{t}}
}
\xtc{
Alternatively, we can view this as a polynomial in the variable
This is a {\it mode-directed} conversion: you indicate
as much of the structure as you care about and let \Language{}
decide on the full type and how to do the transformation.
}{
\spadcommand{u :: UP(b1,?) \free{u}}
}

See \spadref{ugProblemFactor}
for a discussion of the factorization facilities
in \Language{} for univariate polynomials.
For more information on related topics, see
\spadref{ugIntroVariables},
\spadref{ugTypesConvert},
\xmpref{Polynomial},
\xmpref{MultivariatePolynomial}, and
\xmpref{DistributedMultivariatePolynomial}.
%
\showBlurb{UnivariatePolynomial}