path: root/src/hyper/pages/UP.ht

% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\UnivariatePolynomialXmpTitle}{UnivariatePolynomial}
\newcommand{\UnivariatePolynomialXmpNumber}{9.83}
%
% =====================================================================
\begin{page}{UnivariatePolynomialXmpPage}{9.83 UnivariatePolynomial}
% =====================================================================
\beginscroll

The domain constructor \spadtype{UnivariatePolynomial}
%-% \HDindex{polynomial!one variable}{UnivariatePolynomialXmpPage}{9.83}{UnivariatePolynomial}
(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.
}{
\spadpaste{(p,q) : UP(x,INT) \bound{pdec}\bound{qdec}}
}
\xtc{
}{
\spadpaste{p := (3*x-1)**2 * (2*x + 8) \free{pdec}\bound{p}}
}
\xtc{
}{
\spadpaste{q := (1 - 6*x + 9*x**2)**2 \free{qdec}\bound{q}}
}
\xtc{
The usual arithmetic operations are available for univariate
polynomials.
}{
\spadpaste{p**2 + p*q  \free{p q}}
}
\xtc{
The operation \spadfunFrom{leadingCoefficient}{UnivariatePolynomial}
extracts the coefficient of the term of highest degree.
}{
\spadpaste{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}.
}{
\spadpaste{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}.
}{
\spadpaste{reductum p \free{p}}
}
\xtc{
The operation \spadfunFrom{gcd}{UnivariatePolynomial} computes the
greatest common divisor of two polynomials.
}{
\spadpaste{gcd(p,q) \free{p q}}
}
\xtc{
The operation \spadfunFrom{lcm}{UnivariatePolynomial} computes the
least common multiple.
}{
\spadpaste{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.
}{
\spadpaste{resultant(p,q) \free{p q}}
}
\xtc{
To compute the derivative of a univariate polynomial with respect to its
variable, use \spadfunFrom{D}{UnivariatePolynomial}.
}{
\spadpaste{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.
}{
\spadpaste{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}.
}{
\spadpaste{p(q) \free{p q}}
}
\xtc{
This substitutes \spad{p} for the variable in \spad{q}.
}{
\spadpaste{q(p) \free{p q}}
}
\xtc{
To obtain a list of coefficients of the polynomial, use
\spadfunFrom{coefficients}{UnivariatePolynomial}.
}{
\spadpaste{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.
}{
\spadpaste{reduce(gcd,l) \free{l}}
}
\xtc{
Alternatively (and more easily),
you can just call \spadfunFrom{content}{UnivariatePolynomial}.
}{
\spadpaste{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{\spad{i }} position contains the degree \spad{i-1}
coefficient of the polynomial.
\xtc{
}{
\spadpaste{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.
}{
\spadpaste{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.
}{
\spadpaste{p \free{p}}
}
\xtc{
We can demonstrate \userfun{squareTerms} on \spad{p}.
}{
\spadpaste{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{
}{
\spadpaste{(r,s) : UP(a1,FRAC INT) \bound{rdec}\bound{sdec}}
}
\xtc{
}{
\spadpaste{r := a1**2 - 2/3  \free{rdec}\bound{r}}
}
\xtc{
}{
\spadpaste{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.
}{
\spadpaste{r quo s \free{r s}}
}
\xtc{
The operation
\spadfunFrom{rem}{UnivariatePolynomial} computes the remainder.
}{
\spadpaste{r rem s \free{r s}}
}
\xtc{
The operation \spadfunFrom{divide}{UnivariatePolynomial} can be used to
return a record of both components.
}{
\spadpaste{d := divide(r, s) \free{r s}\bound{d}}
}
\xtc{
Now we check the arithmetic!
}{
\spadpaste{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.
}{
\spadpaste{integrate r \free{r}}
}
\xtc{
}{
\spadpaste{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}.
}{
\spadpaste{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.
}{
\spadpaste{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.
}{
\spadpaste{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.
}{
\spadpaste{u :: UP(b1,?) \free{u}}
}

See \downlink{``\ugProblemFactorTitle''}{ugProblemFactorPage} in Section \ugProblemFactorNumber\ignore{ugProblemFactor}
for a discussion of the factorization facilities
in \Language{} for univariate polynomials.
For more information on related topics, see
\downlink{``\ugIntroVariablesTitle''}{ugIntroVariablesPage} in Section \ugIntroVariablesNumber\ignore{ugIntroVariables},
\downlink{``\ugTypesConvertTitle''}{ugTypesConvertPage} in Section \ugTypesConvertNumber\ignore{ugTypesConvert},
\downlink{`Polynomial'}{PolynomialXmpPage}\ignore{Polynomial},
\downlink{`MultivariatePolynomial'}{MultivariatePolynomialXmpPage}\ignore{MultivariatePolynomial}, and
\downlink{`DistributedMultivariatePolynomial'}{DistributedMultivariatePolynomialXmpPage}\ignore{DistributedMultivariatePolynomial}.
%
\showBlurb{UnivariatePolynomial}
\endscroll
\autobuttons
\end{page}
%